题目描述

给定一棵 $n$ 个点的无根树，边有边权。

令 $V(x,y),E(x,y)$ 分别表示树上 $x,y$ 之间的简单路径上的所有点的集合和所有边的集合，特别地，当 $x=y$ 时，$V(x,y) = \{x\}$，$E(x,y) = \varnothing$。

再令边集 $E$ 的权值 $f(E)$ 为 $E$ 中所有边的权值的 异或和，当 $E = \varnothing$ 时，$f(E) = 0$。

现在，要你求出

$$\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))) $$

通俗的讲，你要选择两条简单路径，满足没有重合的点，且边权异或和之和最大。

输入格式

第一行一个整数 $n$，表示树上点的个数。

接下来 $n-1$ 行，每行三个整数 $x,y,w$，表示编号为 $x$ 和 $y$ 的点之间有一条权值为 $w$ 的边。

输出格式

一行一个整数，表示答案。

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

提示

【样例 1 解释】

样例中的树如图所示，选择标红色和蓝色的两条路径，满足没有重合的点，且边权异或和之和最大，为 $(7\oplus 1\oplus 8)+(5\oplus 2)=21$（其中 $\oplus$ 表示异或运算）。

【样例 2 解释】

样例中的树如图所示，为一条链的形状，选择标红色和蓝色的两条路径，蓝色路径退化成了一个点，使异或和之和达到最大值 $2+0=2$。注意红色路径并不能延申到 $3$，否则蓝色路径将无法存在。

---

【数据范围】

本题采用捆绑测试。

子任务编号	$n\leq$	特殊性质	分值	时限
1	$50$	无	12	1s
2	$2\times 10^3$		28	2s
3	$2\times 10^4$	$y = x + 1$	20	3s
4	$3\times 10^4$	无	40	3.5s

对于 $100\%$ 的数据，$2\leq n\leq 3\times 10^4$，$1\leq x,y\leq n$，$0\leq w\leq 10^9$。