アナウンス

サンプル 3 に誤りがありました。答えは 15 ではなく 255 が正しいです。

問題文

$N$ 頂点の重み付き無向木が与えられます。 $i$ 番目の辺は頂点 $A_i$ と $B_i$ を相互に接続し、非負整数の重み $C_i$ が付いています。

木上のパス $P = (e_1, e_2, \ldots, e_m)$ に対して、 $f(P)$ を次のように定義します。

（ただし、 $x \oplus y$ を $x$ と $y$ のビットごとの XOR （排他的論理和）とします。）

この木上のあらゆる単純パス $P$ についての $\max f(P)$ を求めてください。

制約

• $1 \le N \le 10^5$
• $1 \le A_i , B_i \le N$
• $0 \le C_i \lt 2^{30}$
• 入力はすべて整数である
• 与えられる木の重みなし直径は $1000$ 以下である

入力

出力

答えを $1$ 行に出力せよ。

入出力例

5
1 3 1
2 3 2
3 4 4
4 5 8

14

$P = (2, 3, 4)$ とすると、パス上の XOR は $2 \oplus 4 \oplus 8 = 14$ となり、これが最大です。

8
1 6 32
2 4 16
4 3 8
4 5 4
5 1 2
7 4 64
8 1 1

102

12
10 4 174
11 8 47
2 12 171
4 6 158
2 1 218
6 8 84
6 9 121
4 5 26
6 3 136
6 2 216
7 4 80

255