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

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: fengchanghn

题目描述

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

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

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

orzlca

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

输入格式

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

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

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

输出格式

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

样例

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

样例输入 1

1
1 0

样例输出 1

YES

样例解释 1

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

样例输入 2

1
4 2
9 13 1
9 16 2

样例输出 2

NO

样例解释 2

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

数据范围与提示

对于所有数据, 4\leq n \leq 15,0\leq k \leq 2,1 \leq T \leq 20,1\le x,y,z\le n^2

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

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

Subtask # 分值 n k
1 17 \leq 6 -
2 25 \leq 11
3 12 - =0
4 16 \leq 1
5 30 -