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

inline int Count(int x)

{

	int ans=0;

	for(int i=0;i<=15;++i) if(x&(1<<i)) ans++;

	return ans;

}

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(Count(cs)<Count(S)) 

					{

						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: 1.2547619243637995x):
#include<bits/stdc++.h>

#define maxl 100010

#define inf 2000000001



using namespace std;



int n,ans,res;

int a[maxl],dp[maxl],cnt[16];



inline void prework()

{

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

		a[i]=0,cnt[i]=0;

	int u,v,val;

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

	{

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

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

	}

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

		cnt[a[i]]++;

	res=0;ans=0;

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

	{

		ans+=cnt[i]/2;

		if(cnt[i]&1)

			res^=(1<<i);

	}		

}



inline int dfs(int s)

{

    if(s==0)

        return 0;

    if(dp[s])

        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(j!=i&&(s&(1<<j))){

                    int q=i^j;

                    if(s&(1<<q))

                        dp[s]=min(dp[s],dfs(s^(1<<i)^(1<<j)^(1<<q))+2);

                    else

                        dp[s]=min(dp[s],dfs(s^(1<<i)^(1<<j)^(1<<q))+1);

                }

            }



        }

    return dp[s];

}



inline void mainwork()

{

	int x=dfs(res);

	ans+=x;

}



inline void print()

{

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

}



int main()

{

	while(~scanf("%d",&n))

	{

		prework();

		mainwork();

		print();

	}

	return 0;

}
// 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;

inline int Count(int x)

{

	int ans=0;

	for(int i=0;i<=15;++i) if(x&(1<<i)) ans++;

	return ans;

}

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: 1.2543664312807108x):
#include<bits/stdc++.h>

#define maxl 100010

#define inf 2000000001



using namespace std;



int n,ans,res;

int a[maxl],dp[maxl],cnt[16];



inline void prework()

{

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

		a[i]=0,cnt[i]=0;

	int u,v,val;

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

	{

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

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

	}

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

		cnt[a[i]]++;

	res=0;ans=0;

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

	{

		ans+=cnt[i]/2;

		if(cnt[i]&1)

			res^=(1<<i);

	}		

}



inline int dfs(int s)

{

    if(s==0)

        return 0;

    if(dp[s])

        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(j!=i&&(s&(1<<j))){

                    int q=i^j;

                    if(s&(1<<q))

                        dp[s]=min(dp[s],dfs(s^(1<<i)^(1<<j)^(1<<q))+2);

                    else

                        dp[s]=min(dp[s],dfs(s^(1<<i)^(1<<j)^(1<<q))+1);

                }

            }



        }

    return dp[s];

}



inline void mainwork()

{

	int x=dfs(res);

	ans+=x;

}



inline void print()

{

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

}



int main()

{

	while(~scanf("%d",&n))

	{

		prework();

		mainwork();

		print();

	}

	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 gi()

{

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

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

	while(ch>='0' && ch<='9')f=f*10+ch-48,ch=getchar();

	return f;

}

int main()

{

	n=gi();

	int u,v,w;

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

		u=gi(),v=gi(),w=gi(),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.4429205587954543x):
#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;

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

using namespace std;



const int MAXN = 101010;



int a[MAXN];

int cnt[21];

int f[1<<17];

int n;



int res[21];

int cntr;



int main() {

	scanf("%d", &n);

	int u, v, w;

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

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

		a[u] ^= w;

		a[v] ^= w;

	}

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

		cnt[a[i]]++;

	int ans = 0;

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

		ans += cnt[i] >> 1;

		if(cnt[i] & 1) {

			res[cntr++] = i;

		}

	}

	f[0] = 0;

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

		int tmp = 0;

		for(int j = 0; j < cntr; ++j) {

			if(i & (1<<j))

				tmp ^= res[j];

		}

		tmp = !tmp;

		for(int j = 0; j < cntr; ++j) {

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

				f[i] = max(f[i], f[i ^ (1<<j)] + tmp);

			}

		}

	}

	ans += cntr;

	ans -= f[(1<<cntr) - 1];

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

	

	return 0;

}

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

}
// 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;

inline int Count(int x)

{

	int ans=0;

	for(int i=0;i<=15;++i) if(x&(1<<i)) ans++;

	return ans;

}

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(Count(cs)<Count(S)) 

					{

						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: 6.505958266620564x):
#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;

}
// 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;

inline int Count(int x)

{

	int ans=0;

	for(int i=0;i<=15;++i) if(x&(1<<i)) ans++;

	return ans;

}

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: 6.503907629409353x):
#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;

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

#define maxl 100010

#define inf 2000000001



using namespace std;



int n,ans,res;

int a[maxl],dp[maxl],cnt[16];



inline void prework()

{

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

		a[i]=0,cnt[i]=0;

	int u,v,val;

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

	{

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

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

	}

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

		cnt[a[i]]++;

	res=0;ans=0;

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

	{

		ans+=cnt[i]/2;

		if(cnt[i]&1)

			res^=(1<<i);

	}		

}



inline int dfs(int s)

{

    if(s==0)

        return 0;

    if(dp[s])

        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(j!=i&&(s&(1<<j))){

                    int q=i^j;

                    if(s&(1<<q))

                        dp[s]=min(dp[s],dfs(s^(1<<i)^(1<<j)^(1<<q))+2);

                    else

                        dp[s]=min(dp[s],dfs(s^(1<<i)^(1<<j)^(1<<q))+1);

                }

            }



        }

    return dp[s];

}



inline void mainwork()

{

	int x=dfs(res);

	ans+=x;

}



inline void print()

{

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

}



int main()

{

	while(~scanf("%d",&n))

	{

		prework();

		mainwork();

		print();

	}

	return 0;

}

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

}
// 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 gi()

{

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

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

	while(ch>='0' && ch<='9')f=f*10+ch-48,ch=getchar();

	return f;

}

int main()

{

	n=gi();

	int u,v,w;

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

		u=gi(),v=gi(),w=gi(),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: 27.10292168104834x):
#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;

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

}

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

}