#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 100005;
const int R = 16;
const int _R = 1 << R;
int n, head[N], cnt[R], dp[_R], tot, x, y, z, ans;
struct edge { int to, nxt, cost; } e[N << 1];
void addedge(int x, int y, int z) {
	e[++tot] = (edge) { y, head[x], z }; head[x] = tot;
	e[++tot] = (edge) { x, head[y], z }; head[y] = tot;
}
void dfs(int x, int f = -1) {
	int v = 0; for (int i = head[x]; i; i = e[i].nxt) v ^= e[i].cost; cnt[v]++;
	for (int i = head[x]; i; i = e[i].nxt) if (e[i].to != f) dfs(e[i].to, x);
}
int main() {
	std::scanf("%d", &n);
	for (int i = 1; i < n; i++) std::scanf("%d%d%d", &x, &y, &z), addedge(x, y, z); 
	dfs(0);
	int v = 0;
	for (int i = 1; i < R; i++) ans += cnt[i] >> 1, cnt[i] &= 1, v |= cnt[i] << i;
	std::memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for (int i = 2; i < _R; i += 2) {
		int v = 0; for (int t = 0; t < 16; t++) if (i >> t & 1) v ^= t;
		if (v) continue;
		dp[i] = __builtin_popcount(i) - 1;
		for (int j = (i - 1) & i; j; j = (j - 1) & i)
			dp[i] = std::min(dp[i], dp[j] + dp[i - j]);
	}
	std::printf("%d\n", dp[v] + ans);
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

You are given a tree with N vertices. The vertices are numbered 0 through N-1, and the edges are numbered 1 through N-1. Edge i connects Vertex x_i and y_i, and has a value a_i. You can perform the following operation any number of times:

* Choose a simple path and a non-negative integer x, then for each edge e that belongs to the path, change a_e by executing a_e ← a_e ⊕ x (⊕ denotes XOR).



Your objective is to have a_e = 0 for all edges e. Find the minimum number of operations required to achieve it.

Constraints

* 2 ≤ N ≤ 10^5
* 0 ≤ x_i,y_i ≤ N-1
* 0 ≤ a_i ≤ 15
* The given graph is a tree.
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
x_1 y_1 a_1
x_2 y_2 a_2
:
x_{N-1} y_{N-1} a_{N-1}


Output

Find the minimum number of operations required to achieve the objective.

Examples

Input

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


Output

3


Input

2
1 0 0


Output

0

### Response

```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 100005;
const int R = 16;
const int _R = 1 << R;
int n, head[N], cnt[R], dp[_R], tot, x, y, z, ans;
struct edge { int to, nxt, cost; } e[N << 1];
void addedge(int x, int y, int z) {
	e[++tot] = (edge) { y, head[x], z }; head[x] = tot;
	e[++tot] = (edge) { x, head[y], z }; head[y] = tot;
}
void dfs(int x, int f = -1) {
	int v = 0; for (int i = head[x]; i; i = e[i].nxt) v ^= e[i].cost; cnt[v]++;
	for (int i = head[x]; i; i = e[i].nxt) if (e[i].to != f) dfs(e[i].to, x);
}
int main() {
	std::scanf("%d", &n);
	for (int i = 1; i < n; i++) std::scanf("%d%d%d", &x, &y, &z), addedge(x, y, z); 
	dfs(0);
	int v = 0;
	for (int i = 1; i < R; i++) ans += cnt[i] >> 1, cnt[i] &= 1, v |= cnt[i] << i;
	std::memset(dp, 0x3f, sizeof dp);
	dp[0] = 0;
	for (int i = 2; i < _R; i += 2) {
		int v = 0; for (int t = 0; t < 16; t++) if (i >> t & 1) v ^= t;
		if (v) continue;
		dp[i] = __builtin_popcount(i) - 1;
		for (int j = (i - 1) & i; j; j = (j - 1) & i)
			dp[i] = std::min(dp[i], dp[j] + dp[i - j]);
	}
	std::printf("%d\n", dp[v] + ans);
	return 0;
}
```