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

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#define REP(i, n) for(i=0; i<n; i++)

#define REPR(i, n) for(i=n; i>=0; i--)

#define FOR(i, m, n) for(i=m; i<n; i++)

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

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

#define INF 10000000000

#define MOD 1000000007LL

#define MAX 100005

#define NIL -1

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef pair<double, double> doup;



ll modpow(ll x, ll n) {

    ll res=1;

    while(n>0) {

        if(n&1) res=res*x%MOD;

        x=x*x%MOD;

        n>>=1;

    }

    return res;

}



int main(void) {

    ll N, H;

    P p[MAX];

    ll i, ans=0;

    vector<ll> v;

    cin >> N >> H;

    for(i=0; i<N; i++) {

        cin >> p[i].first >> p[i].second;

    }

    sort(p, p+N);

    

    for(i=0; i<N; i++) {

        if(p[N-1].first<=p[i].second) {

            v.push_back(p[i].second);

        }

    }

    sort(v.begin(), v.end());

    

    for(i=(ll)v.size()-1; i>=0; i--) {

        H-=v[i]; ans++;

        if(H<=0) {

            cout << ans << endl;

            return 0;

        }

    }

    ans+=H/p[N-1].first;

    ans+=(H%p[N-1].first==0 ? 0 : 1);

    cout << ans << endl;

}


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

#include <cmath>

#include <string>

#include <algorithm>

#include <set>

#include <vector>

#include <map>

#include <list>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#define mkp(a, b) make_pair(a, b)

#define pb(t) push_back(t)

#define ft first

#define sc second

#define pt(num) cout << num << "\n"

#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD

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

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

#define chmax(a, b) (a<b ? a=b : 0)

#define chmin(a, b) (a>b ? a=b : 0)

#define INF 1000000000000000000

#define MOD 1000000007LL

#define MAX 101010

using namespace std;

typedef long long ll;

typedef pair<ll, ll> P;

typedef map<ll, ll> Map;





int main(void) {

    ll N, H;

    cin >> N >> H;

    ll i;

    priority_queue<P> q;

    for(i=0; i<N; i++) {

        ll a, b;

        cin >> a >> b;

        q.push(P(a, 0));

        q.push(P(b, 1));

    }

    

    ll ans=0;

    while(H>0) {

        P f=q.top(); q.pop();

        ll u=f.ft;

        

        if(f.sc==1) {

            H-=u;

            ans++;

        }else {

            ans+=(H+u-1)/u;

            break;

        }

    }

    

    pt(ans);

    

}


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

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;

}


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

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXS = 1 << 16;

const int MAXN = 1e5 + 5;

int dp[MAXS] , n , S , a[MAXN];

int DP(int now) {

	if(now == 0) return 0;

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

	dp[now] = 1e9;

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

		if(!(now & (1 << i))) continue;

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

			if(!(now & (1 << j))) continue;

			int nnow = now ^ (1 << i) ^ (1 << j) ^ (1 << (((i+1) ^ (j+1)) - 1));

//			if(now == 7) printf("%d %d %d\n" , nnow);

			int f;

			if(((now ^ (1 << i) ^ (1 << j)) & (1 << (((i+1) ^ (j+1)) - 1)))) f = 1;

			else f = 0;

			dp[now] = min(dp[now] , DP(nnow) + 1 + f);

		}

	}

	return dp[now];	

}

int main() {

	scanf("%d" , &n);

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

		int u , v , w;

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

		a[u] ^= w;

		a[v] ^= w;

	}

	int ans = 0;

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

//		printf("%d\n" , a[i]);

		if(!a[i]) continue;

		if(S & (1 << (a[i] - 1))) ans ++;

		S ^= (1 << (a[i] - 1));

	} 

//	printf("%d " , S);

	memset(dp , -1 , sizeof dp);

	dp[0] = 0;

	ans += DP(S);

//	for (int now = 1; now < (1 << 15); ++now) {

//		for (int i = 0; i < 15; ++i) {

////			if(!(now & (1 << i))) continue;

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

////				if(!(now & (1 << j))) continue;

//				int nnow = now ^ (1 << i) ^ (1 << j) ^ (1 << (((i+1) ^ (j+1)) - 1));

////				if(now == 7) printf("%d %d %d\n" , nnow);

//				dp[now] = min(dp[now] , dp[nnow] + 1 + ((now ^ (1 << i) ^ (1 << j)) & (1 << (((i+1) ^ (j+1)) - 1))));

//			}

//		}

//	}

	printf("%d" , ans);

	return 0;

}

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

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>



using namespace std;



#define N 100008

#define INF 0x3f3f3f3f



int n;

int dp[N], v[N], p[N];



int dfs(int s)

{

    if (!s) return 0;

    if (dp[s] != INF) return dp[s];

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

    {

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

        {

            if (i == j) continue;

            if ((s & p[i]) && (s & p[j]))

            {

                int temp = i ^ j;

                if (p[temp] & s)

                    dp[s] = min(dp[s], dfs(s^p[temp]^p[i]^p[j])+2);

                else

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

            }

        }

    }

    return dp[s];

}



int main()

{

    int x, y, z;

    p[0] = 1;

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

        p[i] = p[i-1] * 2;

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

    {

        memset(v, 0, sizeof(v));

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

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

        {

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

            v[x+1] ^= z;

            v[y+1] ^= z;

        }

        int start = 0, ans = 0;

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

        {

            if (v[i] == 0) continue;

            if (start & p[v[i]])

                ans++;

            start ^= p[v[i]];                

        }

        ans += dfs(start);

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

    }

    return 0;

}

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

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXS = 1 << 16;

const int MAXN = 1e5 + 5;

int dp[MAXS] , n , S , a[MAXN];

int DP(int now) {

	if(now == 0) return 0;

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

	dp[now] = 1e9;

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

		if(!(now & (1 << i))) continue;

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

			if(!(now & (1 << j))) continue;

			int nnow = now ^ (1 << i) ^ (1 << j) ^ (1 << (((i+1) ^ (j+1)) - 1));

//			if(now == 7) printf("%d %d %d\n" , nnow);

			int f;

			if(((now ^ (1 << i) ^ (1 << j)) & (1 << (((i+1) ^ (j+1)) - 1)))) f = 1;

			else f = 0;

			dp[now] = min(dp[now] , DP(nnow) + 1 + f);

		}

	}

	return dp[now];	

}

int main() {

	scanf("%d" , &n);

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

		int u , v , w;

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

		a[u] ^= w;

		a[v] ^= w;

	}

	int ans = 0;

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

//		printf("%d\n" , a[i]);

		if(!a[i]) continue;

		if(S & (1 << (a[i] - 1))) ans ++;

		S ^= (1 << (a[i] - 1));

	} 

//	printf("%d " , S);

	memset(dp , -1 , sizeof dp);

	dp[0] = 0;

	ans += DP(S);

//	for (int now = 1; now < (1 << 15); ++now) {

//		for (int i = 0; i < 15; ++i) {

////			if(!(now & (1 << i))) continue;

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

////				if(!(now & (1 << j))) continue;

//				int nnow = now ^ (1 << i) ^ (1 << j) ^ (1 << (((i+1) ^ (j+1)) - 1));

////				if(now == 7) printf("%d %d %d\n" , nnow);

//				dp[now] = min(dp[now] , dp[nnow] + 1 + ((now ^ (1 << i) ^ (1 << j)) & (1 << (((i+1) ^ (j+1)) - 1))));

//			}

//		}

//	}

	printf("%d" , ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// luogu-judger-enable-o2

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<cstring>

#define ll long long

#define maxn 100005

#define ll long long

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

#define for_edge(x) for(int i=head[x];i;i=e[i].nxt)

using namespace std;

inline int read(){char c=getchar();int f=1;int ans = 0;while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}while(c<='9'&&c>='0'){ans =ans*10+c-'0';c=getchar();}return ans*f;}

//______________________________________________________________________________________

int n;

int v[maxn]; 

int cnt[16];

bool bo[1<<15];

int dp[1<<15];

int main()

{

	//freopen("0.in","r",stdin);

	n = read();

	re(i,1,n-1)

	{

		int x = read() ,y =read(), k=read();

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

	}

	re(i,0,n-1)	

		cnt[ v[i] ]++;

	ll ans = 0,s=0;;

	re(i,1,15)

	{

		ans += cnt[i] /2 ;

		//printf("%d ",cnt[i]);

		s|=(cnt[i]&1)<<i-1;

	}

	//printf("%\d",s);

	re(i,0,(1<<15)-1)

	{

		int sum = 0;

		re(j,1,15)

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

				sum^=j;

		if(!sum) bo[i] = 1;

	}

	re(i,1,(1<<15)-1)

		if(bo[i])

		{

			

			for(int j=i;j;j-=j&-j,dp[i]++);dp[i]--;

			for(int j=i;j;j=(j-1)&i)

				if(bo[j])

					dp[i] = min( dp[i] , dp[j] + dp[j^i] );

			//for(int j=15;j;j--) 

			//printf("%d",(i>>j-1)&1);printf(" %d\n",dp[i]);

		}

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

	

}


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

#define N 200005

using namespace std;

int bitcount(int S) {

	int ret = 0;

	while(S) ret ++, S -= (S & (-S));

	return ret;

}

int check(int S) {

	int ret = 0;

	for(int i = 0; i < 15; i ++) if(S & (1 << i)) ret ^= (i + 1);

	return ret;

}

int n, d[N], cnt[N], f[N];

int main() {

	scanf("%d", &n);

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

		int u, v, c;

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

		d[u] ^= c, d[v] ^= c;

	}

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

	int ans = 0, sta = 0;

	for(int i = 1; i < 16; i ++) ans += cnt[i] / 2, sta |= (cnt[i]&1) << (i - 1);

	memset(f, 0x3f, sizeof f);

	f[0] = 0;

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

		if((sta & S) != S || check(S)) continue;

		f[S] = bitcount(S) - 1;

		for(int SS = S; SS; SS = (SS - 1) & S) if(!check(SS)){ 

			f[S] = min(f[S], f[SS] + f[S ^ SS]);

		}

	}

	int ret = 0;

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

	return 0;

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


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

}


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

}


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

}

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

}

// 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: