Пересечение браслетов - Задачі

Беси сделала n браслетов, последовательно пронумерованных 1..n. i-ый браслет раскрашен цветом i из множества из n различных цветов. Беси разложила их на столе (который мы можем рассматривать как двумерную плоскость) в соответствии со следующими ограничениями:

Каждый браслет - одна замкнутая многоугольная цепочка - серия вершин (точек), соединённых последовательно отрезками прямых, где первая и последняя точки свопадают (детальнее см. многоугольная цепочка),
Браслет не самопересекается (это соответсвует "простой") многоугольной цепочке.
Никакие два браслета не пересекаются.

К несчастью, Фермер Джон проезжая на тракторе, толкнул стол и браслеты упали со стола и возможно разбились (не обязательно замкнутые и простые) многоугольные цепочки. После этого Беси хочет проверить, выполняются ли теперь три указанных выше условия. Однако было темно, и она не может видеть браслеты сейчас.

К счастью, у Беси есть фонарик. Она выбрала m (1 ≤ m ≤ 50) вертикальных прямых x = 1, x = 2,..., x = m и для каждой вертикальной прямой она направила луч вдоль неё от y = −∞ до y = ∞, записывая цвета всех браслетов, которые она увидела в порядке их появления. По счастью, лучи фонарика не пересекли ни одну вершину ни одной многоугольной цепочки. Более того, для каждого луча каждый цвет появился ровно дважды.

Помогите Беси, используя эту информацию, определить возможно ли чтобы браслеты удовлетворяли всем трём указанным выше условиям.

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

Первая строка содержит количество тестов t (1 ≤ t ≤ 50).

Первая строка каждого теста содержит два целых числа n (1 ≤ n ≤ 50) и m. Далее каждый тест содержит m дополнительных строк. Для каждого i от 1 до m, i-ая дополнительная строка содержит целое число k_i (0 ≤ k_i ≤ 2n, k_i чётное, за которымм следуют k_i целых чисел c_i1, c_i2, ..., c_iki (c_ij ∈ [1, n], каждое c_i1 появится 0 или 2 раза). Это значит что когда Беси светит фонариком от (i, −∞) до (i, ∞), она увидит цвета c_i1, c_i2, ..., c_iki в этом порядке.

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

Для каждого теста выведите YES если возможно, чтобы все три условия выполнялись, или NO в противном случае.

Пример

Пример подходящей конфигурации браслетов для первого теста.

Подходлящая конфигурация для 4-го теста:

Ліміт часу 1 секунда

Ліміт використання пам'яті 128 MiB

Вхідні дані #1

5

1 2
2 1 1
2 1 1

1 3
2 1 1
0
2 1 1

2 1
4 1 2 1 2

4 2
6 1 2 2 3 3 1
6 1 2 4 4 2 1

2 2
4 1 1 2 2
4 2 2 1 1

Вихідні дані #1

YES
NO
NO
YES
NO

Джерело 2021 USACO Декабрь, Золото