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

#include <vector>

#include <deque>

#include <math.h>

#include <set>

#include <iomanip>

#include <time.h>

#include <list>

#include <stdio.h>

#include <queue>

#include <map>

#include <algorithm>

#include <assert.h>

#include <memory.h>



#define mk make_pair

#define sc second

#define fr first

#define pb push_back

#define sz(s) ( (int)s.size() )

#define all(s) s.begin(), s.end()



using namespace std;



const int N = 1e5 + 5;



int n, m, ar[N], cur[N], ans, mx[N], cnt, sum;



vector <int> g[N], V;



vector <pair <int, int> > vec;



main ()

{

    cin >> n >> m;

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

    {

        scanf("%d", &ar[i]), cur[ ar[i] % m ]++;



        g[ ar[i] % m ].pb( ar[i] );

    }



    ans = cur[0] >> 1;



    for (int i = 1; i < (m + 1) / 2; i++)

    {

        if (cur[i] >= cur[m - i])

        {

            ans += cur[m - i];

            vec.pb( mk( cur[i] - cur[m - i], i ) );

        }

        else

        {

            ans += cur[i];

            vec.pb( mk( cur[m - i] - cur[i], m - i ) );

        }

    }

    if (m % 2 == 0)

        ans += cur[m / 2] >> 1;



    for (auto x : vec)

    {

//        V.clear();



        sum = 0;

        cnt = 1;



        int v = x.sc, col = x.fr;



        sort(all(g[v]));



        for (int j = 1; j < sz(g[v]); j++)

        {

            if ( g[v][j] == g[v][j - 1] )

                cnt++;

            else

            {

                sum += (cnt - (cnt % 2));

//                V.pb(cnt - (cnt % 2) );

                cnt = 1;

            }

        }

        sum += (cnt - (cnt % 2));

//        V.pb( cnt - (cnt % 2) );

//        sort( all(V), greater<int>() );

        ans += min( sum, col ) / 2;

    }



    cout << ans << endl;

}


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

using namespace std;

int n,m;

int num[100005];

int yu[100005];

int temp;

int ans;

int main()

{

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

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

    {

        scanf("%d",&temp);

        num[temp]++;

        yu[temp%m]++;

    }

    if(yu[0]>=2)

    {

        int minn=yu[0]/2;

        yu[0]-=minn*2;

        ans+=minn;

    }

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

    {

        if(yu[i]>0 && yu[m-i]>0)

        {

            if(i!=m-i)

            {int minn=min(yu[i],yu[m-i]);

            yu[i]-=minn;

            yu[m-i]-=minn;

            ans+=minn;}

            else

            {

                int minn=yu[i]/2;

                yu[i]-=minn*2;

                ans+=minn;

            }

        }

    }

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

    {

        if(num[i]>=2 && yu[i%m]>=2)

        {

            int minn=min(num[i]/2,yu[i%m]/2);

            yu[i%m]-=2*minn;

            ans+=minn;

            //cout<<i<<endl;

        }

    }

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

}


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



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

#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)

#define rep1(i,n) for(int i = 1; i <= (n); i++)

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



#define ll long long

#define pi pair<int, int>

#define pll pair<ll, ll>



#define MOD 1000000007

#define INF 1000000000000000LL



using namespace std;



#define MAXM 110000



int main(){

  int n,m;cin>>n>>m;

  vector<int> x(n);

  rep(i, n)cin>>x[i];

  map<int, int>mp, mm;

  rep(i, n){

    mm[x[i]]++;

    mp[x[i]%m]++;

  }



  int result = 0;

  int tr = 0;

  rep(i, m){

//cout<<i<<' '<<result<<endl;

//if(i==12)cout<<"---"<<i<<endl;



    if(i==0 || m%2==0 && i==m/2){

      tr += mp[i]/2;

//if(i==12)cout<<tr<<endl;

    }else{

      int j = m-i;

      int s=mp[i],t=mp[j];

      mp[i]=0,mp[j]=0;

//if(i==12)cout<<t<<':'<<s<<endl;

      if(s>t)swap(s,t);

      //if(s==0)continue;

//if(i==12)cout<<result<<endl;

      result += s;

//if(i==12)cout<<result<<endl;

      t-=s;s=0;

//if(i==12)cout<<t<<':'<<s<<endl;



      int tt=t;

      int tr1 = 0;

      for(int k=i; k<=MAXM; k+=m){

        if(tt>=2 && mm[k]>=2){

          int x = min(mm[k]/2, tt/2);

          tr1 += x;

          tt -= 2*x;

        }

      }



      tt=t;

      int tr2 = 0;

      for(int k=j%m; k<=MAXM; k+=m){

        if(tt>=2 && mm[k]>=2){

          int x = min(mm[k]/2, tt/2);

          tr2 += x;

          tt -= 2*x;

        }

      }



      result += max(tr1, tr2);



//if(i==12)cout<<result<<' '<<tr1<<' '<<tr2<<endl;

//if(i==12)cout<<"---"<<i<<endl;

    }

  }



  cout<<result+tr<<endl;

//  cout<<result<<' '<<tr<<endl;



  return 0;

}


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



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

#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)

#define rep1(i,n) for(int i = 1; i <= (n); i++)

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



#define ll long long

#define pi pair<int, int>

#define pll pair<ll, ll>



#define MOD 1000000007

#define INF 1000000000000000LL



using namespace std;



#define MAXM 110000



int main(){

  int n,m;cin>>n>>m;

  vector<int> x(n);

  rep(i, n)cin>>x[i];

  map<int, int>mp, mm;

  rep(i, n){

    mm[x[i]]++;

    mp[x[i]%m]++;

  }



  int result = 0;

  int tr = 0;

  rep(i, m){

    if(i==0 || m%2==0 && i==m/2){

      tr += mp[i]/2;

    }else{

      int j = m-i;

      int s=mp[i],t=mp[j];

      mp[i]=0,mp[j]=0;

      if(s>t){

        swap(s,t);

        j=i;

      }

      //if(s==0)continue;

      result += s;

      t-=s;s=0;



      int tt=t;

      int tr2 = 0;

      for(int k=j%m; k<=MAXM; k+=m){

        if(tt>=2 && mm[k]>=2){

          int x = min(mm[k]/2, tt/2);

          tr2 += x;

          tt -= 2*x;

        }

      }



      result += tr2;



    }

  }



  cout<<result+tr<<endl;

//  cout<<result<<' '<<tr<<endl;



  return 0;

}


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

using namespace std;



typedef long long int ll;

typedef pair<ll, ll> pll;



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

#define REP(i, n) FOR(i, n, 0)

#define OF64 std::setprecision(10)



const ll MOD = 1000000007;

const ll INF = (ll)1e15;



vector<ll> Y[100005];

//! 同じmodのなかで同じ整数ペアの数

ll P[100005];

ll S[100005];



int main()

{

    ll N, M;

    cin >> N >> M;

    vector<ll> v;

    REP(i, N)

    {

        ll x;

        cin >> x;

        Y[x % M].push_back(x);

        if (Y[x % M].size() == 1)

            v.push_back(x % M);

    }



    memset(P, 0, sizeof(P));

    memset(S, 0, sizeof(S));

    REP(i, v.size())

    {

        sort(Y[v[i]].begin(), Y[v[i]].end());

        ll p = 0;

        FOR(j, Y[v[i]].size(), 1)

        {

            if (Y[v[i]][j - 1] == Y[v[i]][j])

            {

                p++;

                j++;

            }

        }

        S[v[i]] = Y[v[i]].size();

        P[v[i]] = p;

    }



    ll ans = 0;

    REP(i, v.size())

    {

        //! 先に足してMの倍数になるのかぞえる

        ll n = std::min(S[v[i]], S[(M - v[i]) % M]);

        if (v[i] == 0 || v[i] == M / 2)

            n /= 2;

        ans += n;

        S[v[i]] -= n;

        S[(M - v[i]) % M] -= n;

    }



    REP(i, v.size())

    {

        //! ペアが残ってれば数える

        ans += std::min(P[v[i]], S[v[i]] / 2);

    }

    cout << ans << endl;

    return 0;

}

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



using namespace std;



typedef long long int ll;

typedef pair<ll, ll> pll;



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

#define REP(i, n) FOR(i,n,0)

#define OF64 std::setprecision(10)



const ll MOD = 1000000007;

const ll INF = (ll) 1e15;



ll A[100005];

ll C[100005];

ll D[100005];

ll P[100005];



int main() {

    cin.tie(0);

    ios::sync_with_stdio(false);

    ll N, M;

    cin >> N >> M;

    memset(C, 0, sizeof(C));

    memset(P, 0, sizeof(P));

    REP(i, N) {

        cin >> A[i];

        C[A[i]]++;

        D[A[i] % M]++;

    }

    REP(i, 100005) {

        P[i % M] += C[i] / 2;

    }

    ll ans = 0;

    REP(i, M) {

        ll d = (M - i) % M;

        if (d != i) {

            ll m = std::min(D[d], D[i]);

            ans += m;

            D[d] -= m;

            D[i] -= m;

            ll x = std::min(P[d], D[d] / 2);

            ll y = std::min(P[i], D[i] / 2);

            ans += x + y;

            P[d] -= x;

            D[d] -= 2 * x;

            P[i] -= y;

            D[i] -= 2 * y;

        }

        else {

            ll m = D[i] / 2;

            ans += m;

            D[i] -= 2 * m;

            ll x = std::min(P[i], D[i] / 2);

            ans += x;

            P[i] -= x;

            D[i] -= 2 * x;

        }

    }

    cout << ans << endl;

    return 0;

}

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

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;



#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key



typedef long long ll;

typedef pair<ll,ll> ii;

typedef vector<int> vi;

typedef long double ld; 

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



int n,m;

map<int,int> cnt[100001];

vi vec[100001];



int main()

{

	ios_base::sync_with_stdio(0); cin.tie(0);

	cin>>n>>m;

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

	{

		int x; cin >> x;

		cnt[x%m][x]++;

	}

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

	{

		for(mit it = cnt[i].begin(); it != cnt[i].end(); it++)

		{

			vec[i].pb(it->se);

		}

	}

	int ans = 0;

	for(int i = 0; 2*i <= m; i++)

	{

		if(i==0||i==m-i)

		{

			int sum=0;

			for(int j = 0; j < vec[i].size(); j++)

			{

				sum+=vec[i][j];

			}

			ans+=sum/2;

		}

		else

		{

			int clr1 = 0;

			int clr2 = 0;

			int sum1 = 0;

			int sum2 = 0;

			for(int j = 0; j < vec[i].size(); j++)

			{

				sum1 += vec[i][j];

				clr1 += (vec[i][j]/2);

			}

			for(int j = 0; j < vec[m-i].size(); j++)

			{

				sum2 += vec[m-i][j];

				clr2 += (vec[m-i][j]/2);

			}

			if(sum1>=sum2)

			{

				int mindel = min(clr1, (sum1-sum2)/2);

				sum1 -= 2*mindel;

				ans += min(sum1,sum2) + mindel;

			}

			else

			{

				int mindel = min(clr2, (sum2-sum1)/2);

				sum2 -= 2*mindel;

				ans += min(sum1,sum2) + mindel;

			}

		}

	}

	cout<<ans<<'\n';

}


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

using namespace std;

int n,m,b[100010],d[100010],c[100010];

int main(){

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

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

		int x;

		scanf("%d",&x);

		b[x%m]++;

		c[x]++;

		if(c[x]%2==0)d[x%m]++;

	}

	int ans=0;

	for(int x=0;x<m;x++){

		int y=m-x;

		if(y==x||y==m)ans+=b[x]/2;

		else{

			ans+=min(b[x],b[y]);

			if(b[x]<b[y])ans+=min((b[y]-b[x])/2,d[y]);

			else ans+=min((b[x]-b[y])/2,d[x]);

		}



		//printf("%d %d %d %d %d %d %d\n",x,y,b[x],b[y],d[x],d[y],ans);

		b[x]=b[y]=0;

		d[x]=d[y]=0;

	}

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

	return 0;

}


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

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

using namespace __gnu_pbds;



#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fbo find_by_order

#define ook order_of_key



typedef long long ll;

typedef pair <int, int> pii;

typedef pair <ll, ll> pll;

typedef pair <ll, int> pli;

typedef vector<int> vi;

typedef vector<ll> vl;

typedef long double ld;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

typedef set<int>::iterator sit;

typedef map<int,int>::iterator mit;

typedef vector<int>::iterator vit;



long long INF=numeric_limits<long long>::max();



int main()

