Беси сделала \(N\) браслетов, последовательно пронумерованных \(1 \ldots N\).
(\(1\le N\le 50\)). \(i\)-ый браслет раскрашен цветом \(i\) из множества из \(N\)
различных цветов. Беси разложила их на столе (который мы можем рассматривать
как двумерную плоскость) в соответствии со следующими ограничениями:
- Каждый браслет - одна замкнутая многоугольная цепочка -- серия вершин
(точек), соединённых последовательно отрезками прямых, где первая и последняя
точки свопадают (детальнее см.
многоугольная цепочка),
- Браслет не самопересекается (это соответсвует "простой") многоугольной цепочке.
- Никакие два браслета не пересекаются.
К несчастью, Фермер Джон проезжая на тракторе, толкнул стол и браслеты
упали со стола и возможно разбились (не обязательно замкнутые и простые)
многоугольные цепочки. После этого Беси хочет проверить, выполняются ли теперь
три указанных выше условия. Однако было темно, и она не может видеть браслеты сейчас.
К счастью, у Беси есть фонарик. Она выбрала \(M\) (\(1\le M\le 50\)) вертикальных
прямых \(x=1, x=2, \ldots, x=M\) и для каждой вертикальной прямой она направила луч
вдоль неё от \(y=-\infty\) до \(y=\infty\), записывая цвета всех браслетов, которые
она увидела в порядке их появления. По счастью, лучи фонарика не пересекли
ни одну вершину ни одной многоугольной цепочки. Более того, для каждого луча
каждый цвет появился ровно дважды.
Помогите Беси, используя эту информацию, определить возможно ли чтобы
браслеты удовлетворяли всем трём указанным выше условиям.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Каждый входной тест состоит из
\(T\) подтестов (
\(1 \leq T \leq 50\)), каждый из
которых нужно решить правильно, чтобы получить полный балл за тест.
Тесты разделены пустыми строками.
Первая строка ввода содержит \(T\). Далее следуют \(T\) подтестов.
Первая строка каждого подтеста содержит два целых числа \(N\) \(M\).
Далее каждый подтест содержит \(M\) дополнительных строк. Для каждого \(i\) от \(1\) до \(M\),
\(i\)-ая дополнительная строка содержит целое число \(k_i\) (\(0\le k_i\le 2N\), \(k_i чётное\),
за которымм следуют \(k_i\) целых чисел \(c_{i1}, c_{i2},\ldots, c_{ik_i}\)
(\(c_{ij}\in [1,N]\), каждое \(c_{ij}\) появится 0 или 2 раза). Это значит что
когда Беси светит фонариком от \((i,-\infty)\) до \((i,\infty)\),
она увидит цвета \(c_{i1}, c_{i2},\ldots, c_{ik_i}\) в этом порядке.
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите YES если возможно, чтобы все три условия выполнялись,
или NO в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
YES
NO
NO
YES
NO
|