nodgd有一个 \(N\) 个节点的树，节点编号 $0\sim N-1$ ，树边编号 $1\sim N-1$ 。第 \(i\) 条边连接节点 \(x_i,y_i\) ，权值为 \(a_i\) 。

nodgd每次可以在树上进行这样的操作：选一条链和一个非负整数 \(x\) ，将链上每条边的权值都异或 \(x\) 得到该边的新权值。

nodgd想知道，最少需要多少次操作，才能将所有边的权值都变成 $0$ ？

第一行一个整数 \(N\) 。
接下来 \(N-1\) 行，每行三个整数 \(x_i,y_i,a_i\) 表示一条边。

输出一个整数答案。

数据范围

$2\leq N\leq 10^5$
$0\leq x_i,y_i\leq N-1$
$0\leq a_i\leq 15$

对于40%的数据， \(N\leq 16\)

样例 1

样例输入
5
0 1 1
0 2 3
0 3 6
3 4 4

样例输出
3

方法有多种，例如：
第一次将节点 $1$ 到节点 $2$ 的每条边都异或 $1$ ；
第二次将节点 $2$ 到节点 $3$ 的每条边都异或 $2$ ；
第三次将节点 $0$ 到节点 $4$ 的每条边都异或 $4$ 。

样例 2

样例输入
2
1 0 0

样例输出
0