#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

const int N = 100005;

int n, b[N], up[N], dt[1<<15], ans;

vector<int> er;
vector<pii> adj[N];

void calc (int C, int P) {
	int X = 0;
	for(auto &T : adj[C]) {
		int A, B;
		tie(A, B) = T;
		if(A == P) continue;
		up[A] = B;
		calc(A, C);
		X ^= B;
	}
	if(C && (X^up[C])) {
		X ^= up[C];
		if(b[X]) b[X] = 0;
		else {
			b[X] = 1;
			ans++;
		}
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		int A, B, C;
		scanf("%d%d%d",&A,&B,&C);
		adj[A].push_back({B, C});
		adj[B].push_back({A, C});
	}
	calc(0, -1);
	int X = 0;
	for(int i=0;i<15;i++) {
		if(b[i+1]) X += (1<<i);
	}
	for(int i=1;i<=X;i++) {
		int T = 0;
		for(int j=0;j<15;j++) {
			if(i&(1<<j)) T ^= j+1;
		}
		if(!T) er.push_back(i);
		for(auto &T : er) {
			if((T&i)==T) dt[i] = max(dt[i], dt[i-T]+1);
		}
	}
	printf("%d\n", ans - dt[X]);
}

### Prompt

Develop a solution in cpp 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<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

const int N = 100005;

int n, b[N], up[N], dt[1<<15], ans;

vector<int> er;
vector<pii> adj[N];

void calc (int C, int P) {
	int X = 0;
	for(auto &T : adj[C]) {
		int A, B;
		tie(A, B) = T;
		if(A == P) continue;
		up[A] = B;
		calc(A, C);
		X ^= B;
	}
	if(C && (X^up[C])) {
		X ^= up[C];
		if(b[X]) b[X] = 0;
		else {
			b[X] = 1;
			ans++;
		}
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		int A, B, C;
		scanf("%d%d%d",&A,&B,&C);
		adj[A].push_back({B, C});
		adj[B].push_back({A, C});
	}
	calc(0, -1);
	int X = 0;
	for(int i=0;i<15;i++) {
		if(b[i+1]) X += (1<<i);
	}
	for(int i=1;i<=X;i++) {
		int T = 0;
		for(int j=0;j<15;j++) {
			if(i&(1<<j)) T ^= j+1;
		}
		if(!T) er.push_back(i);
		for(auto &T : er) {
			if((T&i)==T) dt[i] = max(dt[i], dt[i-T]+1);
		}
	}
	printf("%d\n", ans - dt[X]);
}

```