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

#include<vector>



using namespace std;

#define MAX 100000000

#define Is 110

int n, k,req, a, b, c, d, e, i ,j, map[Is][Is], ans;





int dik(int s, int g){

  vector<int> cost(Is, MAX), f(Is, 0);

  cost[s] = 0;

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

    f[s] = 1;

    for(j = 0; j < Is; j++) if(!f[j] && map[s][j] != MAX && cost[j] > cost[s] + map[s][j]) cost[j] = cost[s] + map[s][j];

    int min = MAX + 1;

    for(j = 0; j < Is; j++) if(!f[j] && min > cost[j]) min = cost[s = j];

  }

  return cost[g];

}



int main(){

  

  while(cin >> n >> k, n != 0 || k != 0) { 

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

      for(j = 0; j < Is; j++) {

	map[i][j] = MAX;

      }

    }

    

    while(k--){

      cin >> req;

      

      if(req){

	cin >> c >> d >> e;

	if(e < map[c][d]) map[c][d] = map[d][c] = e;

      }

      

      else{

	cin >> a >> b;

	if((ans = dik(a, b)) != MAX) cout << ans << endl;

	else cout << "-1" << endl;

      }

    }

    

  }

  return 0;

}

  

  

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

#include<algorithm>



using namespace std;



#define INF 100000000



int s, e, r, m;



int dijk(int d[][101]) {

  int mi, i, j;

  int c[m + 1] = {};

    

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

    c[i] = INF;

  }

    

  int f[m + 1] = {};

  mi = s;

  c[s] = 0;



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

    f[mi] = 1;



    for(j = 0; j <= m; j++) {

      if(f[j] == 1) continue;

      if(c[j] > d[mi][j] + c[mi]) {

	c[j] = d[mi][j] + c[mi];

      }

    }



    int MIN = INF * 2;



    for(j = 0; j <= m; j++) {

      if(f[j] == 1) continue;

      if(MIN > c[j]) {

	MIN = c[j];

	mi = j;

      }

    }

  }

  if(c[e] == INF) return -1;

  return c[e];

}



  

int main() {

  int i, j, r, k, a,b, cost;

  while(cin >> m >> k, k != 0 || m != 0) {

    int d[101][101] = {};

    

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

      for(j = 0;j <= m; j++) {

	d[i][j]  = INF;

      }

    }

    

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

      cin >> r;

      if(r == 1) {

	cin >> a >> b >> cost;

	d[a][b] = d[b][a] = min(cost, d[a][b]);

     }

      else {

	cin >> s >> e;

	cout << dijk(d) << endl;

      }

    }

    

  }

  return 0;

}

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

#include<cstring>

#include<algorithm>

using namespace std;



int main(){

	int n,k;

	int x[101][101];

	int a,b,c,d,e;

	int y[101][101];

	int p;

	int sum=1000000000;

	bool s[101];

	int h[101];

	int h2[101][201];



	while(true){

		memset(x,127,sizeof(x));

		memset(s,false,sizeof(s));

		memset(h,0,sizeof(h));

		cin>>n>>k;

		if(n==0 && k==0){

			break;

		}

		e=n;

		sum=1000000000;

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

			memset(y,127,sizeof(y));

			sum=1000000000;

			p=10000000;

			cin>>a;

			if(a==0){

				cin>>b>>c;

				y[0][b]=0;

				if(s[c]==true && s[b]==true){

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

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

							if(y[j-1][l]<100000000){

								for(int m=1;m<=h[l];m++){

									if(x[l][h2[l][m]]<100000000){

										y[j][h2[l][m]]=min(y[j][h2[l][m]],y[j-1][l]+x[l][h2[l][m]]);

									}

								}

							}

						}

					}

				}

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

					sum=min(sum,y[j][c]);

				}

				if(sum>=1000000000){

					sum=-1;

				}

				cout<<sum<<endl;

			}



			if(a==1){

				cin>>b>>c>>d;

				x[b][c]=min(x[b][c],d);

				x[c][b]=min(x[c][b],d);

				s[c]=true;

				s[b]=true;

				h[b]++;

				h[c]++;

				h2[b][h[b]]=c;

				h2[c][h[c]]=b;

			}

		}

	}

	return 0;

}

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

