题目描述

给定一棵 $n$ 个点的带权树，结点下标从 $1$ 开始到 $n$。树上两点之间路径 $p$ 的异或长度指的是路径 $p$ 上所有权值的异或和，即：

其中 $\oplus$ 表示异或运算。

请你寻找树中所有路径的异或长度的最大值。

输入格式

第一行一个整数 $n$，表示点数。

接下来 $n-1$ 行，给出 $u,v,w$ ，分别表示树上的 $u$ 点和 $v$ 点有连边，边的权值是 $w$。

输出格式

一行，一个整数表示答案。

样例 #1

样例输入 #1

4
1 2 3
2 3 4
2 4 6

样例输出 #1

7

提示

最长异或路径是 $\{1,2,3\}$，答案是 $7=3\oplus 4$。

数据范围

• $1\le n \le 100000$

• $0 < u,v \le n$

• $0 \le w < 2^{31}$