Description

You are given an undirected tree with $n$ nodes, and each edge has a weight.

Let $V(x,y)$ and $E(x,y)$ denote the set of all nodes and the set of all edges on the simple path between $x$ and $y$ in the tree. In particular, when $x=y$, $V(x,y)=\{x\}$ and $E(x,y)=\varnothing$.

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

Now, you need to compute

$$\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 plain words, you need to choose two simple paths such that they do not share any common nodes, and the sum of their edge-weight XOR values is as large as possible.

Input Format

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

The next $n-1$ lines each contain three integers $x,y,w$, indicating that there is an edge of weight $w$ between nodes $x$ and $y$.

Output Format

Output one integer on a single line, the answer.

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

21

3
1 2 2
2 3 1

2

Hint

[Sample 1 Explanation]

The tree in the sample is shown in the figure. Choose the two paths marked in red and blue. They have no common nodes, and the sum of XOR values is maximized, which is $(7\oplus 1\oplus 8)+(5\oplus 2)=21$ (where $\oplus$ denotes the XOR operation).

[Sample 2 Explanation]

The tree in the sample is shown in the figure. It is a chain. Choose the red and blue paths; the blue path degenerates into a single node, making the maximum sum of XOR values $2+0=2$. Note that the red path cannot be extended to $3$, otherwise the blue path would not be possible.

---

[Constraints]

This problem uses bundled testdata.

Subtask ID	$n\leq$	Special Property	Score	Time Limit
1	$50$	None	12	1s
2	$2\times 10^3$		28	2s
3	$2\times 10^4$	$y = x + 1$	20	3s
4	$3\times 10^4$	None	40	3.5s

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

Input Format

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

The next $n-1$ lines each contain three integers $x,y,w$, indicating that there is an edge of weight $w$ between nodes $x$ and $y$.

Output Format

Output one integer on a single line, the answer.

Hint

[Sample 1 Explanation]

The tree in the sample is shown in the figure. Choose the two paths marked in red and blue. They have no common nodes, and the sum of XOR values is maximized, which is $(7\oplus 1\oplus 8)+(5\oplus 2)=21$ (where $\oplus$ denotes the XOR operation).

[Sample 2 Explanation]

The tree in the sample is shown in the figure. It is a chain. Choose the red and blue paths; the blue path degenerates into a single node, making the maximum sum of XOR values $2+0=2$. Note that the red path cannot be extended to $3$, otherwise the blue path would not be possible.

---

[Constraints]

This problem uses bundled testdata.

Subtask ID	$n\leq$	Special Property	Score	Time Limit
1	$50$	None	12	1s
2	$2\times 10^3$		28	2s
3	$2\times 10^4$	$y = x + 1$	20	3s
4	$3\times 10^4$	None	40	3.5s

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

Translated by ChatGPT 5