Bracelet Crossings

题目描述

奶牛 Bessie 喜欢手工艺。空闲时，她制作了 $N$ ($1\le N\le 50$) 条手链，方便起见编号为 $1 \ldots N$。第 $i$ 条 手链被涂成 $N$ 种不同颜色中的第 $i$ 种颜色。制作完手链后，Bessie 把它们放在桌子上展示（可以认为是在二维平面上）。她小心地摆放手链，使其满足以下三个条件： 每条手链都是一条单一的闭合折线链——由一系列顶点（点）按顺序用线段连接而成，并且首尾点相同（更多细节欢迎查阅 wikipedia 页面： polygonal chain ）， 没有任何一条手链与自身相交（这对应于“简单”的折线链）；并且 任意两条手链互不相交。 不幸的是，就在 Bessie 如此小心地摆好手链后，Farmer John 开着拖拉机路过，震动了桌子，导致手链移动，甚至可能断裂成多条（不一定闭合或简单的）折线链！事后，Bessie 想检查上述三个条件是否仍然成立。然而天太黑了，她已经看不见手链了。 幸运的是，Bessie 有一支手电筒。她选择了 $M$ ($1\le M\le 50$) 条竖直直线 $x=1, x=2, \ldots, x=M$，并且对每条直线，她沿着该直线将手电光束从 $y=-\infty$ 扫到 $y=\infty$，记录她看到的所有手链颜色按出现顺序排列的序列。幸运的是，没有任何光束恰好穿过任意折线链的顶点，也不会在同一时刻穿过两条线段。此外，对每一束光而言，出现过的每种颜色都恰好出现两次。 你能否利用这些信息判断：是否存在一种可能，使得这些手链仍然满足上述三个条件？

输入格式

每个输入包含 $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）。这表示当 Bessie 将手电筒从 $(i,-\infty)$ 扫到 $(i,\infty)$ 时，她按顺序遇到的颜色为 $c_{i1}, c_{i2},\ldots, c_{ik_i}$。

输出格式

对每个子测试用例：如果存在一种可能使得上述三个条件可以同时满足，则输出 YES；否则输出 NO。

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

提示

第一个子用例的一种可行手链构型示例如下： 对于第四个子用例，一种可行的摆放方式如下： 计分（SCORING）： 测试点 2 满足 $N = 1$。 测试点 3-5 满足 $N=2$。 测试点 6-8 满足 $M=1$。 测试点 9-14 满足 $M=2$。 测试点 15-20 没有额外限制。 题目鸣谢：Richard Qi

标签: USACO|2021|Gold

来源

USACO|2021|Gold