stablegradients/pie-gem5-pairs huggingface dataset:
// 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);

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

}




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

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

}

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

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

}


// Faster C++ solution for the same problem (measured speedup: 2.2033180030478845x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MN 200005

using namespace std;

int n,m,a[MN],val[MN],ans,f[1<<16],sum[20];

int main(){

	scanf("%d",&n);int x,y,v;

	for(int i=1;i<n;i++)scanf("%d%d%d",&x,&y,&v),a[x]^=v,a[y]^=v;

	for(int i=0;i<n;i++)sum[a[i]]++;

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

		ans+=sum[i]/2;

		if(sum[i]%2)val[m++]=i;

	}memset(f,0x3f,sizeof(f));f[0]=0;

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

		int x=0,cnt=0;

		for(int j=0;j<m;j++)if(i&(1<<j))x^=val[j],cnt++;

		if(!x)f[i]=cnt-1;

		for(int y=i-(i&(-i)),z=y;z;z=(z-1)&y,f[i]=min(f[i],f[z]+f[i^z]));

	}printf("%d\n",f[(1<<m)-1]+ans);

}
// Slower C++ solution:
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

const int inf = 1<<16;

int N,x,y,z,need[100010],tot[20],ans,md[inf],all;

bool vis[inf];

int read()

{

	static int x;

	static char ch;

	x = 0;

	for(ch=getchar();ch>'9'||ch<'0';ch=getchar());

	for(;ch>='0'&&ch<='9';ch=getchar()) x = x * 10 + ch - '0';

	return x;

}

int length(int x)

{

	int len = 0; 

	while (x)

	{

		len += x & 1;

		x >>= 1;

	}

	return len;

}

int find(int now)

{

	if (!now) return 0;

	if (vis[now]) return md[now];

	vis[now] = true;

	int ret = 20,next;

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

	 if ((now >> i) & 1)

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

	   if ((i!=j) && ((now>>j)&1))

	     {

	     	next = now ^ (1<<i) ^ (1<<j) ^ (1<<(i ^ j));

	     	if (length(next) < length(now)) ret = min(ret , find(next) + 1 + (~next >> (i ^ j) & 1));

		 }

	 return md[now] = ret;	

}

int main()

{

	N = read();

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

	{

		x = read() + 1;

		y = read() + 1;

		z = read();

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

	}

	ans = 0;

	for (int i = 1;i<=N;++i) tot[need[i]]++;

	for (int i = 1;i<=15;++i) ans += tot[i] >> 1,all |= (tot[i] & 1) << i;

	ans += find(all);

	printf("%d\n",ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.1680605775258006x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MN 200005

using namespace std;

int n,m,a[MN],val[MN],ans,f[1<<16],sum[20];

int main(){

	scanf("%d",&n);int x,y,v;

	for(int i=1;i<n;i++)scanf("%d%d%d",&x,&y,&v),a[x]^=v,a[y]^=v;

	for(int i=0;i<n;i++)sum[a[i]]++;

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

		ans+=sum[i]/2;

		if(sum[i]%2)val[m++]=i;

	}memset(f,0x3f,sizeof(f));f[0]=0;

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

		int x=0,cnt=0;

		for(int j=0;j<m;j++)if(i&(1<<j))x^=val[j],cnt++;

		if(!x)f[i]=cnt-1;

		for(int y=i-(i&(-i)),z=y;z;z=(z-1)&y,f[i]=min(f[i],f[z]+f[i^z]));

	}printf("%d\n",f[(1<<m)-1]+ans);

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

}


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

*/
// Slower C++ solution:
#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

const int inf = 1<<16;

int N,x,y,z,need[100010],tot[20],ans,md[inf],all;

bool vis[inf];

int read()

{

	static int x;

	static char ch;

	x = 0;

	for(ch=getchar();ch>'9'||ch<'0';ch=getchar());

	for(;ch>='0'&&ch<='9';ch=getchar()) x = x * 10 + ch - '0';

	return x;

}

int length(int x)

{

	int len = 0; 

	while (x)

	{

		len += x & 1;

		x >>= 1;

	}

	return len;

}

int find(int now)

{

	if (!now) return 0;

	if (vis[now]) return md[now];

	vis[now] = true;

	int ret = 20,next;

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

	 if ((now >> i) & 1)

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

	   if ((i!=j) && ((now>>j)&1))

	     {

	     	next = now ^ (1<<i) ^ (1<<j) ^ (1<<(i ^ j));

	     	if (length(next) < length(now)) ret = min(ret , find(next) + 1 + (~next >> (i ^ j) & 1));

		 }

	 return md[now] = ret;	

}

int main()

{

	N = read();

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

	{

		x = read() + 1;

		y = read() + 1;

		z = read();

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

	}

	ans = 0;

	for (int i = 1;i<=N;++i) tot[need[i]]++;

	for (int i = 1;i<=15;++i) ans += tot[i] >> 1,all |= (tot[i] & 1) << i;

	ans += find(all);

	printf("%d\n",ans);

	return 0;

}

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

