题目描述

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

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

$\red { _{xor} length(p) = \bigoplus _ {e\in p} w(e) }$

$\red \bigoplus$为异或符号。

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

输入格式

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

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

输出格式

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

样例

输入样例

4
0 1 3
1 2 4
1 3 6

输出样例

7

提示

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