P7989 [USACO21DEC] Bracelet Crossings G

Bessie the cow likes handicrafts. In her spare time, she makes $N$ ($1\le N\le 50$) bracelets, numbered $1 \ldots N$. Bracelet $i$ is painted with color $i$, one of $N$ distinct colors. After making the bracelets, Bessie places them on a table for display (we can think of this as the 2D plane). She carefully arranges these bracelets to satisfy the following three conditions: - Each bracelet is a simple closed polygonal chain — a sequence of vertices (points) connected in order by line segments, with the first point equal to the last point (see the Wikipedia page for more details: [Polygonal_chain](https://en.wikipedia.org/wiki/Polygonal_chain), or the Baidu Baike page: [折线](https://baike.baidu.com/item/%E6%8A%98%E7%BA%BF/486302)). - No bracelet intersects itself (this corresponds to a “simple” polygonal chain). - No two bracelets intersect each other. Unfortunately, right after Bessie arranged the bracelets so carefully, Farmer John drove by on a tractor. The table shook, causing the bracelets to move around and possibly even break into multiple (not necessarily closed or simple) polygonal chains. After that, Bessie still wants to check whether the above three conditions are still satisfied. However, it is dark now, and she cannot see the bracelets clearly. Luckily, Bessie has a flashlight. She chooses $M$ ($1\le M\le 50$) vertical lines $x=1, x=2, \ldots, x=M$, and for each line, she shines the flashlight along that line from $y=-\infty$ to $y=\infty$, recording in order the colors of all bracelets she sees. Fortunately, no beam passes through any vertex of any polygonal chain, and no beam passes through two line segments at the same time. Also, for each beam, every color that appears appears exactly twice. Can you help Bessie use this information to determine whether the bracelets can still satisfy all three conditions above?

The input for each testcase contains $T$ subtasks ($1 \leq T \leq 50$). All subtasks must be answered correctly to pass the entire testcase. Adjacent subtasks are separated by a blank line. The first line contains $T$. Then follow $T$ subtasks. The first line of each subtask contains two integers $N$ and $M$. Then each subtask contains $M$ lines. For each $i$ from $1$ to $M$, line $i$ contains an integer $k_i$ ($0\le k_i\le 2N$, $k_i$ is even), followed by $k_i$ integers $c_{i1}, c_{i2},\ldots, c_{ik_i}$ ($c_{ij}\in [1,N]$, each $c_{ij}$ appears either zero times or twice). This means that when Bessie sweeps her flashlight from $(i,-\infty)$ to $(i,\infty)$, she sees the colors in order $c_{i1}, c_{i2},\ldots, c_{ik_i}$.

For each subtask, output YES if it is possible for all three conditions above to be satisfied. Otherwise, output NO.

[Sample Explanation] For the first subtask, one feasible arrangement of the bracelets is:  For the fourth subtask, one feasible arrangement of the bracelets is:  [Constraints] - Test point 2 satisfies $N = 1$. - Test points 3-5 satisfy $N = 2$. - Test points 6-8 satisfy $M = 1$. - Test points 9-14 satisfy $M = 2$. - Test points 15-20 have no additional constraints. Translated by ChatGPT 5