Description

给定一棵n个点的带权树，求树上最长的异或和路径。

Format

Input

多组数据。每组数据第一行一个整数n(1<=n<=100,000)。接下去n-1行每行三个整数：u(0<=u<n),v(0<=v<n),w(0<=w<2^31),表示u和v之间的长度为w的边。

Output

对于每组数据输出结果。

Sample 1

Input

4
1 2 3
2 3 4
2 4 6

Output

7

Limitation

1s, 64MiB for each test case.

Source

pku3764 bzoj1954