using namespace std;

int dist[105],n,m,a,b,c,d;

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q;

vector<pair<int,int> >x[105];

void add_edge(int a1,int a2,int a3){

    x[a1].push_back(make_pair(a2,a3));

    x[a2].push_back(make_pair(a1,a3));

}

int solve(int b1,int b2){

    for(int i=0;i<105;i++)dist[i]=100000000;dist[b1]=0;

    Q.push(make_pair(0,b1));

    while(!Q.empty()){

        int a1=Q.top().first,a2=Q.top().second;Q.pop();

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

            int to=x[a2][i].first,len=x[a2][i].second;

            if(dist[to]>a1+len){

                dist[to]=a1+len;

                Q.push(make_pair(dist[to],to));

            }

        }

    }

    if(dist[b2]==100000000)return -1;

    return dist[b2];

}

int main(){

    while(true){

        cin>>n>>m;for(int i=0;i<105;i++)x[i].clear();

        if(n==0 && m==0)break;

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

            cin>>a;

            if(a==0){cin>>b>>c;cout<<solve(b,c)<<endl;}

            if(a==1){cin>>b>>c>>d;add_edge(b,c,d);}

        }

    }

}

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

#include<cstdio>

#include<algorithm>

using namespace std;

long long int cost[101][101],k,n,a,b,c,d,e,which,go[101];

bool used[101];

void dij(int s){

    fill(go,go+101,10000000);

    fill(used,used+101,false);

    go[s]=0;

    while(true){

        int v=-1;

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

            if(!used[i]&&(v==-1||go[i]<go[v]))v=i;

        }

        if(v==-1)break;

        used[v]=true;

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

            go[i]=min(go[i],go[v]+cost[v][i]);

        }

    }

}

int main(){

    for(;;){

        cin>>n>>k;

        if(n==0&&k==0)break;

        fill(cost[0],cost[0]+101*101,10000000);

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

            cin>>which;

            if(!which){

                cin>>a>>b;

                dij(a-1);

                if(go[b-1]!=10000000)cout<<go[b-1]<<endl;

                else cout<<-1<<endl;

            }

            else {

                cin>>c>>d>>e;

                cost[c-1][d-1]=min(cost[c-1][d-1],e);

                cost[d-1][c-1]=min(cost[d-1][c-1],e);

            }

        }

    }

    return 0;

}

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

#include<cstdio>

#include<algorithm>

#include<string>

#include<vector>

#include<queue>

#define int long long

using namespace std;

int cost[101][101];

int d[101];

bool used[101];

int V,k,o,a,b,c,di,e,ans;

void dij(int s){

    fill(d,d+101,10000000);

    fill(used,used+101,false);

    d[s]=0;

    while(true){

        int v=-1;

        for(int u=0;u<V;u++){

            if(!used[u]&&(v==-1||d[u]<d[v]))v=u;

        }

        if(v==-1)break;

        used[v]=true;

        for(int u=0;u<V;u++){

            d[u]=min(d[u],d[v]+cost[v][u]);

        }

    }

}

signed main(){

    for(;;){

        cin>>V>>k;

        if(V==0&&k==0)break;

        fill(cost[0],cost[0]+101*101,10000000);

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

            cin>>o;

            if(o==1){

                cin>>c>>di>>e;

                cost[c-1][di-1]=min(cost[c-1][di-1],e);

                cost[di-1][c-1]=min(cost[di-1][c-1],e);

            }

            if(o==0){

                cin>>a>>b;

                dij(a-1);

                if(d[b-1]==10000000)cout<<-1<<endl;

                else cout<<d[b-1]<<endl;

            }

        }

    }

    return 0;

}

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

#include <map>

#include <vector>

using namespace std;



const int N = 2e5 + 5;

int pa1[N], pa2[N];

int find(int* p, int v) { return v == p[v] ? v : p[v] = find(p, p[v]); }

void unite(int* p, int a, int b) { p[find(p, b)] = find(p, a); }



typedef long long LL;

int n, k, l;

// vector<int> e1[N], e2[N];



