stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include "stdio.h"

#include"queue"

#include "climits"

using namespace std;



queue<int>Q;



int island;

int query;

int kind;

int start;

int goal;

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

int price;

int dis[101] = {};



int main() {

	scanf("%d %d", &island, &query);

	while (island != 0) {

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

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

				connect[i][j] = INT_MAX;

			}

		}

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

			scanf("%d", &kind);

			if (kind == 1) {

				scanf("%d %d %d", &start, &goal, &price);

				if (connect[start][goal] > price) {

					connect[start][goal] = price;

					connect[goal][start] = price;

				}

			}

			else {

				scanf("%d %d", &start, &goal);

				Q.push(start);

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

					dis[i] = INT_MAX;

				}

				dis[start] = 0;

				while (!Q.empty()) {

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

						if (connect[Q.front()][i] != INT_MAX) {

							if (dis[i] > dis[Q.front()] + connect[Q.front()][i]) {

								dis[i] = dis[Q.front()] + connect[Q.front()][i];

								Q.push(i);

							}

						}

					}

					Q.pop();

				}

				if (dis[goal] == INT_MAX)printf("-1\n");

				else printf("%d\n", dis[goal]);

			}

		}

		scanf("%d %d", &island, &query);

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.742980473492339x):
#include "stdio.h"

#include "climits"



int n, m;

int edge[101][101];

int dis[101];

bool flag[101];

int box;

int s, e, p;



int main() {

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

	while (n != 0) {

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

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

				edge[i][j] = 200000000;

			}

		}

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

			scanf("%d", &box);

			if (box == 1) {

				scanf("%d %d %d", &s, &e, &p);

				if (edge[s][e] > p) {

					edge[s][e] = p;

					edge[e][s] = p;

				}

			}

			else {

				scanf("%d %d", &s, &e);

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

					flag[j] = true;

					dis[j] = 200000000;

				}

				dis[s] = 0;

				box = s;

				while (flag[e]) {

					flag[box] = false;

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

						if (dis[box] + edge[box][j] < dis[j]) {

							dis[j] = dis[box] + edge[box][j];

						}

					}

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

						if (flag[j]) {

							box = j;

							break;

						}

					}

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

						if (flag[j]) {

							if (dis[box] > dis[j])box = j;

						}

					}

				}

				if (dis[e] == 200000000)printf("-1\n");

				else printf("%d\n", dis[e]);

			}

		}

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

	}

	return 0;

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

}

  

  

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

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

}

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

        }

    }

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

}

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

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

}


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

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

}


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

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

}


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

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

}

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

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

}


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

#include <assert.h>

#include <bitset>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>

#define MP make_pair

#define ls (o << 1)

#define rs (o << 1 | 1)

#define mid ((L + R) >> 1)

#define eps (1e-5)

using namespace std;

typedef long long LL;

const LL mod = 1e9 + 7;

typedef pair<int, int> PII;

int n, k, l;

int f[200010], g[200010], h[200010], ans[200010];

int findfa(int *w, int o) {

    if (w[o] == o)

        return o;

    return w[o] = findfa(w, w[o]);

}

bool cmp(const int &o, const int &p) {

    int fa = findfa(f, o);

    int fb = findfa(f, p);

    if (fa != fb)

        return fa < fb;

    fa = findfa(h, o);

    fb = findfa(h, p);

    return fa < fb;

}

int main() {

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

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

        f[i] = i;

        g[i] = i;

        h[i] = i;

    }

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

        int u, v;

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

        int fa = findfa(f, u);

        int fb = findfa(f, v);

        f[fa] = fb;

    }

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

        int u, v;

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

        int fa = findfa(h, u);

        int fb = findfa(h, v);

        h[fa] = fb;

    }

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

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

        int j = i;

        while (j <= n && findfa(f, g[i]) == findfa(f, g[j]) &&

               findfa(h, g[i]) == findfa(h, g[j])) {

            j++;

        }

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

            ans[g[k]] = j - i;

        }

        i = j;

    }

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

        printf("%d%c", ans[i], i == n ? '\n' : ' ');

    }

    return 0;

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

}


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

}