Chef c8kbf has an unrooted, weighted tree with N nodes, where vertices u and v are connected by an edge with weight w.

The value of the simple path from x to y is defined as the [bitwise XOR] of the weights of the edges it consists of.
Recall that a simple path is a path that does not have repeating vertices.

Help Chef c8kbf find any four vertices a, b, c, d, such that:
a < b and c < d;
The value of the simple path from a to b is equal to that of the path from c to d;
The pairs (a, b) and (c, d) are different. In other words, $a \neq c$ or $b \neq d$.
Note that the four vertices do not have to be all distinct. For example, it is allowed for a and c to be the same if b and d are different.

If no four vertices satisfy such a property, report so. If there are multiple answers, output any one of them.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input. For each test case,
• The first line contains an integer N, the number of vertices.
• The next N-1 lines contain three space-separated integers u_{i}, v_{i}, and w_{i}, denoting an edge between u_{i} and v_{i} with weight w_{i}. It is guaranteed that these edges will form a tree.

------ Output Format ------

For each test case, output four space-separated integers a, b, c, and d on a new line, representing the four vertices. If there are multiple answers, output any one of them.

If no four vertices satisfy the property, output -1 on a new line instead.

------ Constraints ------

$1 ≤ T ≤ 10$
$3 ≤ N ≤ 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$
$u_{i} \neq v_{i}$ for each $1 ≤ i ≤ N-1$.
$0 ≤ w_{i} ≤ 2^{20}$
- It is guaranteed that the given edges will form a tree.
- The sum of $N$ over all test cases won't exceed $3\cdot10^{5}$.

----- Sample Input 1 ------
3
4
1 2 1
2 3 2
2 4 3
4
1 2 2
2 3 4
2 4 8
3
1 2 5
2 3 0
----- Sample Output 1 ------
1 4 2 3
-1
1 2 1 3
----- explanation 1 ------
Test case $1$: The value of the path between vertices $1$ and $4$ is $1\oplus 3 = 2$. The path between vertices $3$ and $2$ only has one edge, so the value is also $2$. Note that $2$ $3$ $1$ $4$ or $2$ $4$ $1$ $3$ would be other acceptable answers.

Test case $2$: No four vertices satisfy the property.

Test case $3$: Note that $a = c$ for the output of this case, which is allowed.

见题面

见题面