stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

const int N = 100010;

int n, val[N], res, cnt[20], Get, dp[1 << 17], st[20];

bool check(int s)

{

	int cnt = 0;

	while(s)

	{

		int t = s & 1;

		s >>= 1;

		if(st[cnt] == 0 && t) return false;

		cnt ++;

	}

	return true;

}

int Solve(int s)

{

	if(s == 0) return 0;

	if(dp[s] != 0x3f3f3f3f) return dp[s];

	for(int i=1;i<=15;i++)

	{

		for(int j=i+1;j<=15;j++)

		{

			if((s >> i & 1) && (s >> j & 1))

			{

				int t = i ^ j;

				int p = s ^ (1 << i) ^ (1 << j) ^ (1 << t);

				if(s >> t & 1) dp[s] = std:: min(dp[s], Solve(p) + 2);

				else dp[s] = std:: min(dp[s], Solve(p) + 1);

			}

		}

	}

	return dp[s];

}

int main() 

{

	scanf("%d", &n);

	for(int i=1;i<n;i++)

	{

		int u, v, w;

		scanf("%d%d%d", &u, &v, &w);

		val[u] ^= w; val[v] ^= w; 

	}

	for(int i=0;i<n;i++) cnt[val[i]] ++;

	for(int i=1;i<=15;i++) 

	{

		res += cnt[i] / 2;

		if(cnt[i] & 1) Get |= (1 << i), st[i] = 1;

	}

	memset(dp, 0x3f3f3f3f, sizeof(dp));

	printf("%d\n", res + Solve(Get));

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<ctime>

#define INF 1e9

using namespace std;

const int maxn=100010;

const double Pi=acos(-1.0);

template<class T>void read(T &x)

{

	x=0;int f=0;char ch=getchar();

	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}

	x=f?-x:x;

	return;

}

int n,num[maxn],book[21],s;

int f[(1<<17)+10],ans;

int dp(int s)

{

	if(!s)

		return 0;

	if(f[s])

		return f[s];

	f[s]=INF;

	for(int i=1;i<=15;i++)

	{

		if(!(s&(1<<i)))

			continue;

		for(int j=1;j<=15;j++)

		{

			if(i==j||!(s&(1<<j)))

				continue;

			int k=i^j;

			int t=s^(1<<i)^(1<<j)^(1<<k);

			if(s&(1<<k))

				f[s]=min(f[s],dp(t)+2);

			else

				f[s]=min(f[s],dp(t)+1);

		}

	}

	return f[s];

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<n;i++)

	{

		int a,b,c;

		scanf("%d%d%d",&a,&b,&c);

		num[a]^=c;

		num[b]^=c;

	}

	for(int i=0;i<n;i++)

		book[num[i]]++;

	for(int i=1;i<=15;i++)

	{

		ans+=(book[i]>>1);

		s|=((book[i]&1)<<i);//奇数最后剩下

	}

	printf("%d",ans+dp(s));

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

  mail: mleautomaton@foxmail.com

  author: MLEAutoMaton

  This Code is made by MLEAutoMaton

*/

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<iostream>

using namespace std;

#define ll long long

#define re register

#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)

inline int gi(){

	int f=1,sum=0;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=200010,M=20,Inf=2e9;

int n,a[N],cnt[M],ans,f[1<<M];

void chkmin(int &x,int y){x=min(x,y);}

int main(){

	n=gi();

	for(int i=1;i<n;i++){

		int u=gi()+1,v=gi()+1,w=gi();

		a[u]^=w;a[v]^=w;

	}

	int now=0;

	for(int i=1;i<=n;i++)cnt[a[i]]++;

	for(int i=1;i<=15;i++){ans+=cnt[i]/2;cnt[i]&=1;now+=cnt[i]<<(i-1);}

	memset(f,127,sizeof(f));f[now]=0;

	for(int i=(1<<15)-1;i;i--)

		if(f[i]<Inf)

			for(int j=1;j<=15;j++)

				if(i&(1<<j-1))

					for(int k=1;k<=15;k++)

						if(i&(1<<k-1) && j!=k){

							int x=j^k;

							if(i&(1<<x-1))chkmin(f[i-(1<<j-1)-(1<<k-1)-(1<<x-1)],f[i]+2);

							else chkmin(f[i-(1<<j-1)-(1<<k-1)+(1<<x-1)],f[i]+1);

						}

	printf("%d\n",f[0]+ans);

	return 0;

}


// Optimized solution to the same problem (faster):
#pragma GCC optimize("Ofast,unroll-loops")

#include<bits/stdc++.h>

#define ll long long

#define F first

#define S second

#define P pair

#define FOR(i,a,b) for(int i=a;i<=b;i++)

#define rep(i,a,b) for(int i=a;i<b;i++) 

#define V vector

#define RE return

#define ALL(a) a.begin(),a.end()

#define MP make_pair

#define PB push_back

#define PF push_front

#define FILL(a,b) memset(a,b,sizeof(a))

using namespace std;

int c[16],n,v[200005],dp[1<<16];

int dfs(int x){

	if(dp[x]!=-1)RE dp[x];

	int re=1000000000;

	rep(i,1,16){

		if(x&(1<<i)){

			rep(j,i+1,16){

				if(x&(1<<j)){

					re=min(re,dfs(x^(1<<i)^(1<<j)^(1<<(i^j)))+((x&(1<<(i^j)))?2:1));

				}

			}

			break;

		}

	}

	RE dp[x]=re;

}

int main(){

	ios::sync_with_stdio(0);

    cin.tie(0);

	cin>>n;

	int x,y,z;

	rep(i,1,n){

		cin>>x>>y>>z;

		v[x]^=z;v[y]^=z;

	}

	int ans=0;

	rep(i,0,n){

		c[v[i]]++;

	}

	FOR(i,1,15){

		ans+=c[i]/2;

		c[i]&=1;

	}

	int get=0;

	FILL(dp,-1);dp[0]=0;

	FOR(i,1,15)if(c[i])get^=(1<<i);

	cout<<dfs(get)+ans;

	RE 0;

}






// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int n;

const int N=100010,M=16;

int s[N],cnt[M],ans,f[1000010];

void chkmin(int &x,int y)

{

	if(y<x)x=y;

}

int main()

{

	scanf("%d",&n);

	int u,v,w;

	for(int i=1;i<n;i++)

		scanf("%d%d%d",&u,&v,&w),s[u]^=w,s[v]^=w;

	for(int i=0;i<n;i++)

		cnt[s[i]]++;

	int now=0;

	for(int i=1;i<16;i++)

		ans+=cnt[i]/2,now+=((cnt[i]&1)<<i-1);

	memset(f,127,sizeof(f)); f[now]=0;

	for(int i=(1<<15)-1;i;i--)

		if(f[i]<2000000000)

		{

			for(int j=1;j<=15;j++)

				if(i&(1<<j-1))

					for(int k=1;k<=15;k++)

						if(i&(1<<k-1) && j!=k)

						{

							int l=j^k;

							if(i&(1<<l-1))

								chkmin(f[i-(1<<j-1)-(1<<k-1)-(1<<l-1)],f[i]+2);

							else

								chkmin(f[i-(1<<j-1)-(1<<k-1)+(1<<l-1)],f[i]+1);

						}

		}

	printf("%d\n",f[0]+ans);

	return 0;

}


// Optimized solution to the same problem (faster):
#pragma GCC optimize("Ofast,unroll-loops")

#include<bits/stdc++.h>

#define ll long long

#define F first

#define S second

#define P pair

#define FOR(i,a,b) for(int i=a;i<=b;i++)

#define rep(i,a,b) for(int i=a;i<b;i++) 

#define V vector

#define RE return

#define ALL(a) a.begin(),a.end()

#define MP make_pair

#define PB push_back

#define PF push_front

#define FILL(a,b) memset(a,b,sizeof(a))

using namespace std;

int c[16],n,v[200005],dp[1<<16];

int dfs(int x){

	if(dp[x]!=-1)RE dp[x];

	int re=1000000000;

	rep(i,1,16){

		if(x&(1<<i)){

			rep(j,i+1,16){

				if(x&(1<<j)){

					re=min(re,dfs(x^(1<<i)^(1<<j)^(1<<(i^j)))+((x&(1<<(i^j)))?2:1));

				}

			}

			break;

		}

	}

	RE dp[x]=re;

}

int main(){

	ios::sync_with_stdio(0);

    cin.tie(0);

	cin>>n;

	int x,y,z;

	rep(i,1,n){

		cin>>x>>y>>z;

		v[x]^=z;v[y]^=z;

	}

	int ans=0;

	rep(i,0,n){

		c[v[i]]++;

	}

	FOR(i,1,15){

		ans+=c[i]/2;

		c[i]&=1;

	}

	int get=0;

	FILL(dp,-1);dp[0]=0;

	FOR(i,1,15)if(c[i])get^=(1<<i);

	cout<<dfs(get)+ans;

	RE 0;

}






// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>



#define ed end

#define bg begin

#define fr first

#define sc second

#define il inline

#define LL long long

#define pb push_back

#define mk make_pair

#define to(k) E[k].to

#define val(k) E[k].val

#define next(k) E[k].next

#define pint pair<int, int>



#define MAXN 400010

#define MAXS 400100

#define Inf 998244353



using namespace std ;

struct Edge{

	int to, next, val ;

}E[MAXN << 1] ; int head[MAXN], cnt, sz[MAXS] ; 

int N, vals[MAXN], dp[MAXN], ctn[MAXN], now_st, ans ; 



void add(int u, int v, int w){

	E[++ cnt].to = v, E[cnt].val = w,

	E[cnt].next = head[u], head[u] = cnt ;

	E[++ cnt].to = u, E[cnt].val = w,

	E[cnt].next = head[v], head[v] = cnt ;

}

int do_do(int stt){

	if (!stt) return 0 ;

	if (dp[stt] != -1) return dp[stt] ;

	int ret = Inf ;

	for (int i = 1 ; i <= 15 ; ++ i){

		if (!(stt >> i & 1)) continue ;

		for (int j = 1 ; j <= 15 ; ++ j){

			if (i == j || !(stt >> j & 1)) continue ;

			int now_st = stt ^ (1 << i) ^ (1 << j) ;

			int q = i ^ j ; now_st ^= (1 << q) ; 

			if (sz[now_st] < sz[stt]) ret = min(ret, do_do(now_st) + 1 + (~now_st >> (q) & 1)) ; 

		}

	}

	return dp[stt] = ret ; 

}

int main(){

	cin >> N ; 

	int u, v, w, i ; 

	memset(dp, -1, sizeof(dp)) ;

	for (i = 1 ; i < N ; ++ i) 

		scanf("%d%d%d", &u, &v, &w), 

		add(u + 1, v + 1, w), vals[u + 1] ^= w, vals[v + 1] ^= w ;  

	for (i = 1 ; i <= N ; ++ i) if (vals[i]) ctn[vals[i]] ++ ; 

	for (i = 0 ; i <= 15 ; ++ i) ans += ctn[i] / 2, now_st |= (ctn[i] & 1) << i ;

	for (i = 1 ; i < MAXS ; ++ i) sz[i] = sz[i - (i & -i)] + 1 ; 

	ans += do_do(now_st) ; cout << ans << endl ; return 0 ; 

}

// Optimized solution to the same problem (faster):
#pragma GCC optimize("Ofast,unroll-loops")

#include<bits/stdc++.h>

#define ll long long

#define F first

#define S second

#define P pair

#define FOR(i,a,b) for(int i=a;i<=b;i++)

#define rep(i,a,b) for(int i=a;i<b;i++) 

#define V vector

#define RE return

#define ALL(a) a.begin(),a.end()

#define MP make_pair

#define PB push_back

#define PF push_front

#define FILL(a,b) memset(a,b,sizeof(a))

using namespace std;

int c[16],n,v[200005],dp[1<<16];

int dfs(int x){

	if(dp[x]!=-1)RE dp[x];

	int re=1000000000;

	rep(i,1,16){

		if(x&(1<<i)){

			rep(j,i+1,16){

				if(x&(1<<j)){

					re=min(re,dfs(x^(1<<i)^(1<<j)^(1<<(i^j)))+((x&(1<<(i^j)))?2:1));

				}

			}

			break;

		}

	}

	RE dp[x]=re;

}

int main(){

	ios::sync_with_stdio(0);

    cin.tie(0);

	cin>>n;

	int x,y,z;

	rep(i,1,n){

		cin>>x>>y>>z;

		v[x]^=z;v[y]^=z;

	}

	int ans=0;

	rep(i,0,n){

		c[v[i]]++;

	}

	FOR(i,1,15){

		ans+=c[i]/2;

		c[i]&=1;

	}

	int get=0;

	FILL(dp,-1);dp[0]=0;

	FOR(i,1,15)if(c[i])get^=(1<<i);

	cout<<dfs(get)+ans;

	RE 0;

}






// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<cstring>

using namespace std ;

int n ;

const int N = 1e5 + 10 ;

const int M = 1 << 17 ;

int s[N] , S , ans , f[M] , inf , sum[20] ;

 

inline int dfs(int S) {

  if(! S) return 0 ;

  if(f[S] < inf) return f[S] ;

  for(register int i = 0 ; i < 16 ; i ++)

    if(S & (1 << i)) {

      for(register int j = 0 ; j < 16 ; j ++)

        if(i != j && (S & (1 << j))) {

          int p = i ^ j ;

          int x = S ^ (1 << i) ^ (1 << j) ^ (1 << p) ;

          if(S & (1 << p)) { f[S] = min(f[S] , dfs(x) + 2) ; }

          else { f[S] = min(f[S] , dfs(x) + 1) ; }

        }

    }

    return f[S] ;

}

signed main(){

  ios :: sync_with_stdio(false) ;

  cin.tie(0) ;

  cout.tie(0) ;

  cin >> n ;

  for(register int i = 1 ; i < n ; i ++) { int a , b , c ; cin >> a >> b >> c ; s[a] ^= c ; s[b] ^= c ; }

  for(register int i = 0 ; i < n ; i ++) { sum[s[i]] ++ ; }

  for(register int i = 1 ; i < 16 ; i ++)

    ans += (sum[i] >> 1) , S += (1 << i) * (sum[i] & 1) ;

  memset(f , 0x7f , sizeof(f)) ; inf = f[0] ;

  cout << ans + dfs(S) << '\n' ;

}

/*

5

0 1 1

0 2 3

0 3 6

3 4 4

*/

// Optimized solution to the same problem (faster):
#pragma GCC optimize("Ofast,unroll-loops")

#include<bits/stdc++.h>

#define ll long long

#define F first

#define S second

#define P pair

#define FOR(i,a,b) for(int i=a;i<=b;i++)

#define rep(i,a,b) for(int i=a;i<b;i++) 

#define V vector

#define RE return

#define ALL(a) a.begin(),a.end()

#define MP make_pair

#define PB push_back

#define PF push_front

#define FILL(a,b) memset(a,b,sizeof(a))

using namespace std;

int c[16],n,v[200005],dp[1<<16];

int dfs(int x){

	if(dp[x]!=-1)RE dp[x];

	int re=1000000000;

	rep(i,1,16){

		if(x&(1<<i)){

			rep(j,i+1,16){

				if(x&(1<<j)){

					re=min(re,dfs(x^(1<<i)^(1<<j)^(1<<(i^j)))+((x&(1<<(i^j)))?2:1));

				}

			}

			break;

		}

	}

	RE dp[x]=re;

}

int main(){

	ios::sync_with_stdio(0);

    cin.tie(0);

	cin>>n;

	int x,y,z;

	rep(i,1,n){

		cin>>x>>y>>z;

		v[x]^=z;v[y]^=z;

	}

	int ans=0;

	rep(i,0,n){

		c[v[i]]++;

	}

	FOR(i,1,15){

		ans+=c[i]/2;

		c[i]&=1;

	}

	int get=0;

	FILL(dp,-1);dp[0]=0;

	FOR(i,1,15)if(c[i])get^=(1<<i);

	cout<<dfs(get)+ans;

	RE 0;

}






// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <algorithm>

#include <cstdio>

#include <vector>



int scan() {

  int r = 0, c;

  while ((c = getchar_unlocked()) >= '0')

    r = r * 10 + c - '0';

  return r;

}



inline bool test(const int x, const int y) noexcept { return x & 1 << y; }



int main() {

  const int n = scan();

  std::vector<int> v(n, 0);

  for (int i = 0; i != n - 1; i += 1) {

    const int x = scan();

    const int y = scan();

    const int a = scan();

    v[x] ^= a;

    v[y] ^= a;

  }

  int ans = n;

  int b = 0;

  for (const int e : v) {

    if (e == 0) {

      ans -= 1;

      continue;

    }

    if (test(b, e))

      ans -= 1;

    b ^= 1 << e;

  }

  std::vector<int> dp(b / 2 + 1, -1);

  dp[b / 2] = 0;

  for (int s = b; s != 0; s -= 2) {

    if (dp[s >> 1] == -1)

      continue;

    int i = 16;

    while (i != 0) {

      i -= 1;

      if (test(s, i))

        break;

    }

    for (int j = 0; j != i; j += 1) {

      if (!test(s, j))

        continue;

      const int k = i ^ j;

      if (k > j)

        continue;

      int &d = dp[(s ^ 1 << i ^ 1 << j ^ 1 << k) >> 1];

      if (test(s, k))

        d = std::max(d, dp[s >> 1] + 1);

      else

        d = std::max(d, dp[s >> 1]);

    }

  }

  printf("%d", ans - dp[0]);

}

// Optimized solution to the same problem (faster):
#include <algorithm>

#include <array>

#include <cstdio>



/*

https://atcoder.jp/contests/abc153/submissions/9767872

*/

const int cm = 1 << 17;

char cn[cm], *ci = cn + cm, ct;

inline char getcha() {

  if (ci - cn == cm) {

    fread_unlocked(cn, 1, cm, stdin);

    ci = cn;

  }

  return *ci++;

}

inline int getint() {

  int A = 0;

  if (ci - cn + 16 > cm)

    while ((ct = getcha()) >= '0')

      A = A * 10 + ct - '0';

  else

    while ((ct = *ci++) >= '0')

      A = A * 10 + ct - '0';

  return A;

}

/*

https://atcoder.jp/contests/abc153/submissions/9767872

*/



inline constexpr bool test(const int x, const int y) noexcept {

  return x & 1 << y;

}



int main() {

  const int n = getint();

  std::array<int, 100000> v = {};

  for (int i = 0; i != n - 1; i += 1) {

    const int x = getint();

    const int y = getint();

    const int a = getint();

    v[x] ^= a;

    v[y] ^= a;

  }

  int ans = n;

  int b = 0;

  for (int i = 0; i != n; i += 1) {

    const int e = v[i];

    if (e == 0) {

      ans -= 1;

    } else {

      if (test(b, e))

        ans -= 1;

      b ^= 1 << e;

    }

  }



  std::array<int, 65536 / 2> dp = {};

  dp[b >> 1] = 1;

  for (int s = b; s != 0; s -= 2) {

    if (dp[s >> 1] == 0)

      continue;

    int i = 16;

    while (i != 0) {

      i -= 1;

      if (test(s, i))

        break;

    }

    for (int j = 0; j != i; j += 1) {

      if (!test(s, j))

        continue;

      const int k = i ^ j;

      if (k > j)

        continue;

      int &d = dp[(s ^ 1 << i ^ 1 << j ^ 1 << k) >> 1];

      if (test(s, k))

        d = std::max(d, dp[s >> 1] + 1);

      else

        d = std::max(d, dp[s >> 1]);

    }

  }

  printf("%d", ans - dp[0] + 1);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <algorithm>

#include <cstdio>

#include <vector>



int scan() {

  int r = 0, c;

  while ((c = getchar_unlocked()) >= '0')

    r = r * 10 + c - '0';

  return r;

}



inline bool test(const int x, const int y) noexcept { return x & 1 << y; }



int main() {

  const int n = scan();

  std::vector<int> v(n, 0);

  for (int i = 0; i != n - 1; i += 1) {

    const int x = scan();

    const int y = scan();

    const int a = scan();

    v[x] ^= a;

    v[y] ^= a;

  }

  int ans = n;

  int b = 0;

  for (const int e : v) {

    if (e == 0) {

      ans -= 1;

      continue;

    }

    if (test(b, e))

      ans -= 1;

    b ^= 1 << e;

  }

  std::vector<int> dp(b / 2 + 1, -1);

  dp[b / 2] = 0;

  for (int s = b; s != 0; s -= 2) {

    if (dp[s >> 1] == -1)

      continue;

    int i = 16;

    while (i != 0) {

      i -= 1;

      if (test(s, i))

        break;

    }

    for (int j = 0; j != i; j += 1) {

      if (!test(s, j))

        continue;

      const int k = i ^ j;

      if (k > j)

        continue;

      int &d = dp[(s ^ 1 << i ^ 1 << j ^ 1 << k) >> 1];

      if (test(s, k))

        d = std::max(d, dp[s >> 1] + 1);

      else

        d = std::max(d, dp[s >> 1]);

    }

  }

  printf("%d", ans - dp[0]);

}


// Optimized solution to the same problem (faster):
#include <algorithm>

#include <array>

#include <cstdio>



/*

https://atcoder.jp/contests/abc153/submissions/9767872

*/

const int cm = 1 << 17;

char cn[cm], *ci = cn + cm, ct;

inline char getcha() {

  if (ci - cn == cm) {

    fread_unlocked(cn, 1, cm, stdin);

    ci = cn;

  }

  return *ci++;

}

inline int getint() {

  int A = 0;

  if (ci - cn + 16 > cm)

    while ((ct = getcha()) >= '0')

      A = A * 10 + ct - '0';

  else

    while ((ct = *ci++) >= '0')

      A = A * 10 + ct - '0';

  return A;

}

/*

https://atcoder.jp/contests/abc153/submissions/9767872

*/



inline constexpr bool test(const int x, const int y) noexcept {

  return x & 1 << y;

}



int main() {

  const int n = getint();

  std::array<int, 100000> v = {};

  for (int i = 0; i != n - 1; i += 1) {

    const int x = getint();

    const int y = getint();

    const int a = getint();

    v[x] ^= a;

    v[y] ^= a;

  }

  int ans = n;

  int b = 0;

  for (int i = 0; i != n; i += 1) {

    const int e = v[i];

    if (e == 0) {

      ans -= 1;

    } else {

      if (test(b, e))

        ans -= 1;

      b ^= 1 << e;

    }

  }



  std::array<int, 65536 / 2> dp = {};

  dp[b >> 1] = 1;

  for (int s = b; s != 0; s -= 2) {

    if (dp[s >> 1] == 0)

      continue;

    int i = 16;

    while (i != 0) {

      i -= 1;

      if (test(s, i))

        break;

    }

    for (int j = 0; j != i; j += 1) {

      if (!test(s, j))

        continue;

      const int k = i ^ j;

      if (k > j)

        continue;

      int &d = dp[(s ^ 1 << i ^ 1 << j ^ 1 << k) >> 1];

      if (test(s, k))

        d = std::max(d, dp[s >> 1] + 1);

      else

        d = std::max(d, dp[s >> 1]);

    }

  }

  printf("%d", ans - dp[0] + 1);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int inf=1e9;

const int maxn=1e5+5;

int d[maxn],cnt[16],dp[1<<16],vis[1<<16],n;

int dfs(int S) {

	if(!S) return 0;

	if(vis[S]) return dp[S];

	dp[S]=inf;vis[S]=1;

	for(re int i=1;i<16;++i) 

		for(re int j=i+1;j<16;++j) 

			if((S>>(j-1)&1)&&(S>>(i-1)&1)) {

				int x=S^(1<<(i-1))^(1<<(j-1));

				if(x>>((i^j)-1)&1) 

					dp[S]=min(dp[S],dfs(x^(1<<(i^j)-1))+2);

				else dp[S]=min(dp[S],dfs(x|(1<<(i^j)-1))+1);

			}

	return dp[S];

}

int main() {

	n=read();

	for(re int x,y,w,i=1;i<n;i++) {

		x=read(),y=read(),w=read();

		d[x]^=w,d[y]^=w;

	}

	for(re int i=0;i<n;i++) cnt[d[i]]++;

	int S=0,nw=0;

	for(re int i=1;i<16;++i) nw+=cnt[i]/2;

	for(re int i=1;i<16;++i) if(cnt[i]&1) S|=(1<<(i-1));

	printf("%d\n",nw+dfs(S)); 

	return 0;

}




// Optimized solution to the same problem (faster):
#include<stdio.h>

void ckmin(int&x,const int&y)

{

	x=x<y?x:y;

}

int n,m,a[100005],f[1<<15],ans;

int main()

{

	scanf("%d",&n);

	for(int i=1,x,y,z;i<n;i++)

	{

		scanf("%d%d%d",&x,&y,&z);

		a[x]^=z;a[y]^=z;

	}

	for(int i=0;i<n;i++)

		if(a[i]--)

			ans+=m>>a[i]&1,m^=1<<a[i];

	for(int s=1;s<=m;++s)

	{

		int x=0;

		for(int j=0;j<16;++j)if(s>>j&1)x^=j+1;

		if(x)f[s]=1e9;

		else{

			f[s]=__builtin_popcount(s)-1;

			for(int t=(s-1)&s;t;t=(t-1)&s)ckmin(f[s],f[t]+f[s^t]);

		}

	}

	printf("%d",ans+f[m]);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int n,cnt[100003],cntt[16],ans;

int dp[65536];

int main(){

	cin>>n;

	for(int i=1;i<n;i++){int x,y,a;cin>>x>>y>>a;cnt[x]^=a;cnt[y]^=a;}

	for(int i=0;i<n;i++)cntt[cnt[i]]++;

	for(int i=1;i<16;i++)ans+=cntt[i]/2,cntt[i]%=2;

	int tmp=0;for(int i=1;i<16;i++)tmp=tmp+cntt[i]*(1<<i);

	memset(dp,31,sizeof(dp));

	dp[tmp]=0; 

	for(int i=tmp;i>0;i-=2)

		if(dp[i]<20000000)

			for(int j=1;j<16;j++)

				for(int k=j+1;k<16;k++)

					if((i|(1<<j))==i&&(i|(1<<k))==i)

						for(int l=1;l<=j;l++)

							if(((j|k)|l)==(j|k))

								dp[(((i-(1<<j)-(1<<k))^(1<<(j^l)))^(1<<(k^l)))/2*2]=min(dp[i]+1+bool((i&(1<<(j^l)))!=0)+

								bool((i&(1<<(k^l)))!=0),dp[(((i-(1<<j)-(1<<k))^(1<<(j^l)))^(1<<(k^l)))/2*2]);

	cout<<ans+dp[0];

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

void ckmin(int&x,const int&y)

{

	x=x<y?x:y;

}

int n,m,a[100005],f[1<<15],ans;

int main()

{

	scanf("%d",&n);

	for(int i=1,x,y,z;i<n;i++)

	{

		scanf("%d%d%d",&x,&y,&z);

		a[x]^=z;a[y]^=z;

	}

	for(int i=0;i<n;i++)

		if(a[i]--)

			ans+=m>>a[i]&1,m^=1<<a[i];

	for(int s=1;s<=m;++s)

	{

		int x=0;

		for(int j=0;j<16;++j)if(s>>j&1)x^=j+1;

		if(x)f[s]=1e9;

		else{

			f[s]=__builtin_popcount(s)-1;

			for(int t=(s-1)&s;t;t=(t-1)&s)ckmin(f[s],f[t]+f[s^t]);

		}

	}

	printf("%d",ans+f[m]);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

const int maxn=100005;

int n,a[maxn],cnt[16],dp[1<<16];

vector<int> v;

int main()

{

    scanf("%d",&n);

    for (int i=0;i<n-1;++i) {

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        a[u]^=w;

        a[v]^=w;

    }

    for (int i=0;i<n;++i)

        ++cnt[a[i]];

    int res=0;

    for (int i=1;i<16;++i) {

        res+=cnt[i]/2;

        if (cnt[i]&1)

            v.push_back(i);

    }

    dp[0]=0;

    for (int i=1;i<1<<(int)v.size();++i) {

        int mask=0;

        for (int j=0;j<(int)v.size();++j)

            if (1&(i>>j))

                mask^=v[j];

        for (int j=0;j<(int)v.size();++j)

            if (1&(i>>j))

                dp[i]=max(dp[i],dp[i^(1<<j)]+!mask);

    }

    return cout<<res+v.size()-dp[(1<<(int)v.size())-1]<<endl,0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5, MAXS = ( 1 << 16 ) + 5;



template<typename _T>

void read( _T &x )

{

	x = 0;char s = getchar();int f = 1;

	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}

	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}

	x *= f;

}



template<typename _T>

void write( _T x )

{

	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }

	if( 9 < x ){ write( x / 10 ); }

	putchar( x % 10 + '0' );

}



template<typename _T>

_T MIN( const _T a, const _T b )

{

	return a < b ? a : b;

}



int f[MAXS];

int w[MAXN];

int N, cnt;

bool vis[MAXS];



bool chk( const int S, const int b ) { return S >> b & 1; }



int DFS( const int S )

{

	if( ! S ) return f[S] = 0;

	if( vis[S] ) return f[S];

	vis[S] = true;

	for( int i = 1 ; i <= 15 ; i ++ )

		for( int j = i + 1 ; j <= 15 ; j ++ )

			if( chk( S, i - 1 ) && chk( S, j - 1 ) )

			{

				int t = S ^ ( 1 << i - 1 ) ^ ( 1 << j - 1 );

				int v = i ^ j, nxt = t ^ ( 1 << v - 1 );

				f[S] = MIN( f[S], DFS( nxt ) + 1 + chk( t, v - 1 ) );

			}

	return f[S];

}



int main()

{

	read( N );

	for( int i = 1, x, y, b ; i < N ; i ++ )

		read( x ), read( y ), read( b ),

		w[x + 1] ^= b, w[y + 1] ^= b;

	int sta = 0, tot = 0;

	for( int i = 1 ; i <= N ; i ++ )

		if( w[i] )

			tot += ( sta >> w[i] - 1 ) & 1, 

			sta ^= 1 << w[i] - 1;

	memset( f, 0x3f, sizeof f );

	write( DFS( sta ) + tot ), putchar( '\n' ); 

	return 0;

}

/*

3

0 1 1

0 2 1

*/

// Fastest known solution for this problem: