CF2257A.Creating Abbreviations

The Beaver was given a set of words $S$, which initially contained $n$ words. Then he performed the following operation $m$ times:

1. The Beaver forms a sequence of one or more words from the set $S$. The same word may appear in the sequence several times. An abbreviation$^{\text{∗}}$ is formed from the resulting phrase.
2. Then the Beaver adds the resulting abbreviation to $S$ and can now use it in subsequent operations as an ordinary word.

You are given the $n$ initial words that were in the set $S$, and the set of abbreviations that the Beaver formed. Determine whether the Beaver made a mistake and whether all these abbreviations could have appeared as a result of the operation described above. Note that the abbreviations did not necessarily appear in the same order in which they are given to you.

$^{\text{∗}}$The abbreviation of a sequence is the word produced by the first letters of the words in the sequence. For example, the sequence birch OAK birch redwood produces the abbreviation BOBR.

海狸得到了一个单词集合 $S$，该集合初始时包含 $n$ 个单词。随后，他执行了如下操作 $m$ 次：

1. 海狸从集合 $S$ 中选取一个或多个单词构成一个序列（同一单词可在序列中重复出现）。由该短语生成一个缩写词$^{\text{∗}}$。
2. 接着，海狸将生成的缩写词加入集合 $S$ 中，此后即可像普通单词一样在后续操作中使用它。

你被给定了集合 $S$ 初始时的 $n$ 个单词，以及海狸所生成的一组缩写词。请判断海狸是否犯了错误，即：这些缩写词是否有可能全部通过上述操作产生。（注意：这些缩写词在输入中给出的顺序，不一定与其实际生成顺序一致。）

$^{\text{∗}}$一个序列的缩写词，是指该序列中各单词首字母依次拼接而成的单词。例如，序列 birch OAK birch redwood 的缩写词为 BOBR。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ — the number of ordinary words and the number of abbreviations, respectively ($1 \le n, m \le 100$).

Each of the next $n$ lines contains one string $w_i$ — an ordinary word ($1 \le |w_i| \le 20$).

Each of the next $m$ lines contains one string $a_i$ — an abbreviation formed by Bobr ($1 \le |a_i| \le 20$).

All ordinary words consist of lowercase English letters, and all abbreviations consist of uppercase English letters. In each test case, all strings $w_1, w_2, \ldots, w_n, a_1, a_2, \ldots, a_m$ are pairwise distinct.

The total length of all strings over all test cases does not exceed $50\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ —— 分别表示普通单词的数量和缩写词的数量（$1 \le n, m \le 100$）。

接下来的 $n$ 行中，每行包含一个字符串 $w_i$ —— 一个普通单词（$1 \le |w_i| \le 20$）。

再接下来的 $m$ 行中，每行包含一个字符串 $a_i$ —— Bobr 构造的一个缩写词（$1 \le |a_i| \le 20$）。

所有普通单词均由小写英文字母组成，所有缩写词均由大写英文字母组成。在每个测试用例中，所有字符串 $w_1, w_2, \ldots, w_n, a_1, a_2, \ldots, a_m$ 两两互不相同。

所有测试用例中所有字符串的总长度不超过 $50\,000$。

For each test case, print "YES" if there exists a suitable order in which the given abbreviations could have appeared, and "NO" otherwise.

You may print each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

对于每个测试用例，如果存在一种合适的顺序，使得给定的缩写词可以按该顺序出现，则输出 “YES”；否则输出 “NO”。

你可以以任意大小写形式输出每个字母（小写或大写）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均被视为有效的肯定回答。

In the first test case, the order AG, BG, CG, ABC is suitable. The first three abbreviations can be created using the pairs of words apple and grand, banana and great, and cherry and good, respectively. After that, the abbreviation ABC can be created using the already created abbreviations AG, BG, and CG.

In the second test case, one can create AA using apple twice.

In the third test case, one can first create A using apple, and then create AA using apple and the already created abbreviation A.

In the fourth test case, it can be shown that the required order of creating the abbreviations does not exist.

在第一个测试用例中，顺序 AG、BG、CG、ABC 是可行的。前三个缩写分别可由单词对 apple 与 grand、banana 与 great、cherry 与 good 创建。此后，缩写 ABC 可利用已创建的缩写 AG、BG 和 CG 来生成。

在第二个测试用例中，可以使用两次 apple 创建 AA。

在第三个测试用例中，可先使用 apple 创建 A，然后利用 apple 和已创建的缩写 A 来创建 AA。

在第四个测试用例中，可以证明：不存在满足要求的缩写创建顺序。