题目描述

给定一棵有 $n$ 个结点的带权树，结点编号从 $1$ 到 $n$。求树中所有异或路径的最大值。

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

输入格式

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

接下来 $n-1$ 行，每行三个整数 $u, v, w$，表示结点 $u$ 和结点 $v$ 之间有一条边，边权为 $w$。

输出格式

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

样例

4
1 2 3
2 3 4
2 4 6

7

提示

当两个结点分别是 $1, 3$ 时，答案是 $7 = 3 \oplus 4$，取最大值。

数据范围

$1 \le n \le 10^5$；$0 \lt u, v \le n$；$0 \le w \lt 2^{31}$。