Problem Statement

There is a connected simple undirected graph with $N$ vertices and $M$ edges, where the vertices are numbered $1, \dots ,N$ and the edges are numbered $1, \dots ,M$. Edge $i$ connects vertices $A_i$ and $B_i$. Also, there are a total of $N+1$ cards, one each with the integers from $0$ to $N$ written on them.

Snuke performed the following operations in order:

1. Place one card on each vertex, and eat the remaining one card.
2. For each $i\ (1 \le i \le M)$, write on edge $i$ the bitwise $\mathrm{XOR}$ of the integers written on the two cards placed on vertices $A_i$ and $B_i$. Let this integer be $X_i$.
3. Discard all cards placed on the vertices.

Given the information about the graph ($N,M,A_1,\dots ,A_M,B_1,\dots ,B_M,X_1,\dots ,X_M$), determine the integer written on the card that Snuke ate. If it cannot be uniquely determined, output -1. It is guaranteed that the given $X$ can be obtained by the above operations.

You are given $T$ test cases; solve each of them.

What is bitwise $\mathrm{XOR}$? The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows: In the binary representation of $A \oplus B$, the digit in the $2^k$ ($k \geq 0$) place is $1$ if exactly one of the digits in the $2^k$ place in the binary representations of $A$ and $B$ is $1$, and $0$ otherwise. For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$). In general, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, p_3, \dots, p_k$.

Constraints

• $1 \le T \le 10^4$
• $1 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le A_i,B_i \le N$
• The given graph is a connected simple undirected graph.
• $X_1,\dots ,X_M$ can be obtained by the operations in the problem statement.
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• The sum of $M$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N M
A_1 B_1 X_1
A_2 B_2 X_2
\vdots
A_M B_M X_M

Output

Output $T$ lines.

The $i$-th line should contain the integer written on the card Snuke ate for the $i$-th test case if it can be uniquely determined, and -1 otherwise.