Problem Description

Given an undirected tree with $n$ vertices, each edge has a weight.

Let $V(x,y)$ and $E(x,y)$ represent the set of vertices and edges, respectively, on the simple path between vertices $x$ and $y$ in the tree. Specifically, when $x = y$, $V(x,y) = \{x\}$ and $E(x,y) = \varnothing$.

Define the value $f(E)$ of an edge set $E$ as the XOR sum of the weights of all edges in $E$. When $E = \varnothing$, $f(E) = 0$.

Your task is to find the maximum value of
$$ \max_{1\le x,y,u,v \le n, V(x,y) \cap V(u,v) = \varnothing} (f(E(x,y)) + f(E(u,v))) $$
In simpler terms, you need to select two simple paths that do not share any vertices and maximize the sum of their edge weight XOR sums.

Input Format

The first line contains an integer $n$, the number of vertices in the tree.

The next $n-1$ lines each contain three integers $x, y, w$, indicating an edge between vertex $x$ and vertex $y$ with weight $w$.

Output Format

Output a single integer, the answer to the problem.

Sample Input and Output

Sample Input #1

9
1 2 1
1 3 7
2 4 8
3 5 3
4 6 3
3 7 3
7 8 5
7 9 2

Sample Output #1

21

Sample Input #2

3
1 2 2
2 3 1

Sample Output #2

2

Notes

Sample 1 Explanation:

In the given tree, select the red and blue paths as shown, which do not overlap and maximize the sum of their edge weight XOR sums, which is $(7 \oplus 1 \oplus 8) + (5 \oplus 2) = 21$ (where $\oplus$ denotes the XOR operation).

Sample 2 Explanation:

In the given tree, which is a linear chain, select the red and blue paths as shown. The blue path degenerates into a single point, maximizing the XOR sum to $2 + 0 = 2$. Note that the red path cannot extend to vertex 3, otherwise, the blue path would not exist.

Data Range:

This problem is group-tested.

For $100\%$ of the data, $2 \leq n \leq 3 \times 10^4$, $1 \leq x, y \leq n$, $0 \leq w \leq 10^9$.

见题面 Input 部分

见题面 Output 部分