#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

int n, cnt[16], ans, now, f[101000], g[77777];
vector<pii>vec;
void U(int &x,int y){ x=min(x,y); }

int main(){
  memset(g,33,sizeof g); g[0]=0;
  for (int i=2;i<(1<<16);i+=2){
    int x=0, c=-1;
    for (int j=1;j<16;++j)
      if (i>>j&1)
        x^=j, ++c;
    if (!x) vec.push_back((pii){i,c});
  }
  
  for (int i=0;i<16;++i)
    for (int x=0;x<(1<<16);x+=2) if (g[x]==i){
      for (auto o:vec)
        U(g[x^o.fi],i+o.se);
    }
  
  cin>>n;
  int x, y, z;
  for (int i=1;i<n;++i){
    scanf("%d%d%d",&x,&y,&z); f[++x]^=z; f[++y]^=z;
  }
  for (int i=1;i<=n;++i) ++cnt[f[i]];
  for (int i=1;i<16;++i){
    ans+=cnt[i]>>1;
    now|=(cnt[i]&1)<<i;
  }
  cout<<ans+g[now];
}
### 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<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

int n, cnt[16], ans, now, f[101000], g[77777];
vector<pii>vec;
void U(int &x,int y){ x=min(x,y); }

int main(){
  memset(g,33,sizeof g); g[0]=0;
  for (int i=2;i<(1<<16);i+=2){
    int x=0, c=-1;
    for (int j=1;j<16;++j)
      if (i>>j&1)
        x^=j, ++c;
    if (!x) vec.push_back((pii){i,c});
  }
  
  for (int i=0;i<16;++i)
    for (int x=0;x<(1<<16);x+=2) if (g[x]==i){
      for (auto o:vec)
        U(g[x^o.fi],i+o.se);
    }
  
  cin>>n;
  int x, y, z;
  for (int i=1;i<n;++i){
    scanf("%d%d%d",&x,&y,&z); f[++x]^=z; f[++y]^=z;
  }
  for (int i=1;i<=n;++i) ++cnt[f[i]];
  for (int i=1;i<16;++i){
    ans+=cnt[i]>>1;
    now|=(cnt[i]&1)<<i;
  }
  cout<<ans+g[now];
}
```