#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
using namespace std;

const int maxn = 100005;
const int inf = 1e9;
int a[maxn], c[16], f[1<<16], ins[1<<16];
int n, x, y, z, ans, now;

int solve(int s) {
	if (!(s >> 1)) return 0;
	if (ins[s]) return inf;
	if (f[s] != -1) return f[s];
	f[s] = inf; ins[s] = 1;
	rep (i, 1, 15) if (s >> i & 1)
		rep (j, 1, 15) if (i != j)
			f[s] = min(f[s], solve(s ^ (1 << i) ^ (1 << j)
			^ (1 << (i ^ j)) | 1) + 1 + ((s >> (i ^ j)) & 1));
	ins[s] = 0;
	//printf("%d %d\n", s, f[s]);
	return f[s];
}

int main() {
	scanf("%d", &n);
	rep (i, 2, n) {
		scanf("%d%d%d", &x, &y, &z);
		a[x+1] ^= z; a[y+1] ^= z;
	}
	rep (i, 1, n) c[a[i]]++;
	rep (i, 1, 15) {
		ans += c[i] / 2;
		c[i] &= 1;
		now |= c[i] << i;
	}
	memset(f, -1, sizeof f);
	printf("%d\n", ans + solve(now | 1));
	return 0;
}

### Prompt

Generate a cpp solution to the following problem:

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<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
using namespace std;

const int maxn = 100005;
const int inf = 1e9;
int a[maxn], c[16], f[1<<16], ins[1<<16];
int n, x, y, z, ans, now;

int solve(int s) {
	if (!(s >> 1)) return 0;
	if (ins[s]) return inf;
	if (f[s] != -1) return f[s];
	f[s] = inf; ins[s] = 1;
	rep (i, 1, 15) if (s >> i & 1)
		rep (j, 1, 15) if (i != j)
			f[s] = min(f[s], solve(s ^ (1 << i) ^ (1 << j)
			^ (1 << (i ^ j)) | 1) + 1 + ((s >> (i ^ j)) & 1));
	ins[s] = 0;
	//printf("%d %d\n", s, f[s]);
	return f[s];
}

int main() {
	scanf("%d", &n);
	rep (i, 2, n) {
		scanf("%d%d%d", &x, &y, &z);
		a[x+1] ^= z; a[y+1] ^= z;
	}
	rep (i, 1, n) c[a[i]]++;
	rep (i, 1, 15) {
		ans += c[i] / 2;
		c[i] &= 1;
		now |= c[i] << i;
	}
	memset(f, -1, sizeof f);
	printf("%d\n", ans + solve(now | 1));
	return 0;
}

```