stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<iomanip>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<vector>

#include<cctype>

#define szxb 1000010

#define GO goto endreturn;

using namespace std;

int n,m;

struct ele{int cut;bool fly;}a[szxb];

inline bool cmp(ele x,ele y){return (x.cut>y.cut);}

int main()

{

	scanf("%d%d",&n,&m);int now(0);

	for(register int i(1);i<=n;i++){scanf("%d",&a[now++].cut);a[now].fly=1;scanf("%d",&a[now++].cut);}

	//for(register int i(0);i<=now-2;i++){for(register int j(0);j<=now-i-1;j++){if(a[j].cut<a[j+1].cut){swap(a[j],a[j+1]);}}}

	sort(a,a+now,cmp);

	int ans(0);

	for(register int i(0);i<=now-1;i++){if(a[i].fly){ans++;m-=a[i].cut;if(m<=0){GO}}else{if(!(m%a[i].cut)){ans+=(m/a[i].cut);}else{ans+=((m/a[i].cut)+1);}GO;}}

	endreturn:

		printf("%d",ans);return putchar(10),0;

}

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

#include<algorithm>

using namespace std;

struct ben

{

    int x;

    int y;

}a[1000000];

int cmp(const ben &xx,const ben &yy)

{

    return xx.x>yy.x;

}



int main()

{

    int n,h;

    int c=0;

    scanf("%d%d",&n,&h);

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

    {

    	c++;

        scanf("%d",&a[c].x);

        c++;

        a[c].y=1;

        

        scanf("%d",&a[c].x);

    }

    sort(a+1,a+c+1,cmp);

    int sum=0;

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

    {

        if(a[i].y==1)

        {

            sum++;

            h-=a[i].x;

            if(h<=0)

            {

                printf("%d",sum);

                return 0;

            }

        }

        else if(a[i].y!=1)

        {

            if(h%a[i].x==0) 

				sum+=h/a[i].x;

            else

			 	sum+=h/a[i].x+1;

            printf("%d",sum);

            return 0;



        }

    }

	return 0; 

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

     

    using namespace std;

     

    const int MaxN = 1e5 + 15;

     

    int n, h;

     

    pair<int, int> a[MaxN];

    long long c[MaxN];

     

    int main()

    {

        ios_base :: sync_with_stdio(false);

        cin.tie(NULL);

     

        cin >> n >> h;

     

        int mx = 0;

     

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

        {

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

            mx = max(mx, a[i].second);

        }

        sort(a + 1, a + n + 1);

        for(int i = n; i; --i)

            c[i] = c[i + 1] + a[i].first;

     

        long long ans = 1e9;

     

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

        {

            if(c[i] >= h)

                ans = min(ans, n - i + 1ll);

            else

                ans = min(ans, n - i + 1 + (h - c[i]) / mx + ((h - c[i]) % mx ? 1 : 0));

        }

     

        cout << ans << '\n';

        return 0;

    }

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

#include<algorithm>

using namespace std;

struct ben

{

    int x;

    int y;

}a[1000000];

int cmp(const ben &xx,const ben &yy)

{

    return xx.x>yy.x;

}



int main()

{

    int n,h;

    int c=0;

    scanf("%d%d",&n,&h);

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

    {

    	c++;

        scanf("%d",&a[c].x);

        c++;

        a[c].y=1;

        

        scanf("%d",&a[c].x);

    }

    sort(a+1,a+c+1,cmp);

    int sum=0;

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

    {

        if(a[i].y==1)

        {

            sum++;

            h-=a[i].x;

            if(h<=0)

            {

                printf("%d",sum);

                return 0;

            }

        }

        else if(a[i].y!=1)

        {

            if(h%a[i].x==0) 

				sum+=h/a[i].x;

            else

			 	sum+=h/a[i].x+1;

            printf("%d",sum);

            return 0;



        }

    }

	return 0; 

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

#include<iomanip>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<vector>

#include<cctype>

#define szxb 1000010

#define GO goto endreturn;

using namespace std;

int n,m;

struct ele{int cut;bool fly;}a[szxb];

inline bool cmp(ele x,ele y){return (x.cut>y.cut);}

int main()

{

	scanf("%d%d",&n,&m);int now(0);

	for(register int i(1);i<=n;i++){scanf("%d",&a[now++].cut);a[now].fly=1;scanf("%d",&a[now++].cut);}

	//for(register int i(0);i<=now-2;i++){for(register int j(0);j<=now-i-1;j++){if(a[j].cut<a[j+1].cut){swap(a[j],a[j+1]);}}}

	sort(a,a+now,cmp);

	int ans(0);

	for(register int i(0);i<=now-1;i++){if(a[i].fly){ans++;m-=a[i].cut;if(m<=0){GO}}else{if(!(m%a[i].cut)){ans+=(m/a[i].cut);}else{ans+=((m/a[i].cut)+1);}GO;}}

	endreturn:

		printf("%d",ans);return putchar(10),0;

}

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

#include<cstdio>

using namespace std;

inline void in(int &s){

	s=0;char c=getchar();

	while(c<'0' || c>'9'){

		c=getchar();

	}

	while(c>='0' && c<='9'){

		s=(s<<1)+(s<<3)+c-'0';

		c=getchar();

	}

}

int n,m,z,ans;

long long sum;

bool ok=1;

struct xx{

	int a,b;

}s[200002];

int cmp(xx x,xx y){

	return x.a>y.a;

}

int main(){

	in(n);in(m);

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

		in(s[z++].a);s[z].b=1;in(s[z++].a);

	}

	sort(s,s+z,cmp);

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

		if(s[i].b){

			m-=s[i].a;++ans;

		}

		else{

			if(m%s[i].a==0) ans+=m/s[i].a;

			else ans+=m/s[i].a+1;

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

		}

		if(m<1){

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

		}

	}

	return 0;

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

     

    using namespace std;

     

    const int MaxN = 1e5 + 15;

     

    int n, h;

     

    pair<int, int> a[MaxN];

    long long c[MaxN];

     

    int main()

    {

        ios_base :: sync_with_stdio(false);

        cin.tie(NULL);

     

        cin >> n >> h;

     

        int mx = 0;

     

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

        {

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

            mx = max(mx, a[i].second);

        }

        sort(a + 1, a + n + 1);

        for(int i = n; i; --i)

            c[i] = c[i + 1] + a[i].first;

     

        long long ans = 1e9;

     

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

        {

            if(c[i] >= h)

                ans = min(ans, n - i + 1ll);

            else

                ans = min(ans, n - i + 1 + (h - c[i]) / mx + ((h - c[i]) % mx ? 1 : 0));

        }

     

        cout << ans << '\n';

        return 0;

    }

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

#include<cstdio>

using namespace std;

inline void in(int &s){

	s=0;char c=getchar();

	while(c<'0' || c>'9'){

		c=getchar();

	}

	while(c>='0' && c<='9'){

		s=(s<<1)+(s<<3)+c-'0';

		c=getchar();

	}

}

int n,m,z,ans;

long long sum;

bool ok=1;

struct xx{

	int a,b;

}s[200002];

int cmp(xx x,xx y){

	return x.a>y.a;

}

int main(){

	in(n);in(m);

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

		in(s[z++].a);s[z].b=1;in(s[z++].a);

	}

	sort(s,s+z,cmp);

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

		if(s[i].b){

			m-=s[i].a;++ans;

		}

		else{

			if(m%s[i].a==0) ans+=m/s[i].a;

			else ans+=m/s[i].a+1;

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

		}

		if(m<1){

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

		}

	}

	return 0;

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

#include <cmath>

#include <functional>

#include <algorithm>

 

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

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

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

 

using namespace std;

 

int main() {

    int N, H, a[100000], b[100000];

    cin >> N >> H;

    REP(i, N) cin >> a[i] >> b[i];

 

    int a_max = *max_element(a, a + N);

    sort(b, b + N, greater<int>());

 

    int ans = 0, i = 0;

    while (H > 0) {

        if (b[i] > a_max) {

            H -= b[i];

            ans++;

        }

        else break;

        i++;

    }

    if (H <= 0) {

        cout << ans << endl;

        return 0;

    }

    ans += ceil((double)H / a_max);

    cout << ans << endl;

 

    return 0;

}

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

#include <algorithm>



using namespace std;



long long N, H;

long long b[100010], a = 0;



int main() {

  int i;

  scanf("%lld %lld", &N, &H);

  long long sum = 0;

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

    long long k;

    scanf("%lld %lld", &k, &b[i]);

    a = max(a, k);

  }

  sort(b, b+N);

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

    printf("a:%d b:%d", a[i], b[i]);

    }*/

  long long ans = 0;

  for (i = N-1; i >= 0 && b[i] > a; i--) {

    H -= b[i];

    ans += 1;

    if (H <= 0) {

      break;

    }

  }

  //printf("after_b:%d", ans);

  if (H >= 0) {

    long long num_a = H / a;

    ans += num_a;

    if (H % a > 0) {

      ans += 1;

    }

  }

  printf("%lld", ans);

  return 0;

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

        }

    }

    

    while(H>0) {

        H-=p[N-1].first;

        ans++;

        if(H<=0) {

            cout << ans << endl;

            return 0;

        }

    }

}


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

    

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

}


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

    

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

}


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

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

}

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

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

	

}


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

}