1255: #543. 「LibreOJ β Round #7」奴隶主的游戏

Memory Limit:1024 MB Time Limit:2.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

奴隶主家的公告:欢迎和我玩数独游戏,赢了你将获得万贯家财,输了 …… 而你正好看到这则公告

数独游戏的规则是这样的:

初始的时候有一个 nnn 阶数独(nnn 阶数独即边长为 n2n^2n2 的分成 n2n^2n2n×nn\times nn×n 区域的方格,下图为 444 阶数独),并且已经填了 kkk 个格子,现在两个人轮流在空格子中填数(当然是你先填啦),每次填完需保证局面合法(合法即要求每个人填完后同行同列同区域不能出现相同数字并且填的数字是 [1,n2][1,n^2][1,n2] 中的整数),能填必须填,不能填者输。

orzlca

现在你要确定你(先手)是否有必胜策略,以免鲁莽输掉游戏沦为奴隶。

输入格式

第一行一个整数 TTT 表示有 TTT 组数据。

对于每组数据第一行两个整数 n,kn,kn,k

接下来有 kkk 行,每行三个整数 x,y,zx,y,zx,y,z 表示第 xxxyyy 列填了数字 zzz。保证填的格子不重复,且已经填好的数字合法。

输出格式

对于每组数据输出一个字符串:YES 表示有必胜策略,NO 表示没有必胜策略。

样例

注意:样例中有 1≤n<41\le n < 41n<4 的情况,这只是为了便于解释样例及说明游戏规则,在实际的测试数据中保证 n≥4n \ge 4n4

样例输入 1

1
1 0

样例输出 1

YES

样例解释 1

初始局面是一个 1×11\times 11×1 的方块并且没有填,你只要填上 1 就可获胜。

样例输入 2

1
4 2
9 13 1
9 16 2

样例输出 2

NO

样例解释 2

输入即为上图填了 12 后的局面。

数据范围与提示

对于所有数据,4≤n≤15,0≤k≤2,1≤T≤20,1≤x,y,z≤n24\leq n \leq 15,0\leq k \leq 2,1 \leq T \leq 20,1\le x,y,z\le n^24n15,0k2,1T20,1x,y,zn2

保证填的格子不重复,且已经填好的数字合法。

详细的数据限制及约定如下(留空表示和上述所有数据的约定相同):

Subtask # 分值 nnn kkk
111 171717 ≤6\leq 66 -
222 252525 ≤11\leq 1111 -
333 121212 - =0=0=0
444 161616 - ≤1\leq 11
555 303030 - -