*/
// Slower C++ solution:
#include<bits/stdc++.h>

#include<iostream>

using namespace std;

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

#define PII pair<int,int>

#define PI acos(-1.0)

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

typedef long long ll;

typedef unsigned long long ull;

const int INF=0x3f3f3f3f;

const int maxn=1e5+10;

int dp[1<<16],V[maxn],cnt[16];

int n,x,y,a;



int Work(int S)

{

    if(S==0) return 0;

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

    dp[S]=INF;

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

    {

    	if(S&(1<<i))

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

            {

            	

            	if(S&(1<<j))

                {

                    int cs=S^(1<<i)^(1<<j)^(1<<(i^j));

                    if(i!=j)

					{

						if(((1<<(i^j)) & S) == (1<<(i^j))) dp[S]=min(dp[S], Work(cs) + 2);

						else dp[S]=min(dp[S], Work(cs) + 1 ); 

					}

                }

			}

	}

    return dp[S];

}

int main()

{

    scanf("%d",&n);

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

    {

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

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

    }

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

    int ans=0,s=0;

    for(int i=0;i<16;i++) ans += cnt[i]/2, s^=(cnt[i]&1)<<i;

    memset(dp,-1,sizeof dp);

    ans+=Work(s);

    printf("%d\n",ans);

	return 0;

}


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

*/
// Slower C++ solution:
#include<bits/stdc++.h>

#define N 100005

#define M 65540

using namespace std;

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



int dfs(int S)

{

  if(!S)return 0; 

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

  for(int i=0;i<16;i++)if((S>>i)&1)

    for(int j=0;j<16;j++)if(i!=j&&(S>>j)&1)

    {

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

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

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

      //枚举每次异或的两个节点i,j,i异或掉j,j异或掉j,还剩下p=i^j

      //如果p本身存在那两个p直接消掉 

    }

  return f[S];

}



int main()

{

  int a,b,c;

  scanf("%d",&n);

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

    scanf("%d%d%d",&a,&b,&c),s[a]^=c,s[b]^=c;

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

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

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

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

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

  return 0;

} 

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

*/
// Slower C++ solution:
#include <iostream>

using namespace std;



typedef long long ll;



int cnt = 0, len, k;

ll ans;



void dfs(int x, ll i) {

    if (len == x) {

        cnt++;

        if (cnt == k) {

            ans = i;

        }

        i /= 10;

        return;

    }

    ll u = i % 10;

    for (ll j = u - 1; j <= u + 1; j++) {

        if (j < 0 || j > 9)

            continue;

        else {

            len++;

            dfs(x, i * 10 + j);

            len--;

        }

    }

}



int main(int argc, const char* argv[]) {

    cin >> k;

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

        for (ll i = 1; i <= 9; i++) {

            len = 1;

            dfs(j, i);

        }

    }

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.2921877230880305x):
#include <iostream>

#include <cstdio>

#include <iomanip>

#include <string>

#include <cmath>

#include <algorithm>

#include <iomanip> 

#include <cstring>

#include <queue>

#include <stack> 

#include <vector>

#include <map>

#include <set>

using namespace std;

typedef long long ll;

queue<ll> q;

int k;

int main(){

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	cin >> k;

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

		q.push(i);

	}

	ll cnt = 0;

	ll t;

	while(!q.empty()){

		cnt++;

		t = q.front();

		q.pop();

		if(cnt == k){

			cout << t << endl; 

			break;

		}

		if(t % 10 != 0){

			q.push(t * 10 + t % 10 - 1);

		}

		q.push(t * 10 + t % 10);

		if(t % 10 != 9){

			q.push(t * 10 + t % 10 + 1);

		}

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

using namespace std;



typedef long long ll;



int cnt = 0, len, k;

ll ans;



void dfs(int x, ll i) {

    if (len == x) {

        cnt++;

        if (cnt == k) {

            ans = i;

        }

        i /= 10;

        return;

    }

    ll u = i % 10;

    for (ll j = u - 1; j <= u + 1; j++) {

        if (j < 0 || j > 9)

            continue;

        else {

            len++;

            dfs(x, i * 10 + j);

            len--;

        }

    }

}



int main(int argc, const char* argv[]) {

    cin >> k;

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

        for (ll i = 1; i <= 9; i++) {

            len = 1;

            dfs(j, i);

        }

    }

    cout << ans << endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.4245304019371976x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[100010]={0,1,2,3,4,5,6,7,8,9}; 

int main()

{

	int k,id=1;scanf("%d",&k);

	for(int i=10; i<=k; )

	{

		ll x=a[id]*10,y=a[id++]%10;

		if(y==0)

		{

			a[i++]=x;

			a[i++]=x+1;

		}

		else if(y==9)

		{

			a[i++]=x+8;

			a[i++]=x+9;

		}

		else

		{

			a[i++]=x+y-1;

			a[i++]=x+y;

			a[i++]=x+y+1;

		}

	}

	printf("%lld\n",a[k]);

	return 0;

}