map<LL, int> mp;



int main() {

#ifdef D

    freopen("a.in", "r", stdin);

#endif

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

        pa1[i] = pa2[i] = i;

    }

    scanf("%d%d%d", &n, &k, &l);

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

        int a, b;

        scanf("%d%d", &a, &b);

        unite(pa1, a, b);

        // e1[a].push_back(b);

        // e1[b].push_back(a);

    }

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

        int a, b;

        scanf("%d%d", &a, &b);

        unite(pa2, a, b);

        // e2[a].push_back(b);

        // e2[b].push_back(a);

    }



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

        mp[find(pa1, i) * (LL)(n + 1) + find(pa2, i)] += 1;

    }



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

        printf("%d ", mp[find(pa1, i) * (LL)(n + 1) + find(pa2, i)]);

    }

    puts("");



    return 0;

}


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

#include<string.h>

#include<set>

#include<stdlib.h>

#include<algorithm>

using namespace std;

int n,m1,m2;

int a1[400005],a2[400005];

int f1(int i){

	if(i==a1[i])return i;

	return a1[i]=f1(a1[i]);

}

int f2(int i){

	if(i==a2[i])return i;

	return a2[i]=f2(a2[i]);

}



long long line[1400005],g[400005],h[4000005],num;

int find(long long k){

	int i=1,mid,j=num;

	while(j-i>1){

		mid=(i+j)/2;

		if(k>line[mid])

		     i=mid;

		else j=mid;

		

	}

	if(line[i]==k)return h[i];

	return h[j];

	

}

int main(){

	

	scanf("%d%d%d",&n,&m1,&m2);

	for(int q=1;q<=n;q++)a1[q]=a2[q]=q;

	for(int q=1;q<=m1;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a1[f1(i)]=f1(j);

		

	}

	for(int q=1;q<=m2;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a2[f2(i)]=f2(j);

		

	}

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

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		g[q]=ppp;

		

	}

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

	

	for(int q=1;q<=n;){

		

		line[++num]=g[q];

		int z=1;

		q++;

		while(g[q]==g[q-1]){

			q++;z++;

		}

		h[num]=z;

		if(q>n)break;

	}

	

	

	for(int q=1;q<=1;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf("%d",ans);

		

	}

	for(int q=2;q<=n;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf(" %d",ans);

		

	}

	printf("\n");

	

	return 0;

}

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

using namespace std;



const int maxn = 200010;



int fa1[maxn], fa2[maxn], r1[maxn], r2[maxn];



map<pair<int, int>, int> mp;



void kexin_init() {

	for (int i=1; i<=maxn; ++i) {fa1[i] = i; fa2[i] = i;}

	memset(r1, 0, sizeof r1);

	memset(r2, 0, sizeof r2);

}



int kexin_find_road(int x) {

	if (fa1[x] == x) return x;

	return fa1[x] = kexin_find_road(fa1[x]);

}

void kexin_Union_road(int x, int y) {

	x = kexin_find_road(x);

	y = kexin_find_road(y);

	if (x == y) return ;

	if (r1[x] < r1[y]) swap(x, y);

	fa1[y] = x;

	if (r1[x] == r1[y]) r1[x]++;

}



int kexin_find_railway(int x) {

	if (fa2[x] == x) return x;

	return fa2[x] = kexin_find_railway(fa2[x]);

}

void kexin_Union_railway(int x, int y) {

	x = kexin_find_railway(x);

	y = kexin_find_railway(y);

	if (x == y) return ;

	if (r2[x] < r2[y]) swap(x, y);

	fa2[y] = x;

	if (r2[x] == r2[y]) r2[x]++;

}

int main() {

	int n, k, l;

	scanf("%d%d%d", &n, &k, &l);

	

	kexin_init();

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

		int x, y;

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

		kexin_Union_road(x, y);

	}

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

		int x, y;

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

		kexin_Union_railway(x, y);

	}

	

	mp.clear();



	for (int i=1; i<=n; ++i) mp[make_pair(kexin_find_road(i), kexin_find_railway(i))]++;

	for (int i=1; i<n; ++i) printf("%d ", mp[make_pair(kexin_find_road(i), kexin_find_railway(i))]);

	printf("%d\n", mp[make_pair(kexin_find_road(n), kexin_find_railway(n))]);



	return 0;

}

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

