Description

在边权树中，路径p的xor长度被定义为 路径p上边权的 ，⊕是xor运算符，表示异或。若一个路径有最大的xor长度，则该路径是xor最长的路径。给定n 个节点的边权树，找到xor最长的路径。

Format

Input

输入包含几个测试用例。每个测试用例的第1行都包含一个整数$n （1≤n ≤100000）$，表示节点数。以下$n -1$行，每行都包含三个整数$u 、v 、w$间的长度为$w$ 。

Output

对每个测试用例，都单行输出$xor$最长的路径长度。

Samples

4
0 1 3
1 2 4
1 3 6

7

来源

POJ3764