{

    ios_base::sync_with_stdio(0); cin.tie(0);

    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

    ll n,m,ans(0);

    cin >> n >> m;

    ll mod[m],same[100001],smod[m];

    memset(mod,0,sizeof(mod));

    memset(smod,0,sizeof(smod));

    memset(same,0,sizeof(same));

    vector< ll > x(n);

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

    {

        cin >> x[i];

        same[x[i]]++;

    }

    for(ll i = 1; i <= 100000; i++)

    {

        ll a = i%m;

        mod[a]+=same[i];

        smod[a]+=same[i]/2;

    }

    ans += mod[0]/2;

    if(m%2==0)ans += mod[m/2]/2;

    for(ll i = 1; i < (m+1)/2; i++)

    {

        ll j = m-i;

        //cout << mod[i] << " " << mod[j] << endl;

        if(mod[i]==mod[j])

        {

            ans += mod[i];

        }

        else if(mod[i]>mod[j])

        {

            ans += mod[j];

            ll left = mod[i] - mod[j];

            //cout << left/2 << " " << smod[i] << endl;

            left = min(left/2,smod[i]);

            ans += left;

        }

        else

        {

            ans += mod[i];

            ll left = mod[j] - mod[i];

            left = min(left/2,smod[j]);

            ans += left;

        }

    }

    cout << ans << endl;

}

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

using namespace std;

int n,m,b[100010],d[100010],c[100010];

int main(){

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

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

		int x;

		scanf("%d",&x);

		b[x%m]++;

		c[x]++;

		if(c[x]%2==0)d[x%m]++;

	}

	int ans=0;

	for(int x=0;x<m;x++){

		int y=m-x;

		if(y==x||y==m)ans+=b[x]/2;

		else{

			ans+=min(b[x],b[y]);

			if(b[x]<b[y])ans+=min((b[y]-b[x])/2,d[y]);

			else ans+=min((b[x]-b[y])/2,d[x]);

		}



		//printf("%d %d %d %d %d %d %d\n",x,y,b[x],b[y],d[x],d[y],ans);

		b[x]=b[y]=0;

		d[x]=d[y]=0;

	}

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

	return 0;

}


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

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define fin(x) freopen(x,"r",stdin)

#define fout(x) freopen(x,"w",stdout)

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

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const ll INF=0x3f3f3f3f3f3f3f3f;

const ll inf=0xc0c0c0c0c0c0c0c0;

const double pi=acos(-1);

const int MAXM=1e5+7;

typedef map<int,int>::iterator IT;

int N,M,cnt;

map<int,int> tool[MAXM];

int odd[MAXM],pir[MAXM];

void solve(int a,int b)

{

	if(odd[a]>odd[b])

	{

		swap(odd[a],odd[b]);

		swap(pir[a],pir[b]);

	}

	int left=odd[b]-odd[a];

	int k=min(left>>1,pir[a]);

	odd[a]+=k<<1;

	pir[a]-=k;

	cnt+=odd[a];

	cnt+=pir[b]+pir[a];

}

void solve(int x)

{

	cnt+=pir[x];

	cnt+=odd[x]>>1;

}



int main()

{

	scanf("%d%d",&N,&M);

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

	{

		int x;

		scanf("%d",&x);

		tool[x%M][x]++;

	}

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

	{

		for(IT it=tool[i].begin();it!=tool[i].end();it++)

		{

			pir[i]+=it->se>>1;

			if(it->se&1)

			{

				it->se--;

				odd[i]++;

			}

		}

	}

	cnt=0;

	solve(0);

	if((M&1)==0)solve(M>>1);

	for(int i=1;i<=((M-1)>>1);i++)

		solve(i,M-i);

	

	printf("%d",cnt);

	return 0;

}

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

using namespace std;

int n,m,b[100010],d[100010],c[100010];

int main(){

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

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

		int x;

		scanf("%d",&x);

		b[x%m]++;

		c[x]++;

		if(c[x]%2==0)d[x%m]++;

	}

	int ans=0;

	for(int x=0;x<m;x++){

		int y=m-x;

		if(y==x||y==m)ans+=b[x]/2;

		else{

			ans+=min(b[x],b[y]);

			if(b[x]<b[y])ans+=min((b[y]-b[x])/2,d[y]);

			else ans+=min((b[x]-b[y])/2,d[x]);

		}



		//printf("%d %d %d %d %d %d %d\n",x,y,b[x],b[y],d[x],d[y],ans);

		b[x]=b[y]=0;

		d[x]=d[y]=0;

	}

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

	return 0;

}


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



using namespace std;



#define pb push_back

#define all(s) s.begin(), s.end()



const int N = (int)1e5 + 7;



int x[N];

int used[N];

int u[N];

int mx[N];

int ans;

vector < int > v[N];