#include<string.h>

#include<set>

#include<stdlib.h>

#include<algorithm>

using namespace std;

int n,m1,m2;

int a1[400005],a2[400005];

int f1(int i){

	if(i==a1[i])return i;

	return a1[i]=f1(a1[i]);

}

int f2(int i){

	if(i==a2[i])return i;

	return a2[i]=f2(a2[i]);

}



long long line[1400005],g[400005],h[4000005],num;

int find(long long k){

	int i=1,mid,j=num;

	while(j-i>1){

		mid=(i+j)/2;

		if(k>line[mid])

		     i=mid;

		else j=mid;

		

	}

	if(line[i]==k)return h[i];

	return h[j];

	

}

int main(){

	

	scanf("%d%d%d",&n,&m1,&m2);

	for(int q=1;q<=n;q++)a1[q]=a2[q]=q;

	for(int q=1;q<=m1;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a1[f1(i)]=f1(j);

		

	}

	for(int q=1;q<=m2;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a2[f2(i)]=f2(j);

		

	}

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

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		g[q]=ppp;

		

	}

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

	

	for(int q=1;q<=n;){

		

		line[++num]=g[q];

		int z=1;

		q++;

		while(g[q]==g[q-1]){

			q++;z++;

		}

		h[num]=z;

		if(q>n)break;

	}

	

	

	for(int q=1;q<=1;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf("%d",ans);

		

	}

	for(int q=2;q<=n;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf(" %d",ans);

		

	}

	printf("\n");

	

	return 0;

}

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

using namespace std;

#define LL long long

const int maxn = 2e5+10;

int n, k, l;

map<LL, int> num;

int fa[3][maxn];

LL Find (int x, int mod) {

    if (fa[mod][x] == x) return x;

    else return fa[mod][x] = Find (fa[mod][x], mod);

}

void Comb (int x, int y, int mod) {

    fa[mod][Find(x, mod)] = Find (y, mod);

}

LL id (int x) {

    return Find(x,0) * 1e6 + Find (x, 1);

}

int main (void) {

    scanf ("%d%d%d", &n, &k, &l);

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

        fa[0][i] = i;

        fa[1][i] = i;

    }

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

        int a, b;

        scanf ("%d%d", &a, &b);

        Comb (a, b, 0);

    }

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

        int a, b;

        scanf ("%d%d", &a, &b);

        Comb (a, b, 1);

    };

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

        num[id(i)]++;

    }

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

        printf ("%d", num[id(i)]);

        if (i != n) printf (" ");

        else printf ("\n");

    }

    return 0;

}


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

#include<string.h>

#include<set>

#include<stdlib.h>

#include<algorithm>

using namespace std;

int n,m1,m2;

int a1[400005],a2[400005];

int f1(int i){

	if(i==a1[i])return i;

	return a1[i]=f1(a1[i]);

}

int f2(int i){

	if(i==a2[i])return i;

	return a2[i]=f2(a2[i]);

}



long long line[1400005],g[400005],h[4000005],num;

int find(long long k){

	int i=1,mid,j=num;

	while(j-i>1){

		mid=(i+j)/2;

		if(k>line[mid])

		     i=mid;

		else j=mid;

		

	}

	if(line[i]==k)return h[i];

	return h[j];

	

}

int main(){

	

	scanf("%d%d%d",&n,&m1,&m2);

	for(int q=1;q<=n;q++)a1[q]=a2[q]=q;

	for(int q=1;q<=m1;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a1[f1(i)]=f1(j);

		

	}

	for(int q=1;q<=m2;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a2[f2(i)]=f2(j);

		

	}

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

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		g[q]=ppp;

		

	}

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

	

	for(int q=1;q<=n;){

		

		line[++num]=g[q];

		int z=1;

		q++;

		while(g[q]==g[q-1]){

			q++;z++;

		}

		h[num]=z;

		if(q>n)break;

	}

	

	

	for(int q=1;q<=1;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf("%d",ans);

		

	}

	for(int q=2;q<=n;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf(" %d",ans);

		

	}

	printf("\n");

	

	return 0;

}

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

