题目描述

给定一个树，树上的边都具有权值。

树中一条路径的异或长度被定义为路径上所有边的权值的异或和。

给定上述的具有 $n$ 个节点的树，你能找到异或长度最大的路径吗？

输入格式

第一行包含整数 $n$，表示树的节点数目。

接下来 $n-1$ 行，每行包括三个整数 $u, v, w$，表示节点 $u$ 和节点 $v$ 之间有一条边权重为 $w$。

输出格式

输出一个整数，表示异或长度最大的路径的最大异或和。

样例

输入样例：

4
0 1 3
1 2 4
1 3 6

输出样例：

7

样例解释

树的结构：

0 --(3)-- 1 --(4)-- 2
      |
     (6)
      |
      3

计算路径 0 → 1 → 2 的异或和：3 ⊕ 4 = 7，这是最大异或路径。

也可以验证其他路径：

• 0 → 1 → 3：3 ⊕ 6 = 5
• 2 → 1 → 3：4 ⊕ 6 = 2 等等。

最大为 7。

数据范围

• $1 \le n \le 100000$
• $0 \le u, v < n$
• $0 \le w < 2^{31}$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB