c8kbf and Tree CodeChef Solution

Problem

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=c or �≠�b=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 ��ui​, ��vi​, and ��wi​, denoting an edge between ��ui​ and ��vi​ with weight ��wi​. 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

Sample 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

1 4 2 3
-1
1 2 1 3

Explanation:

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.