Busy Beaver 正在尝试进入 MIT。他没有去参加 SAT 考试，而是认为自己能做得更好——好三倍，因为他着手解决 3-SAT 问题！他找到了一个非常美妙的解法，但不幸的是，他申请材料的页边距太窄，写不下这个解法。于是，他提出了自己版本的题目，但他需要你的帮助来解决它：

令 $n, m$ 为正整数。有 $n$ 个变量 $x_1, \dots, x_n$，取值在 $\{0, 1\}$ 中。一个子句（clause）是三个变量 $x_a \cdot x_b \cdot x_c$ 的乘积，其中下标满足 $1 \le a \le b \le c \le n$。给定一个由 $m$ 个此类子句组成的和式表达式。例如，一个包含四个变量和三个子句的表达式可以是：

$$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_3 \cdot x_4 + x_2 \cdot x_3 \cdot x_4$$

请确定是否存在一种对 $x_1, \dots, x_n$ 的赋值，使得最终的表达式结果为奇数。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ ($1 \le n, m \le 10^5$)。

接下来的 $m$ 行，每行描述和式中的一个子句。第 $i$ 行包含三个空格分隔的整数 $a_i, b_i, c_i$ ($1 \le a_i \le b_i \le c_i \le n$)，表示和式中的第 $i$ 个子句为 $x_{a_i} \cdot x_{b_i} \cdot x_{c_i}$。

保证所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $10^5$。

输出格式

对于每个测试用例，如果存在一种 $x_i$ 的赋值使得表达式结果为奇数，则输出一行字符串 YES，否则输出 NO。你可以以任意大小写形式打印每个字母。例如，yes, Yes, YeS 都将被识别为肯定回答。

然后，如果你回答了 YES，请打印第二行，包含空格分隔的整数 $x_1, \dots, x_n$ ($x_i = 0$ 或 $1$)，使得表达式的计算结果为奇数。如果存在多个可能的解，打印其中任意一个即可。

子任务

如果你给出的 YES/NO 回答正确，但提供的 $x_i$ 值不正确，你将获得每个子任务 50% 的分数。对于每个测试用例，你必须输出恰好 $n$ 个 $x_i$ 的值才能获得部分分。

• (50 分)：在每个子句中，没有变量出现超过一次，即 $a_i < b_i < c_i$。
• (50 分)：无附加限制。

样例

样例输入 1

2
4 3
1 2 3
1 3 4
2 3 4
3 2
1 2 3
1 2 3

样例输出 1

YES
1 1 1 1
NO

说明

第一个测试用例与题目描述中的例子相同。在该表达式中，将所有变量设为 1 使得表达式等于 $1 + 1 + 1 = 3$，这是奇数。

在第二个测试用例中，给定的表达式是 $x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$。可以证明，不存在任何 $x_1, x_2, x_3$ 的赋值使得该表达式为奇数。