問題文

$N$ 頂点の木が与えられます。頂点には $0$ から $N-1$ の番号がついています。 辺は $1$ から $N-1$ までの番号がついていて、辺 $i$ は頂点 $x_i$ と $y_i$ をつなぎ、また $a_i$ という値を保持しています。 あなたは以下の操作を何回でもすることが出来ます:

• ある単純pathとある非負整数 $x$ を選び、そのpathを構成する各辺 $e$ について、 $a_e ← a_e ⊕ x$ (⊕ は xor)と変化させる。

目標はすべての辺 $e$ について $a_e = 0$ とすることです。 目標を達成するために必要な最小の操作回数を求めてください。

制約

• $2 ≤ N ≤ 10^5$
• $0 ≤ x_i,y_i ≤ N-1$
• $0 ≤ a_i ≤ 15$
• 与えられるグラフは木
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $y_1$ $a_1$ $x_2$ $y_2$ $a_2$ $:$ $x_{N-1}$ $y_{N-1}$ $a_{N-1}$

出力

目標を達成するために必要な操作回数の最小値を出力せよ。

入力例 1

5
0 1 1
0 2 3
0 3 6
3 4 4

出力例 1

3

以下のようにして三回で目標を達成できます。

• まず、頂点 $1,2$ を結ぶ path に対して $x=1$ で操作する
• 次に、頂点 $2,3$ を結ぶ path に対して $x=2$ で操作する
• 最後に、頂点 $0,4$ を結ぶ path に対して $x=4$ で操作する

入力例 2

2
1 0 0

出力例 2

0