问题描述

给定一棵 n 个结点的树，结点编号为 1 ~ n。（注：此处点的编号与 POJ3764 不同。）树上的边都具有权值。

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

你能找到异或长度最大的路径吗？你只需要输出最大的异或长度。

输入格式

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

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

输出格式

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

数据范围

1 ≤ n ≤ 100000, 1 ≤ u, v ≤ n, 0 ≤ w < 2^31

输入样例

4
1 2 3
2 3 4
2 4 6

输出样例

7

样例解释

样例中最长异或路径应为 1 -> 2 -> 3，值为 7(=3⊕4)。