G. Xor Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are tasked with constructing a tree with $$$n$$$ nodes. Each edge must have a non-negative integer weight.

Additionally, you are given $$$m$$$ constraints. Each constraint is described by three integers $$$u$$$, $$$v$$$, and $$$w$$$, meaning that the bitwise XOR of the weights of all edges along the unique path between nodes $$$u$$$ and $$$v$$$ must be equal to $$$w$$$.

Determine whether such a tree exists. If it does, output any valid assignment of edges and their weights.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq 4 \cdot 10^5$$$).

The next $$$m$$$ lines contain three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$0 \leq w \lt 2^{30}$$$), representing a constraint.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

—

Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Tests $$$1-20$$$ satisfy no additional constraints.

Output

For each test case, output "YES" or "NO", depending on whether or not such a tree exists. 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 you output "YES", output $$$n - 1$$$ lines, each containing three space-separated integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$0 \leq w \lt 2^{30}$$$), denoting that there is an edge between nodes $$$u$$$ and $$$v$$$ with weight $$$w$$$.

Example
Input
2
5 5
1 5 3
1 4 4
3 5 5
3 2 1
2 5 4
5 2
2 3 3
2 3 4
Output
YES
1 3 6
3 4 2
2 4 3
4 5 7
NO
Note

For the first test case, the sample output corresponds to the tree below:

We can show that this tree satisfies all listed constraints. For example, for the constraint $$$u = 1$$$, $$$v = 5$$$, $$$w = 3$$$, the path XOR from node $$$1$$$ to node $$$5$$$ is $$$6 \oplus 2 \oplus 7 = 3$$$, satisfying the constraint.

For the second test case, there is no possible tree because it is impossible for the path between node $$$2$$$ and node $$$3$$$ to have a path XOR of both $$$3$$$ and $$$4$$$.

—

Problem Idea: theyashb

Problem Preparation: n685

Occurrences: Novice G, Advanced C