题目描述

给一棵有 $N$ 个节点的树，节点编号从 $0$ 到 $N-1$， 树边编号从 $1$ 到 $N-1$。第 $i$ 条边连接节点 $x_i$ 和 $y_i$，其权值为 $a_i$。

你可以对树执行任意次操作，每次操作选取一条链和一个非负整数 $x$，将链上的边的权值与 $x$ 异或成为该边的新权值。

问最少需要多少次操作，使得所有边的权值都为 $0$。

输入格式

第一行有 $1$ 个整数，代表树的节点数 $N$。

接下来 $N-1$ 行，每行有 $3$ 个整数，第 $i+1$ 行上的整数分别代表第 $i$ 条边的参数 $x_i,y_i,a_i$。

输出格式

仅一行 $1$ 个整数，即最小操作数。

输入输出样例 #1

输入 #1

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

输出 #1

3

输入输出样例 #2

输入 #2

2
1 0 0

输出 #2

0

说明/提示

• $2\leq N \leq 10^5$
• $0\leq x_i,y_i \leq N-1$
• $0\leq a_i \leq 15$
• 保证给定的图是一棵树
• 保证输入数据都是整数