#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
#define inc(i) (++ (i))
#define dec(i) (-- (i))
#define Rep(i , a , b) for(int i = (a) , i##Limit = (b) ; i <= i##Limit ; inc(i))
#define rep(i , a , b) for(int i = (a) , i##Limit = (b) ; i >= i##Limit ; dec(i))
#define Eep(i , u , v) for(int i = Head[u] , v = Node[i] ; i ; v = Node[i = Next[i]])
using namespace std;

const int N = 100000 + 7 , M = 16;
int n , tot[M] , Dp[(1 << 16) + 7] , W[N] , Sum[N];

int main() {
	int u , v , w , S = 0 , Ret = 0;
	scanf("%d" , &n);
	Rep(i , 2 , n) scanf("%d%d%d" , &u , &v , &w) , W[u + 1] ^= w , W[v + 1] ^= w;
	Rep(i , 1 , n) inc(tot[W[i]]);
	Rep(i , 1 , 15) Ret += tot[i] / 2 , S |= (tot[i] & 1) << i;
	Rep(i , 1 , (1 << 16) - 1) Dp[i] = Dp[i >> 1] + (i & 1);
	Rep(i , 1 , (1 << 16) - 1) Dp[i] -= 1;
	Rep(i , 1 , (1 << 16) - 1)
		Rep(j , 0 , 15) if((i >> j) & 1) Sum[i] ^= j;
	Rep(i , 1 , (1 << 16) - 1) if(!Sum[i]) {
		for(int k = i & (i - 1) ; k ; k = (k - 1) & i)
			if(!Sum[k]) Dp[i] = min(Dp[i] , Dp[i ^ k] + Dp[k]);
	}
	printf("%d" , Ret + Dp[S]);
	return 0;
}
### Prompt

Create a solution in cpp for 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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
#define inc(i) (++ (i))
#define dec(i) (-- (i))
#define Rep(i , a , b) for(int i = (a) , i##Limit = (b) ; i <= i##Limit ; inc(i))
#define rep(i , a , b) for(int i = (a) , i##Limit = (b) ; i >= i##Limit ; dec(i))
#define Eep(i , u , v) for(int i = Head[u] , v = Node[i] ; i ; v = Node[i = Next[i]])
using namespace std;

const int N = 100000 + 7 , M = 16;
int n , tot[M] , Dp[(1 << 16) + 7] , W[N] , Sum[N];

int main() {
	int u , v , w , S = 0 , Ret = 0;
	scanf("%d" , &n);
	Rep(i , 2 , n) scanf("%d%d%d" , &u , &v , &w) , W[u + 1] ^= w , W[v + 1] ^= w;
	Rep(i , 1 , n) inc(tot[W[i]]);
	Rep(i , 1 , 15) Ret += tot[i] / 2 , S |= (tot[i] & 1) << i;
	Rep(i , 1 , (1 << 16) - 1) Dp[i] = Dp[i >> 1] + (i & 1);
	Rep(i , 1 , (1 << 16) - 1) Dp[i] -= 1;
	Rep(i , 1 , (1 << 16) - 1)
		Rep(j , 0 , 15) if((i >> j) & 1) Sum[i] ^= j;
	Rep(i , 1 , (1 << 16) - 1) if(!Sum[i]) {
		for(int k = i & (i - 1) ; k ; k = (k - 1) & i)
			if(!Sum[k]) Dp[i] = min(Dp[i] , Dp[i ^ k] + Dp[k]);
	}
	printf("%d" , Ret + Dp[S]);
	return 0;
}
```