给定一棵包含 $N$ 个顶点的树。顶点编号为 $0$ 到 $N-1$，边编号为 $1$ 到 $N-1$。第 $i$ 条边连接顶点 $x_i$ 和 $y_i$，并具有一个权值 $a_i$。你可以执行任意次数的以下操作：选择一条简单路径和一个非负整数 $x$，然后对于路径上的每一条边 $e$，通过执行 $a_e := a_e \oplus x$ 来改变 $a_e$（其中 $\oplus$ 表示异或运算）。

你的目标是使所有边 $e$ 的 $a_e = 0$。求实现该目标所需的最少操作次数。

输入格式

输入按以下格式给出：

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

数据范围： $2 \le N \le 10^5$，$0 \le x_i, y_i \le N-1$，$0 \le a_i \le 15$。给定图为一棵树，所有输入值均为整数。

输出格式

输出实现目标所需的最少操作次数。

样例

输入格式 1

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

输出格式 1

3

输入格式 2

2
1 0 0

输出格式 2

0

说明

在样例 1 中，可以通过三次操作实现目标，过程如下：首先，选择连接顶点 $1, 2$ 的路径，取 $x = 1$；然后，选择连接顶点 $2, 3$ 的路径，取 $x = 2$；最后，选择连接顶点 $0, 4$ 的路径，取 $x = 4$。