Description

Original problem from: POJ 3764

Given a weighted tree with $n$ nodes, find the longest XOR path on the tree.

Input Format

The first line contains an integer $n$. The next $n-1$ lines each contain three integers $u, v, w$, indicating an edge between $u$ and $v$ with length $w$.

Output Format

Output a single integer representing the answer.

Sample 1

The longest XOR path is $1\to 2\to 3$, with a length of $3 \bigoplus 4=7$.

Note: Node indices range from $1$ to $N$.

Note: $x \bigoplus y$ denotes the bitwise XOR of $x$ and $y$.

4
1 2 3
2 3 4
2 4 6

7

Constraints & Hints

For $100\%$ of the data, $1\le n\le 10^5,1\le u, v \le n,0 \le w < 2^{31}$