F. Xored Pairs
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You need to construct an array $$$a_1, a_2, \dots, a_n$$$ $$$\left(0 \leq a_i \lt 2^{30}\right)$$$ that satisfies $$$m$$$ given constraints. Each constraint is one of two types —

  1. $$$a_i \neq x$$$, for given $$$i$$$ and $$$x$$$.
  2. $$$a_i \oplus a_j = x$$$, for given $$$i,\ j$$$ and $$$x$$$.
Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le m \le 10^5$$$) — the length of the required array and the number of constraints.

The following $$$m$$$ lines each contain the description of a constraint —

  • 1 i x — First type of constraint. It means $$$a_i \neq x$$$, ($$$1 \le i \le n$$$; $$$0 \le x \lt 2^{30}$$$).
  • 2 i j x — Second type of constraint. It means $$$a_i \oplus a_j = x$$$, ($$$1 \le i,\ j \le n$$$; $$$i \neq j$$$; $$$0 \le x \lt 2^{30}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$, and the sum of $$$m$$$ doesn't exceed $$$10^5$$$.

Output

For each test case, if it is impossible to construct such an array, print "No".

Otherwise, print "Yes" in the first line. In the second line print $$$n$$$ integers corresponding to the constructed array $$$a$$$ $$$\left(0 \leq a_i \lt 2^{30}\right)$$$ .

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

If there are multiple solutions, print any.

Example
Input
2
3 4
1 1 0
2 1 2 3
2 2 3 1
2 3 1 2
3 4
1 1 0
2 1 2 4
2 2 3 1
2 3 1 2
Output
YES
1 2 3
NO