题目背景

苍岭之间散落着若干座哨站，哨站之间由驿道相连，任何两座哨站之间恰有一条不重复走驿道的通路。每条驿道上都刻着一个印记值。巡线人常用一条通路上的印记值互相异或，异或结果为 $0$ 的通路被认为"无痕"，是他最爱走的路。

题目描述

给定一棵 $n$ 个结点的树，每条边有一个非负整数权值。对于两个不同的结点 $u, v$，取它们之间唯一的简单路径，将路径上所有边的权值按位异或起来；若结果为 $0$，则称这条路径是无痕路径。

请求出树中无痕路径的条数。$(u, v)$ 与 $(v, u)$ 视为同一条路径。

输入格式

第一行一个整数 $n$。

接下来 $n - 1$ 行，每行三个整数 $u, v, w$，表示结点 $u$ 与 $v$ 之间有一条权值为 $w$ 的边。

输出格式

一行一个整数，表示无痕路径的条数。

输入输出样例 #1

输入 #1

3
1 2 5
2 3 5

输出 #1

1

输入输出样例 #2

输入 #2

4
1 2 1
1 3 1
1 4 2

输出 #2

1

输入输出样例 #3

输入 #3

2
1 2 0

输出 #3

1

说明

样例解释

样例 1：三条路径中，$1 \to 2$ 的异或值为 $5$，$2 \to 3$ 的异或值为 $5$，$1 \to 2 \to 3$ 的异或值为 $5 \oplus 5 = 0$，故答案为 $1$。

样例 2：路径 $1 \to 2$、$1 \to 3$、$1 \to 4$、$2 \to 3$、$2 \to 4$、$3 \to 4$ 的异或值依次为 $1, 1, 2, 0, 3, 3$，只有 $2 \to 3$ 的异或值为 $0$，故答案为 $1$。

样例 3：两点之间只有一条边，权值为 $0$，故答案为 $1$。

数据范围

• 对于 $30\%$ 的数据，$1 \le n \le 100$；
• 对于 $60\%$ 的数据，$1 \le n \le 5000$；
• 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^{5}$，$0 \le w < 2^{30}$。