题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例 1

1
1 0

YES

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

1
4 2
9 13 1
9 16 2

NO

输入即为上图填了 1 和 2 后的局面。

数据范围与提示

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

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

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：