#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5;
int i, dp[1<<15], j, x, y, z, n, m, xr, val[Nmax], cnt[20], ans;
vector<int> v;

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<n; ++i)
    {
        cin >> x >> y >> z;
        val[x] ^= z; val[y] ^= z;
    }

    for(i=0; i<n; ++i) cnt[val[i]]++;
    ans = cnt[0];
    for(i=1; i<=15; ++i)
    {
        ans += cnt[i] / 2;
        if(cnt[i] & 1) v.push_back(i);
    }

    m = v.size();
    if(m)
    {
        for(i=0; i<(1<<m); ++i)
        {
            xr = 0;
            for(j=0; j<m; ++j)
                if(i&(1<<j)) xr ^= v[j];

            if(!xr) dp[i] = 1;
                else
                {
                    dp[i] = -1e9;
                    continue;
                }

            for(j=i&(i-1); j; j = i&(j-1))
                dp[i] = max(dp[i], dp[j] + dp[i^j]);
        }
        ans += dp[i-1];
    }

    ans = n - ans;
    cout << ans << '\n';;

    return 0;
}

### Prompt

In CPP, your task is to solve 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>

using namespace std;

const int Nmax = 1e5 + 5;
int i, dp[1<<15], j, x, y, z, n, m, xr, val[Nmax], cnt[20], ans;
vector<int> v;

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<n; ++i)
    {
        cin >> x >> y >> z;
        val[x] ^= z; val[y] ^= z;
    }

    for(i=0; i<n; ++i) cnt[val[i]]++;
    ans = cnt[0];
    for(i=1; i<=15; ++i)
    {
        ans += cnt[i] / 2;
        if(cnt[i] & 1) v.push_back(i);
    }

    m = v.size();
    if(m)
    {
        for(i=0; i<(1<<m); ++i)
        {
            xr = 0;
            for(j=0; j<m; ++j)
                if(i&(1<<j)) xr ^= v[j];

            if(!xr) dp[i] = 1;
                else
                {
                    dp[i] = -1e9;
                    continue;
                }

            for(j=i&(i-1); j; j = i&(j-1))
                dp[i] = max(dp[i], dp[j] + dp[i^j]);
        }
        ans += dp[i-1];
    }

    ans = n - ans;
    cout << ans << '\n';;

    return 0;
}

```