A. 3-SAT
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is trying to get into MIT. Instead of taking the SAT, he thinks he can do better — three times better, as he sets out to solve 3-SAT! He's found a truly marvelous solution, but unfortunately, the margins of his application were too narrow to contain it. So, he came up with his own version of the problem, but he needs your help solving it:

Let $$$n, m$$$ be positive integers. There are $$$n$$$ variables $$$x_1, \dots, x_n$$$ taking values in $$$\{0, 1\}$$$. A clause is a product of three variables $$$x_a \cdot x_b \cdot x_c$$$ with indices $$$1 \leq a \leq b \leq c \leq n$$$. You are given an expression that is a sum of $$$m$$$ such clauses. For example, one such expression in four variables with three clauses could be $$$$$$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_3 \cdot x_4 + x_2 \cdot x_3 \cdot x_4.$$$$$$ Determine if it is possible to choose the values $$$x_1, \dots, x_n$$$ such that the resulting expression is odd.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 10^5)$$$. The description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ ($$$1 \leq n, m \leq 10^5$$$).

The next $$$m$$$ lines of each test case describe each of the clauses in the sum. The $$$i^{\mathrm{th}}$$$ of them consists of three space separated integers $$$a_i, b_i, c_i$$$ ($$$1 \leq a_i \leq b_i \leq c_i \leq n$$$), denoting that the $$$i^{\mathrm{th}}$$$ clause of the sum is $$$x_{a_i} \cdot x_{b_i} \cdot x_{c_i}$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases do not exceed $$$10^5$$$.

Output

For each test case, output one line containing the string YES if there exists a setting of the $$$x_i$$$ to make the expression odd, and NO otherwise. You can print each letter in any case. For example, yes, Yes, YeS will all be recognized as a positive answer.

Then, if you responded with YES, print a second line consisting of space separated integers $$$x_1, \dots, x_n$$$ ($$$x_i = 0$$$ or $$$1$$$) that makes the expression evaluate to an odd number. If there are multiple possible solutions, print any of them.

Scoring

You will receive $$$50\%$$$ of the points for each subtask if the YES/NO responses are correct, but the provided values of $$$x_i$$$ are not. For each testcase, you must output exactly $$$n$$$ values of $$$x_i$$$ for partial credit.

  • ($$$50$$$ points): Within each clause, no variable appears more than once, i.e. $$$a_i \lt b_i \lt c_i$$$.
  • ($$$50$$$ points): No additional constraints.
Example
Input
2
4 3
1 2 3
1 3 4
2 3 4
3 2
1 2 3
1 2 3
Output
YES
1 1 1 1 
NO
Note

The first test case is identical to the example in the problem statement. In this expression, setting all of the variables to $$$1$$$ makes the expression equal to $$$1 + 1 + 1 = 3$$$, which is odd.

In the second test case, the given expression is $$$x_1 \cdot x_2 \cdot x_3 + x_1 \cdot x_2 \cdot x_3$$$. It can be shown that no setting of $$$x_1, x_2, x_3$$$ makes this expression odd.