题目描述

给定一棵 $n$ 个点的带权树，结点下标从 $1$ 开始到 $n$。寻找树中找两个结点，求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入格式

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

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

输出格式

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

样例

4
1 2 3
2 3 4
2 4 6

7

说明/提示

样例解释

最长异或序列是 $1,2,3$，答案是 $7=3\oplus 4$。

数据范围与约定

• 对于 $30\%$ 的数据，$n \le 1000$
• 对于 $100\%$ 的数据，$1 \le n \le 10^5; 1 \le u,v \le n; 0 \le w \lt 2^{31}$