#include <iostream>

#include <algorithm>

#include <map>



using namespace std;



typedef long long LL;



#define MAXN 200010



int n, k, l;

int f1[MAXN], f2[MAXN];

map<pair<int, int> , int> m;



int Find(int *f, int u)

{

    return f[u] ? f[u] = Find(f, f[u]) : u;

}



void Init()

{

    int i, u, v, fu, fv;

    scanf("%d %d %d", &n, &k, &l);

    for(i = 1; i <= k; ++i){

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

        fu = Find(f1, u);

        fv = Find(f1, v);

        if(fu == fv) continue;

        f1[fv] = fu;

    }

    for(i = 1; i <= l; ++i){

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

        fu = Find(f2, u);

        fv = Find(f2, v);

        if(fu == fv) continue;

        f2[fv] = fu;

    }

}



void Work()

{

    int i;

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

        ++m[{Find(f1, i), Find(f2, i)}];

    }

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

        printf("%d ", m[{Find(f1, i), Find(f2, i)}]);

    }

    printf("%d\n", m[{Find(f1, i), Find(f2, i)}]);

}



int main()

{

    Init();

    Work();

    return 0;

}


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

#include<string.h>

#include<set>

#include<stdlib.h>

#include<algorithm>

using namespace std;

int n,m1,m2;

int a1[400005],a2[400005];

int f1(int i){

	if(i==a1[i])return i;

	return a1[i]=f1(a1[i]);

}

int f2(int i){

	if(i==a2[i])return i;

	return a2[i]=f2(a2[i]);

}



long long line[1400005],g[400005],h[4000005],num;

int find(long long k){

	int i=1,mid,j=num;

	while(j-i>1){

		mid=(i+j)/2;

		if(k>line[mid])

		     i=mid;

		else j=mid;

		

	}

	if(line[i]==k)return h[i];

	return h[j];

	

}

int main(){

	

	scanf("%d%d%d",&n,&m1,&m2);

	for(int q=1;q<=n;q++)a1[q]=a2[q]=q;

	for(int q=1;q<=m1;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a1[f1(i)]=f1(j);

		

	}

	for(int q=1;q<=m2;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a2[f2(i)]=f2(j);

		

	}

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

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		g[q]=ppp;

		

	}

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

	

	for(int q=1;q<=n;){

		

		line[++num]=g[q];

		int z=1;

		q++;

		while(g[q]==g[q-1]){

			q++;z++;

		}

		h[num]=z;

		if(q>n)break;

	}

	

	

	for(int q=1;q<=1;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf("%d",ans);

		

	}

	for(int q=2;q<=n;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf(" %d",ans);

		

	}

	printf("\n");

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//created by missever



#include<bits/stdc++.h>

#define MAX 1000000007

using namespace std;

typedef long long LL;



typedef pair<int,int> P;

const int maxn = 200005;

int p1[maxn],p2[maxn],t[maxn];

map<P,int> q;



int ff(int f[],int x)

{

    if(f[x] != x) f[x] = ff(f,f[x]);

    return f[x];

}



int main(){

    int n,k,l,i,u,v,a,b;

    scanf("%d%d%d",&n,&k,&l);

    for(i = 0;i <= n; i++) p1[i] = p2[i] = i;

    for(i = 0;i < k; i++)

    {

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

        a = ff(p1,u);

        b = ff(p1,v);

        if(a != b) p1[a] = b;

    }

    for(i = 0;i < l; i++)

    {

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

        a = ff(p2,u);

        b = ff(p2,v);

        if(a != b) p2[a] = b;

    }

    for(i = 1;i <= n; i++) q[P(ff(p1,i),ff(p2,i))]++;

    for(i = 1;i <= n; i++) printf("%d%c",q[P(ff(p1,i),ff(p2,i))]," \n"[i == n]);

    return 0;

}


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

#include<string.h>

#include<set>

#include<stdlib.h>

#include<algorithm>

using namespace std;

int n,m1,m2;

int a1[400005],a2[400005];