main() {

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

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

        scanf ("%d", x + i);

        u[x[i]]++;

        int y = x[i] % m;

        used[y]++;

    }

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

        if (u[i] != 0) v[i % m].pb(u[i]);

    }

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

        sort(all(v[i]));

    }

    if (m % 2 == 0) {

        ans = used[m / 2] / 2;

        used[m / 2] %= 2;

    }

    ans += used[0] / 2;

    used[0] %= 2;

    int l = 1, r = m - 1;

    while (l < r) {

        int mn = min(used[l], used[r]);

        ans += mn;

        used[l] -= mn;

        used[r] -= mn;

        l++; r--;

    }

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

        for (int j = (int)v[i].size() - 1; j >= 0; j--) {

            if (used[i] - v[i][j] <= 0) {

                v[i][j] = used[i];

                ans += v[i][j] / 2;

                break;

            }

            ans += v[i][j] / 2;

            used[i] -= v[i][j] / 2 * 2;

        }

    }

    cout << ans;

}


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

#include<iostream>

#include<cstring>

#include<algorithm>

#define RG register

using namespace std;

const int N=1e5+10;

int n,m,num[N],ans,cnt[N],bck[N],cs[N],maxx[N];

inline int read(){

	char ch=getchar(); int x=0, f=1;

	while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();	}

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

	return x*f;}

inline bool cmp(int a,int b){return a%m<b%m;}

inline int mx(int a,int b){return a>b ? a : b ;}

inline int mi(int a,int b){return a<b ? a : b ;}

int main()

{

//	freopen("Pair Cards.in","r",stdin);

	//freopen(".out","w",stdout);

	n=read(); m=read();

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

	{

		num[i]=read();//%m;

		cnt[num[i]%m]++;

		bck[num[i]]++;

	}

	ans+=cnt[0]/2;//printf("%d\n",ans);

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

	{

		if(i==m-i) 

		{

			ans+=cnt[i]/2;

			cnt[i]=1;

			continue;

		}

		int minn=mi(cnt[i],cnt[m-i]);

		ans+=minn;

		cnt[i]-=minn; cnt[m-i]-=minn;

	}

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

	{

		cnt[i]/=2;

		for(int j=i;j<=100000 && cnt[i]>0;j+=m)

		{

			ans+=mi(cnt[i], bck[j]/2);

			cnt[i]-=bck[j]/2;

		}

	}

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

	//fclose(stdin); fclose(stdout);

	return 0;

}

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

#include<math.h>

#include<ctype.h>

#include<algorithm>

#include<bitset>

#include<cassert>

#include<cctype>

#include<cerrno>

#include<cfloat>

#include<ciso646>

#include<climits>

#include<clocale>

#include<complex>

#include<csetjmp>

#include<csignal>

#include<cstdarg>

#include<cstddef>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cwchar>

#include<cwctype>

#include<deque>

#include<exception>

#include<fstream>

#include<functional>

#include<iomanip>

#include<ios>

#include<iosfwd>

#include<iostream>

#include<istream>

#include<iterator>

#include<limits>

#include<list>

#include<locale>

#include<map>

#include<memory>

#include<new>

#include<numeric>

#include<ostream>

#include<queue>

#include<set>

#include<sstream>

#include<stack>

#include<stdexcept>

#include<streambuf>

#include<string>

#include<typeinfo>

#include<utility>

#include<valarray>

#include<vector>

#include<string.h>

#include<stdlib.h>

#include<stdio.h>

#define ll   long long

#define pb push_back

#define mp make_pair

#define F first

#define S second

#define MAX 100000000000000000

#define MOD 1000000007

#define files  freopen("OUTPUT.TXT","r",stdin);

#define PI 3.141592653589793238462

#define INF 1000000000

using namespace std;

int n,mx,dp[100005];

vector<int> v[100005];

void dfs(int x,int fa){

	dp[x]=0;

	int need=v[x].size()-1,cnt=0;

	for (int i=0;i<v[x].size();i++){

		int u=v[x][i];

		if (u==fa) continue;

		dfs(u,x);

		dp[x]+=dp[u];

		cnt+=(dp[u]!=0);

	}

	dp[x]+=max(0,(int)v[x].size()-(fa!=(-1))-cnt-1);

}

int main(){

	//freopen("input.txt","r",stdin);

	//freopen("output.txt","w",stdout);

	cin>>n;

	if (n==2){

		cout<<1;

		return 0;

	}

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

		int p,q;

		cin>>p>>q;

		v[p].pb(q);

		v[q].pb(p);

	}

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

		if (v[i].size()>v[mx].size()) mx=i;

	}

	dfs(mx,-1);

	cout<<dp[mx];

	return 0;

}


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

