Description

Given a weighted tree with $n$ nodes, indexed from $1$ to $n$. Find the maximum value among the XOR of all paths in the tree.

An XOR path is the XOR of all edge weights along the unique path between two nodes in the tree.

Constraints $1 \le n \le 10^5; 0 < u, v \le n; 0 \le w < 2^{31}$.

Input Format

The first line contains an integer $n$, the number of nodes.

The next $n-1$ lines each contain $u, v, w$, meaning there is an edge between node $u$ and node $v$ with weight $w$.

Output Format

One line with a single integer, the answer.

4
1 2 3
2 3 4
2 4 6

7

Hint

When the two nodes are $1$ and $3$, the value is $7=3\oplus 4$, which is the maximum.

Translated by ChatGPT 5