Перетин браслетів#11227

Перетин браслетів

1 секунда

128 мегабайтів

Дуже складна

Бесі створила $n$ браслетів, пронумерованих від $1$ до $n$ . $i$ -ий браслет пофарбований у колір $i$ з множини $n$ різних кольорів. Вона розклала їх на столі (який можна уявити як двовимірну площину) з дотриманням таких умов:

Кожен браслет є замкненою багатокутною ланкою — це серія вершин (точок), з'єднаних послідовно відрізками прямих, де перша і остання точки збігаються (детальніше дивіться у Вікіпедії: багатокутна ланка).
Браслет не має самоперетинів, тобто є "простою" багатокутною ланкою.
Жодні два браслети не перетинаються між собою.

На жаль, коли Фермер Джон проїжджав на тракторі, він випадково штовхнув стіл, і браслети впали, можливо, розбившись на не замкнені і не прості багатокутні ланки. Тепер Бесі хоче перевірити, чи виконуються всі три вказані вище умови. Проте було темно, і вона не може бачити браслети.

На щастя, у Бесі є ліхтарик. Вона обрала $m$ ( $1 \leq m \leq 50$ 1 \le m \le 50) вертикальних прямих $x = 1$ x = 1, $x = 2$ x = 2, ..., $x = m$ x = m і спрямувала промінь вздовж кожної з них від $y = - \infty$ y = -\infty до $y = \infty$ y = \infty, записуючи кольори всіх браслетів, які вона побачила в порядку їх появи. Промені ліхтарика не перетнули жодну вершину жодної багатокутної ланки. Крім того, для кожного променя кожен колір з'явився рівно двічі.

Допоможіть Бесі, використовуючи цю інформацію, визначити, чи можливо, щоб браслети задовольняли всім трьом вказаним вище умовам.

Вхідні дані

Перша стрічка містить кількість тестів $t$ ( $1 \leq t \leq 50$ 1 \le t \le 50).

Перша стрічка кожного тесту містить два цілі числа $n$ ( $1 \leq n \leq 50$ 1 \le n \le 50) і $m$ . Далі кожен тест містить $m$ додаткових рядків. Для кожного $i$ від $1$ до $m$ , $i$ -ий додатковий рядок містить ціле число $k_{i}$ k_i ( $0 \leq k_{i} \leq 2 n$ 0 \le k_i \le 2n, $k_{i}$ k_i парне), за яким слідують $k_{i}$ k_i цілих чисел $c_{i_{1}}$ c_{i_1}, $c_{i_{2}}$ c_{i_2}, ..., $c_{i_{k_{i}}}$ c_{i_{k_i}} ( $c_{i_{j}} \in [1, n]$ c_{i_j} \in [1, n], кожне $c_{i_{j}}$ c_{i_j} з'явиться $0$ або $2$ рази). Це означає, що коли Бесі світить ліхтариком від $(i, - \infty)$ до $(i, \infty)$ , вона побачить кольори $c_{i_{1}}$ c_{i_1}, $c_{i_{2}}$ c_{i_2}, ..., $c_{i_{k_{i}}}$ c_{i_{k_i}} в цьому порядку.

Вихідні дані

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

Приклади

Приклад 1

Примітка

Приклад відповідної конфігурації браслетів для першого тесту.

Відповідна конфігурація для $4$ -го тесту: