F. Скриншоты чата
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В чате контестов по программированию состоит $$$n$$$ человек. Участники чата упорядочены по активности, однако каждый человек видит самого себя в начале списка.

Например, в чате $$$4$$$ участника, и их порядок равен $$$[2, 3, 1, 4]$$$. Тогда

  • $$$1$$$-й пользователь видит порядок $$$[1, 2, 3, 4]$$$;
  • $$$2$$$-й пользователь видит порядок $$$[2, 3, 1, 4]$$$;
  • $$$3$$$-й пользователь видит порядок $$$[3, 2, 1, 4]$$$;
  • $$$4$$$-й пользователь видит порядок $$$[4, 2, 3, 1]$$$.

$$$k$$$ человек выложили в чат скриншоты, на которых виден порядок участников, показываемый данному пользователю. Скриншоты были сделаны в течение короткого промежутка времени, и порядок участников не изменился.

Ваша задача — определить, существует ли некоторый порядок, которому соответствуют все скриншоты.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5, n \cdot k \le 2 \cdot 10^5$$$) — количество участников чата и количество участников, выложивших скриншоты.

Следующие $$$k$$$ строк содержат описания скриншотов, выложенных участниками.

$$$i$$$-я строка содержит $$$n$$$ целых чисел $$$a_{ij}$$$ каждая ($$$1 \le a_{ij} \le n$$$, все $$$a_{ij}$$$ различны) — порядок участников, показываемый участнику $$$a_{i0}$$$, где $$$a_{i0}$$$ — автор скриншота. Можно показать, что в описании скриншота он всегда будет в начале списка.

Гарантируется, что сумма $$$n \cdot k$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Также гарантируется, что все авторы скриншотов различны.

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

Выведите $$$t$$$ строк, каждая из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите «YES», если существует хотя бы один порядок участников, при котором могли быть получены все $$$k$$$ скриншотов. Иначе выведите «NO».

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

Пример
Входные данные
10
5 1
1 2 3 4 5
4 4
1 2 3 4
2 3 1 4
3 2 1 4
4 2 3 1
6 2
1 3 5 2 4 6
6 3 5 2 1 4
3 3
1 2 3
2 3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 1
1
5 2
1 2 3 5 4
2 1 3 5 4
3 3
3 1 2
2 3 1
1 3 2
5 4
3 5 1 4 2
2 5 1 4 3
1 5 4 3 2
5 1 4 3 2
3 3
1 3 2
2 1 3
3 2 1
Выходные данные
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO