stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
/*

  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;

}


// Faster C++ solution for the same problem (measured speedup: 1.131036590292014x):
#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 ; 

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 3.3902029786093286x):
#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

*/
// Slower C++ solution:
/*

  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;

}


// Faster C++ solution for the same problem (measured speedup: 3.5231978634868906x):
#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

*/
// Slower C++ solution:
#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 ; 

}

// Faster C++ solution for the same problem (measured speedup: 3.1150166968314097x):
#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

*/
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 4.092750302063029x):
#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;

}
// Slower C++ solution:
/*

  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;

}


// Faster C++ solution for the same problem (measured speedup: 4.253305542763914x):
#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;

}
// Slower C++ solution:
#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 ; 

}

// Faster C++ solution for the same problem (measured speedup: 3.7605375274957145x):
#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;

}
// Slower C++ solution:
#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

*/

// Faster C++ solution for the same problem (measured speedup: 1.2072286904018612x):
#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;

}
// Slower C++ solution:
#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]);

}

// Faster C++ solution for the same problem (measured speedup: 1.2770026825318481x):
#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);

}