using namespace std;



const int maxn=100010;

int du[maxn];

int n,root;

struct Edge

{

	int v,next;

}	e[maxn<<1];

int g[maxn],tot;

int fa[maxn];

bool has[maxn];

int ans;

void addedge(int x,int y)

{

	tot++;

	e[tot].v=y;

	e[tot].next=g[x];

	g[x]=tot;

}

void dfs(int t)

{

	int son=du[t];

	if (fa[t]!=0)	son--;

	for (int i=g[t];i;i=e[i].next)

	if (e[i].v!=fa[t])

	{

		fa[e[i].v]=t;

		dfs(e[i].v);

		if (has[e[i].v])	son--,has[t]=true;

	}

	if (son>1)

	{

		ans+=son-1;

		has[t]=true;

	}

}

int main()

{

	scanf("%d",&n);

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

	{

		int x,y;

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

		x++;y++;

		addedge(x,y);

		addedge(y,x);

		du[x]++;

		du[y]++;

		if (du[x]>2)	root=x;

	}

	if (!root)

	{

		printf("1\n");

		return 0;

	}

	ans=0;

	fa[root]=0;

	dfs(root);

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

	return 0;

}

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

#include<cctype>

#include<queue>

#include<cstdio>

#include<cmath>

#include<sstream>

#include<string>

#include<algorithm>

#include<cstring>

#include<vector>

#include<ctime>

#include<cstdlib>

#include<map>

#include<utility>

#include<iomanip>

#include<set>

#include<stack>

#define lowbit(i) ((i)&(-i))

using namespace std;

typedef long long ll;typedef pair<int,int> pii;

typedef pair<ll,ll> pll;typedef vector<string> vss;

typedef vector<int> vii;typedef vector<pii> vpi;

typedef vector<ll> vll;typedef vector<pll> vpl;typedef long double ld;

typedef unsigned long long ul;typedef queue<int> qii;typedef queue<pii> qpi;

int n,x,y,dp[100005],start;

vii v[100005],tmp;

void dfs(int now,int par){

	int ret=0,c=0;

	for(int i=0;i<v[now].size();i++){

		int to=v[now][i];

		if(to==par) continue;

		dfs(to,now);

	}

	tmp.clear();

	for(int i=0;i<v[now].size();i++){

		int to=v[now][i];

		if(to==par) continue;

		if(!dp[to]) c++;

		else ret+=dp[to];

	}

	ret+=max(0,c-1);

	dp[now]=ret;

}

int mx=0;

int main()

{

// 	freopen("","r",stdin);

// 	freopen("","w",stdout);

	cin>>n;

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

		cin>>x>>y;

		v[x].push_back(y);

		v[y].push_back(x);

	}

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

		if(v[i].size()>mx){

			mx=v[i].size();

			start=i;

		}

	}

	if(mx<=2){

		puts("1");

		return 0;

	}

	dfs(start,-1);

//	for(int i=0;i<n;i++) cout<<dp[i]<<' ';cout<<'\n';

	cout<<dp[start]<<'\n';

	return 0;

}

/*

17

0 1

0 2

0 3

1 4

1 5

4 10

4 11

2 6

6 12

6 13

3 7

3 8

3 9

8 16

16 14

16 15

*/

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

using namespace std;



const int maxn=100010;

int du[maxn];

int n,root;

struct Edge

{

	int v,next;

}	e[maxn<<1];

int g[maxn],tot;

int fa[maxn];

bool has[maxn];

int ans;

void addedge(int x,int y)

{

	tot++;

	e[tot].v=y;

	e[tot].next=g[x];

	g[x]=tot;

}

void dfs(int t)

{

	int son=du[t];

	if (fa[t]!=0)	son--;

	for (int i=g[t];i;i=e[i].next)

	if (e[i].v!=fa[t])

	{

		fa[e[i].v]=t;

		dfs(e[i].v);

		if (has[e[i].v])	son--,has[t]=true;

	}

	if (son>1)

	{

		ans+=son-1;

		has[t]=true;

	}

}

int main()

{

	scanf("%d",&n);

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

	{

		int x,y;

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

		x++;y++;

		addedge(x,y);

		addedge(y,x);

		du[x]++;

		du[y]++;

		if (du[x]>2)	root=x;

	}

	if (!root)

	{

		printf("1\n");

		return 0;

	}

	ans=0;

	fa[root]=0;

	dfs(root);

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

	return 0;

}

// Fastest known solution for this problem: