#USACOC2212C. Bracelet Crossings

Bracelet Crossings

奶牛 Bessie 喜欢手工艺。在她的空闲时间,她制作了 NN 个手链,编号为 1N1 \ldots N。第 ii 个手链涂有颜色 ii,是 NN 种不同的颜色之一。制作完手链后,Bessie 将它们放在桌子上进行展示(我们可以将其视为二维平面)。她精心布置这些手链,以满足以下三个条件:

  1. 每个手链是一个简单闭合折线——一组顶点(点)依次用线段连接,并且第一个点和最后一个点相同(欢迎查阅维基百科页面了解更多详情:polygonal chain,或百度百科:折线),
  2. 没有手链与自身相交(这对应「简单」折线);以及
  3. 没有两条手链相交。

不幸的是,就在 Bessie 如此小心翼翼地布置好手链之后,Farmer John 开着拖拉机经过,桌子晃动起来,导致手链四处移动甚至可能断成了多个(不一定是闭合的或简单的)折线!在那之后,Bessie 还是想检查以上三个条件是否仍然成立。然而,天色已暗,她现在无法看清手链。

幸好 Bessie 有一个手电筒。她选择了 MM 条垂直线 x=1,x=2,,x=Mx=1, x=2, \ldots, x=M,并且对于每条线,她用手电筒的光沿着那条线从 y=y=-\infty 扫至 y=y=\infty,按照出现的顺序记录她看到的所有手链的颜色。幸运的是,没有光束穿过任何折线的顶点或同时穿过两条线段。此外,对于每一束光,所有出现的颜色都恰好出现了两次。

你能帮助 Bessie 使用此信息来确定手链是否仍然满足上述所有三个条件吗?

  • 1N501\le N\le 50
  • 1M501\le M\le 50

输入格式

每个测试用例的输入包含 TT 个子测试用例,所有子测试用例必须全部回答正确才能通过整个测试用例。相邻的子测试用例之间用空行分隔。

输入的第一行包含 TT。之后是 TT 个子测试用例。

每个子测试用例的第一行包含两个整数 NNMM。此后每个子测试用例还包含 MM 行。对 11MM 的每一个 ii,第 ii 行包含一个整数 kik_i0ki2N0\le k_i\le 2Nkik_i 为偶数),然后是 kik_i 个整数 ci1,ci2,,cikic_{i1}, c_{i2},\ldots, c_{ik_i}cij[1,N]c_{ij}\in [1,N],每个 cijc_{ij} 出现零次或两次)。这表示当 Bessie 将手电筒从 (i,)(i,-\infty) 扫至 (i,)(i,\infty) 时,她按顺序 ci1,ci2,,cikic_{i1}, c_{i2},\ldots, c_{ik_i} 看到了这些颜色。

  • 1T501 \leq T \leq 50

输出格式

对每个子测试用例,如果有可能使得以上三个条件均满足则输出 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
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

测试点性质

  • 测试点 2 满足 N=1N = 1
  • 测试点 3-5 满足 N=2N=2
  • 测试点 6-8 满足 M=1M=1
  • 测试点 9-14 满足 M=2M=2
  • 测试点 15-20 没有额外限制。

题目提供者

供题:Richard Qi