int f1(int i){

	if(i==a1[i])return i;

	return a1[i]=f1(a1[i]);

}

int f2(int i){

	if(i==a2[i])return i;

	return a2[i]=f2(a2[i]);

}



long long line[1400005],g[400005],h[4000005],num;

int find(long long k){

	int i=1,mid,j=num;

	while(j-i>1){

		mid=(i+j)/2;

		if(k>line[mid])

		     i=mid;

		else j=mid;

		

	}

	if(line[i]==k)return h[i];

	return h[j];

	

}

int main(){

	

	scanf("%d%d%d",&n,&m1,&m2);

	for(int q=1;q<=n;q++)a1[q]=a2[q]=q;

	for(int q=1;q<=m1;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a1[f1(i)]=f1(j);

		

	}

	for(int q=1;q<=m2;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a2[f2(i)]=f2(j);

		

	}

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

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		g[q]=ppp;

		

	}

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

	

	for(int q=1;q<=n;){

		

		line[++num]=g[q];

		int z=1;

		q++;

		while(g[q]==g[q-1]){

			q++;z++;

		}

		h[num]=z;

		if(q>n)break;

	}

	

	

	for(int q=1;q<=1;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf("%d",ans);

		

	}

	for(int q=2;q<=n;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf(" %d",ans);

		

	}

	printf("\n");

	

	return 0;

}

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

using namespace std;

map<pair<int,int>,int>v;

const int MAX = 2e5 +5;

int rail[MAX],road[MAX];



int road_f(int x) {

  if (road[x] == x)return x;

  else return road[x] = road_f(road[x]);

}

int rail_f(int x) {

  if (rail[x] == x)return x;

  else return rail[x] = rail_f(rail[x]);

}

int main() {

  int n,k,l,x,y;

  scanf("%d%d%d",&n,&k,&l);

  for (int i = 1; i <= n; ++i)road[i] = rail[i] = i;

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

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

    x = road_f(x),y = road_f(y);

    road[x] = y;

  }

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

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

    x = rail_f(x),y = rail_f(y);

    rail[x] = y;

  }

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

    road[i] = road_f(i);

    rail[i] = rail_f(i);

    v[make_pair(road[i],rail[i])]++;

  }

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

    printf("%d ",v[make_pair(road[i],rail[i])]);

  }

  printf("%d\n",v[make_pair(road[n],rail[n])]);

}

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

#include<string.h>

#include<set>

#include<stdlib.h>

#include<algorithm>

using namespace std;

int n,m1,m2;

int a1[400005],a2[400005];

int f1(int i){

	if(i==a1[i])return i;

	return a1[i]=f1(a1[i]);

}

int f2(int i){

	if(i==a2[i])return i;

	return a2[i]=f2(a2[i]);

}



long long line[1400005],g[400005],h[4000005],num;

int find(long long k){

	int i=1,mid,j=num;

	while(j-i>1){

		mid=(i+j)/2;

		if(k>line[mid])

		     i=mid;

		else j=mid;

		

	}

	if(line[i]==k)return h[i];

	return h[j];

	

}

int main(){

	

	scanf("%d%d%d",&n,&m1,&m2);

	for(int q=1;q<=n;q++)a1[q]=a2[q]=q;

	for(int q=1;q<=m1;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a1[f1(i)]=f1(j);

		

	}

	for(int q=1;q<=m2;q++){

		int i,j;

		scanf("%d%d",&i,&j);

		a2[f2(i)]=f2(j);

		

	}

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

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		g[q]=ppp;

		

	}

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

	

	for(int q=1;q<=n;){

		

		line[++num]=g[q];

		int z=1;

		q++;

		while(g[q]==g[q-1]){

			q++;z++;

		}

		h[num]=z;

		if(q>n)break;

	}

	

	

	for(int q=1;q<=1;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf("%d",ans);

		

	}

	for(int q=2;q<=n;q++){

		int i1=f1(q),i2=f2(q);

		long long ppp=i1;

		ppp=ppp*1000000+i2;

		int ans=find(ppp);

		printf(" %d",ans);

		

	}

	printf("\n");

	

	return 0;

}

// Fastest known solution for this problem: