A. Создание аббревиатур
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бобру был дан набор слов $$$S$$$, в нём изначально содержалось $$$n$$$ слов. Далее он $$$m$$$ раз выполнил следующую операцию:

  1. Бобр составляет последовательность из одного или более слов из множества $$$S$$$. Одно и то же слово может встречаться в последовательности несколько раз. Из получившейся фразы формируется аббревиатура$$$^{\text{∗}}$$$.
  2. Затем бобр добавляет получившуюся аббревиатуру в $$$S$$$ и теперь может использовать её в последующих операциях как обычное слово.

Вам даны $$$n$$$ изначальных слов, которые были в множестве $$$S$$$, и множество аббревиатур, которые составил Бобр. Определите, не ошибся ли Бобр и могли ли все эти аббревиатуры появиться в результате применения вышеописанной операции. Обратите внимание, что аббревиатуры появлялись не обязательно именно в таком порядке, в каком они даются вам.

$$$^{\text{∗}}$$$Аббревиатурой последовательности называется слово, составленное из первых букв слов в последовательности. Например, birch OAK birch redwood формирует аббревиатуру BOBR

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$ — аббревиатуру, которую составил Бобр ($$$1 \le |a_i| \le 20$$$).

Все обычные слова состоят из строчных букв английского алфавита, а все аббревиатуры — из заглавных букв английского алфавита. В каждом наборе входных данных все строки $$$w_1, w_2, \ldots, w_n, a_1, a_2, \ldots, a_m$$$ попарно различны.

Суммарная длина всех строк по всем наборам входных данных не превосходит $$$50\,000$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если существует подходящий порядок появления данных аббревиатур, и «NO» иначе.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
4
6 4
apple
grand
banana
great
cherry
good
AG
BG
CG
ABC
1 1
apple
AA
1 2
apple
A
AA
2 2
apple
avocado
B
BA
Выходные данные
YES
YES
YES
NO
Примечание

В первом наборе входных данных подходит порядок AG, BG, CG, ABC. Первые три аббревиатуры можно создать, используя пары слов apple и grand, banana и great, cherry и good соответственно. После этого аббревиатуру ABC можно создать, используя уже созданные аббревиатуры AG, BG и CG.

Во втором наборе входных данных можно создать AA, используя apple два раза.

В третьем наборе входных данных можно сначала создать A, используя apple, а затем создать AA, используя apple и уже созданную аббревиатуру A.

В четвёртом наборе входных данных можно показать, что нужного порядка создания аббревиатур не существует.