You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定若干组“父目录—子文件”关系，以及要求的题目文件夹数量 $m$。请判断每组给出的提交目录是否符合以下格式。

1. 根目录只能有一个，名称必须由至少一个字母后面接至少一个数字组成，字母在前、数字在后，且不能有其他字符。例如 BJ01、bJ01 合法，123、ABC、A1B 不合法。
2. 根目录下必须恰有 $m$ 个题目文件夹，名称只能由字母组成。
3. 每个题目文件夹中必须恰有一个 .cpp 文件，文件名必须等于该文件夹名加上 .cpp。例如文件夹 task 中必须有 task.cpp。
4. 本题只判断文件名，不判断文件类型。即 task.cpp 可以是一个文件夹，但它不能再包含任何子文件。
5. 不能有多余的文件或目录，所有给出的节点必须构成一棵以根目录为根的树。

输入给出的关系可能不合法，例如一个节点有多个父亲、存在环、存在多个根等，这些情况都判为不合法。

输入格式

第一行一个正整数 $t$，表示数据组数。

对于每组数据：

• 第一行两个正整数 $n,m$，分别表示关系数量和要求的题目文件夹数量。
• 接下来 $n$ 行，每行两个字符串 $A,B$，表示 $B$ 是 $A$ 的子文件或子目录。

保证同一组数据中不会重复给出完全相同的关系；每个名字在整组数据中唯一标识一个文件或目录。

输出格式

输出 $t$ 行，每行一个 yes 或 no，表示该组目录是否符合格式。

1
8 4
BJ01 task
task task.cpp
BJ01 apple
apple apple.cpp
BJ01 banana
banana banana.cpp
BJ01 candy
candy candy.cpp

yes

1
8 4
123 task
task task.cpp
123 plane
plane plane.cpp
123 banana
banana banana.cpp
123 candy
candy candy.cpp

no

样例解释

样例 $1$：根目录 BJ01 符合“字母 + 数字”的格式，下面恰有 task、apple、banana、candy 四个题目文件夹，而 $m=4$，每个文件夹中都有一个同名的 .cpp 文件，且没有多余文件，因此合法。

样例 $2$：根目录 123 只有数字、没有字母，不符合根目录命名规则，因此不合法。

数据范围与约定

所有名字长度不超过 $20$，只包含大小写字母、数字以及 -、.、(、)。

下发样例

下发样例下载