题目描述

给定一棵包含 $N$ 个顶点的树。这些顶点从 $0$ 到 $N-1$ 进行编号，边从 $1$ 到 $N-1$ 进行编号。边 $i$ 连接了顶点 $x_i$ 和 $y_i$，并且有一个值 $a_i$。你可以执行以下操作任意次数:

• 选择一条简单路径和一个非负整数 $x$，然后对路径上的每条边执行 $a_e ← a_e ⊕ x$（⊕ 表示异或）。

你的目标是使得所有边的 $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$ 的路径，并选择 $x = 1$。
• 然后，选择连接顶点 $2$ 和顶点 $3$ 的路径，并选择 $x = 2$。
• 最后，选择连接顶点 $0$ 和顶点 $4$ 的路径，并选择 $x = 4$。

示例输入 2

2
1 0 0

示例输出 2

0