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

#include<algorithm>

#include<vector>

#include<queue>

#define PP std::pair<int,int>

int N, M;

std::vector<int> P[100010], L[100010];

bool usedp[100010];

bool usedl[100010];

int main() {

	std::cin >> N >> M;

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

		int K;

		std::cin >> K;

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

			int tmp;

			std::cin >> tmp;

			P[i].push_back(tmp);

			L[tmp].push_back(i);

		}

	}

	std::queue<PP> q;

	q.push({ 1,1 });

	while (!q.empty()) {

		PP p = q.front();

		q.pop();

		if (p.first == 1) {

			for (auto u : P[p.second]) {

				if (!usedl[u]) {

					usedl[u] = true;

					q.push({ 0,u });

				}

			}

		}

		else {

			for (auto u : L[p.second]) {

				if (!usedp[u]) {

					usedp[u] = true;

					q.push({ 1,u });

				}

			}

		}

	}

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

		if (!usedp[i]) {

			std::cout << "NO" << std::endl;

			return 0;

		}

	}

	std::cout << "YES" << std::endl;

	return 0;

}

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

#include<algorithm>

#include<vector>

#define PP std::pair<int,int>

int N, M;

std::vector<PP> G;

int par[200010];

int rank[200010];

void init() {

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

		par[i] = i;

		rank[i] = 0;

	}

}



int find(int x) {

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

	return par[x] = find(par[x]);

}



void unite(int x, int y) {

	x = find(x);

	y = find(y);

	if (x == y)return;

	if (rank[x] < rank[y]) {

		par[x] = y;

	}

	else {

		par[y] = x;

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

	}

}



bool same(int x, int y) {

	return find(x) == find(y);

}





int main() {

	std::cin >> N >> M;

	init();

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

		int K;

		std::cin >> K;

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

			int tmp;

			std::cin >> tmp;

			G.push_back({ i,tmp + 100000 });

		}

	}

	for (auto u : G) {

		if (!same(u.first, u.second)) {

			unite(u.first, u.second);

		}

	}

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

		if (!same(i, i + 1)) {

			std::cout << "NO" << std::endl;

			return 0;

		}

	}

	std::cout << "YES" << std::endl;

	return 0;

}

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

#include <iostream>



using namespace std;



int main()

{

	string S, T;



	cin >> S >> T;



	if (S.size() >= T.size())

	{

		for (int i = 0; i <= S.size() - T.size(); i++)

		{

			if (T[0] == S[i])

			{

				if (T == S.substr(i, T.size()))

				{

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

				}

			}

		}

	}



	return 0;

}

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

#include <cstring>

inline void writeln(int x) {

	int s = 0, p; char f[7];

	while (x) {

		p = x; x /= 10;

		f[s++] = p - (x << 1) - (x << 3);

	}

	if (!s) f[s++] = 0;

	while (s--) putchar_unlocked(f[s] + '0');

	putchar_unlocked('\n');

}

char s[1000009], t[10009];

int main() {

	int sl = 0, tl = 0;

	while ((s[sl++] = getchar_unlocked()) != '\n'); sl--;

	while ((t[tl++] = getchar_unlocked()) != '\n'); tl--;

	unsigned long long hs = 0, ht = 0, pw = 1;

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

		hs = (hs << 8) + hs + s[i];

		ht = (ht << 8) + ht + t[i];

		pw = (pw << 8) + pw;

	}

	for (int i = tl; i <= sl; i++) {

		if (hs == ht) writeln(i - tl);

		hs = (hs << 8) + hs + s[i] - s[i - tl] * pw;

	}

	return 0;

}

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

#include <algorithm>

using namespace std;



typedef pair<int, int> P;



int main() {

int n,r;

long long m=0,c=1,q=1e9+7;

P p[200000];

cin>>n;

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

    cin>>p[i].first;

    p[i].second=i/n;

}

sort(p,p+n*2);

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

    if(m==0){

        m++;

        r=p[i].second;

    }else if(p[i].second==r){

        m++;

    }else{

        c=(c*m)%q;

        m--;

    }

}

cout<<c<<endl;





	return 0;

}

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

#include <algorithm>

#include <vector>

using namespace std;

typedef pair<int, int> P;

int main(void){

    int n;

    cin >> n;

    vector<P> v;

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

        int a;

        cin >> a;

        v.push_back(P(a, i));

    }

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

    int lft = 0;

    long long ans = 1, mod = 1e9+7;

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

        int s = v[i].second;

        if(s < n){

            if(lft <= 0) lft--;

            else ans *= lft--;

        }else{

            if(lft >= 0) lft++;

            else ans *= -lft++;

        }

        ans %= mod;

    }

    cout << ans << endl;

}


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

#include <vector>

#include <algorithm>

using namespace std;



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

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



const int MOD = 1e+9 + 7;



int main()

{

    int N;

    cin >> N;

    vector<int> a(N), b(N);    

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

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



    vector<long long> factorial(100001, 1);

    FOR(i, 1, 100001){

        factorial[i] *= i*factorial[i-1];

        factorial[i] %= MOD;

    }



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

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



    long long ans = 1;

    REP(i, N){

        int pos = lower_bound(a.begin(), a.end(), b[i]) - a.begin(), n;

        if(a[i] < b[i]) n = pos-i;

        else n = i-pos+1;

        ans *= n;

        ans %= MOD;

        // i += n-1;

        // cout << i << " " << ans << endl;

    } 

    cout << ans << endl;



    return 0;

}

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

#include <vector>

#include <algorithm>

using namespace std;



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

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



const int MOD = 1e+9 + 7;



int main()

{

    int N;

    cin >> N;

    vector<int> a(N), b(N);    

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

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



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

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



    long long ans = 1;  // 最初は a[i] - b[i] で繋がっている 

    REP(i, N){

        int pos = lower_bound(a.begin(), a.end(), b[i]) - a.begin(), n;

        if(a[i] < b[i]) n = pos-i;

        else n = i-pos+1;

        ans *= n;  // a[i] が繋げる可能性があるものは n 通り

        ans %= MOD;

        // cout << i << " " << ans << endl;

    } 

    cout << ans << endl;



    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//============================================================================

// Name        : AOJ.cpp

// Author      :

// Version     :

// Copyright   : Your copyright notice

// Description : Hello World in C++, Ansi-style

//============================================================================



#include <iostream>

using namespace std;

int P[100001];

long long A[100001],B[100001],C[100001];

int D[100001];



int main() {

	int N,M;

	long long R=0;

	cin>>N>>M;

	for(int i=1;i<M+1;i++)cin>>P[i];



	for(int i=1;i<N;i++)cin>>A[i]>>B[i]>>C[i];



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

		if(P[i]<P[i+1]){

			for(int j=P[i];j<P[i+1];j++)D[j]+=1;

		}else{

			for(int j=P[i+1];j<P[i];j++)D[j]+=1;

		}

	}



	for(int j=1;j<N;j++)R+=min(D[j]*B[j]+C[j],D[j]*A[j]);

	cout<<R<<endl;

	return 0;

}

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

#include<algorithm>



using namespace std;



const int MAX_N = 100000;

const int MAX_M = 100000;

int cnt[MAX_N+1];

int A[MAX_N],B[MAX_N],C[MAX_N];



int P[MAX_M];



int N,M;



int main(){

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

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

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

	}

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

		scanf("%d%d%d",A+i,B+i,C+i);

	}

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

		int x=P[i],y=P[i+1];

		if(x>y) swap(x,y);

		x--;

		y--;

		cnt[x]++;

		cnt[y]--;

	}

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

		cnt[i]+=cnt[i-1];

	}

	long long ans=0;

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

		long long paper=(long long)A[i]*cnt[i];

		long long ic=(long long)B[i]*cnt[i]+C[i];

		ans+=min(paper,ic);

	}

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

	return 0;

}




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

using namespace std;

int P[100001];

long long A[100001], B[100001], C[100001];

int D[100001];



int main() {

	int N,M;

	long long R=0;



	cin>>N>>M;

	for(int i=1; i<M+1; i++)cin>>P[i];

	for(int i=1; i<N; i++)cin>>A[i]>>B[i]>>C[i];



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

		if(P[i]<P[i+1]){

			for(int j=P[i]; j<P[i+1]; j++)D[ j ] += 1;

		}else{

			for(int j=P[i+1]; j<P[i]; j++)D[ j ] += 1;

		}

	}



	for(int j=1; j<N; j++) R += min(D[ j ]*B[ j ]+C[ j ],  D[ j ]*A[ j ]);

	cout<<R<<endl;

	return 0;

}




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

#include<algorithm>



using namespace std;



const int MAX_N = 100000;

const int MAX_M = 100000;

int cnt[MAX_N+1];

int A[MAX_N],B[MAX_N],C[MAX_N];



int P[MAX_M];



int N,M;



int main(){

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

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

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

	}

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

		scanf("%d%d%d",A+i,B+i,C+i);

	}

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

		int x=P[i],y=P[i+1];

		if(x>y) swap(x,y);

		x--;

		y--;

		cnt[x]++;

		cnt[y]--;

	}

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

		cnt[i]+=cnt[i-1];

	}

	long long ans=0;

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

		long long paper=(long long)A[i]*cnt[i];

		long long ic=(long long)B[i]*cnt[i]+C[i];

		ans+=min(paper,ic);

	}

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

	return 0;

}




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

using namespace std;

#define INF 1000000000



int main(void){

    

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

    int p[100010];

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

        cin >> p[i];

    }

    long long array[100010] = {};

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

        if(p[i] < p[i+1]){

            for(int j = p[i]; j < p[i+1]; j++){

                array[j]++;

            }

        }else{

            for(int j = p[i+1]; j < p[i]; j++){

                array[j]++;

            }

        }

    }



    

    long long ans = 0;



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

        long long a, b, c; cin >> a >> b >> c;

        ans += min(a*array[i], c + b*array[i]);

    }

    cout << ans << endl;

    return 0;

}

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

using namespace std;

#define int long long

const int MOD = 1000000007LL;

const int INF = LLONG_MAX;



signed main(){

    

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

    vector<int> p(n);

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

        cin >> p[i];

        p[i]--;

    }

    vector<int> a(n - 1);

    vector<int> b(n - 1);

    vector<int> c(n - 1);

    for(int i = 0; i < n - 1; i++) cin >> a[i] >> b[i] >> c[i];

    

    vector<int> imos(n, 0);

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

        int r = max(p[i], p[i - 1]);

        int l = min(p[i], p[i - 1]);

        imos[l]++;

        imos[r]--;

    }



    for(int i = 0; i < n - 1; i++) imos[i + 1] += imos[i];

    int ans = 0;

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

        ans += min(imos[i] * a[i], imos[i] * b[i] + c[i]);

    }



    cout << ans << endl;

    

    return 0;

}


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

using namespace std;

#define INF 1000000000





int main(void){

    

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

    int p[100010];

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

        cin >> p[i];

    }



    int array[100010] = {};

    //テヲツ?堙ァツ崢エ

    /*for(int i = 0; i < m-1; i++){

        if(p[i] < p[i+1]){

            for(int j = p[i]; j < p[i+1]; j++){

                array[j]++;

            }

        }else{

            for(int j = p[i+1]; j < p[i]; j++){

                array[j]++;

            }

        }

    }*/



    //テ」ツつ、テ」ツδ「テ」ツつケテヲツウツ?

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

        if(p[i] < p[i + 1]){

            array[p[i]]++;

            array[p[i + 1]]--;

        }else{

            array[p[i + 1]]++;

            array[p[i]]--;

        }

    }



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

        array[i+1] += array[i];

    }

    

    

    long long ans = 0;



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

        long long a, b, c; cin >> a >> b >> c;

        ans += min(a*array[i], c + b*array[i]);

    }

    cout << ans << endl;

    return 0;

}

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

using namespace std;

#define int long long

const int MOD = 1000000007LL;

const int INF = LLONG_MAX;



signed main(){

    

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

    vector<int> p(n);

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

        cin >> p[i];

        p[i]--;

    }

    vector<int> a(n - 1);

    vector<int> b(n - 1);

    vector<int> c(n - 1);

    for(int i = 0; i < n - 1; i++) cin >> a[i] >> b[i] >> c[i];

    

    vector<int> imos(n, 0);

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

        int r = max(p[i], p[i - 1]);

        int l = min(p[i], p[i - 1]);

        imos[l]++;

        imos[r]--;

    }



    for(int i = 0; i < n - 1; i++) imos[i + 1] += imos[i];

    int ans = 0;

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

        ans += min(imos[i] * a[i], imos[i] * b[i] + c[i]);

    }



    cout << ans << endl;

    

    return 0;

}


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

#include <iostream>

#include <algorithm>



using namespace std;



int main()

{

    int N, M;

    

    scanf("%d", &N);

    scanf("%d", &M);

    

    vector<long long> P(M);

    

    vector<long long> Q(N - 1);

    vector<long long> A(N - 1);

    vector<long long> B(N - 1);

    vector<long long> C(N - 1);

    

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

    {

        scanf("%lld", &P[i]); P[i]--;

    }

    

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

    {

        for(int j = min(P[i], P[i + 1]); j < max(P[i], P[i + 1]); j++)

        {

            Q[j]++;

        }

    }

    

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

    {

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

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

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

    }

    

    long long ret = 0;

    

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

    {

        long long s = A[i] * Q[i];

        long long t = B[i] * Q[i] + C[i];

        

        ret += min(s, t);

    }

    

    printf("%lld\n", ret);

    

    return 0;

}

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

#include <vector>

#include <algorithm>

using namespace std;

int N, M, A[100009], B[100009], C[100009], P[100009], sum[100009];

int main() {

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

	for (int i = 0; i < M; i++) scanf("%d", &P[i]), P[i]--;

	for (int i = 0; i < N - 1; i++) scanf("%d%d%d", &A[i], &B[i], &C[i]);

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

		int pl = P[i - 1], pr = P[i];

		if (pl > pr) swap(pl, pr);

		sum[pl]++; sum[pr]--;

	}

	for (int i = 1; i < N; i++) sum[i] += sum[i - 1];

	long long ret = 0;

	for (int i = 0; i < N - 1; i++) ret += min(1LL * A[i] * sum[i], 1LL * B[i] * sum[i] + C[i]);

	printf("%lld\n", ret);

	return 0;

}

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

using namespace std;



int main(){

    int N;

    int64_t X, x[200001];

    cin >> N >> X;

    for(int i=1; i<=N; i++) cin >> x[i];

    int64_t accum[200001] = {0};

    for(int i=1; i<=N; i++) accum[i] = x[i] + accum[i-1];



    int64_t ans = 2e15;

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

        int64_t result = (N+k) * X;

        for(int j=0; j<(N-1)/k+1; j++){

            int M = N - j*k;

            int m = max(0, M-k);

            int c = j==0 ? 5 : 2*j+3;

            result += c * (accum[M] - accum[m]);

            if(result >= ans) break;

        }

        ans = min(ans, result);

    }

    cout << ans << endl;

    return 0;

}

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

using namespace std;



int main(){

    int64_t N, X;

    cin >> N >> X;

    vector<int64_t> x(N+1), S(N+1);

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

        cin >> x[i];

        S[i] = S[i-1] + x[i];

    }



    int64_t ans = 1e18;

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

        int64_t res = (N+d)*X;

        int pt = N;

        for(int64_t i=0; pt>0; i++){

            int nxt = max(0, pt-d);

            res += (S[pt]-S[nxt]) * (i==0 ? 5 : 2*i+3);

            if(res >= ans) break;

            pt = nxt;

        }

        ans = min(ans, res);

    }

    cout << ans << endl;

}

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

#include <cmath>

#include <vector>

using namespace std;



typedef vector<double> point;

typedef const point &rpoint;



point add(rpoint p1, rpoint p2){

	point p(3);

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

		p[i] = p1[i] + p2[i];

	return p;

}



point sub(rpoint p1, rpoint p2){

	point p(3);

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

		p[i] = p1[i] - p2[i];

	return p;

}



point mul(double t, rpoint p2){

	point p(3);

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

		p[i] = t * p2[i];

	return p;

}



double abs(rpoint p){

	double s = 0.0;

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

		s += p[i] * p[i];

	return sqrt(s);

}



int main(){

	int n;

	point p(3);



	while( scanf("%d", &n), n != 0 ){

		vector<point> v;

		v.reserve(n);



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

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

				scanf("%lf", &p[j]);

			}

			v.push_back(p);

		}

		

		double mv = 0.5;

		double minr;

		while( mv > 1e-8 ){

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

				minr = -1.0;

				int mini = -1;

				

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

					double r = abs(sub(v[i], p));

					if( minr < r ){

						minr = r;

						mini = i;

					}

				}

				

				p = add(p, mul(mv, sub(v[mini], p) ) );

			}

			

			mv *= 0.5;

		}

		

		printf("%.10f\n", minr);

	}

}

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

#include <cmath>

#include <vector>

using namespace std;



typedef vector<double> point;

typedef const point &rpoint;



point add(rpoint p1, rpoint p2){

	point p(3);

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

		p[i] = p1[i] + p2[i];

	return p;

}



point sub(rpoint p1, rpoint p2){

	point p(3);

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

		p[i] = p1[i] - p2[i];

	return p;

}



point mul(double t, rpoint p2){

	point p(3);

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

		p[i] = t * p2[i];

	return p;

}



double abs(rpoint p){

	double s = 0.0;

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

		s += p[i] * p[i];

	return sqrt(s);

}



int main(){

	int n;

	point p(3);



	while( scanf("%d", &n), n != 0 ){

		vector<point> v;

		v.reserve(n);



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

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

				scanf("%lf", &p[j]);

			}

			v.push_back(p);

		}

		

		double mv = 0.5;

		double minr;

		while( mv > 1e-8 ){

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

				minr = -1.0;

				int mini = -1;

				

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

					double r = abs(sub(v[i], p));

					if( minr < r ){

						minr = r;

						mini = i;

					}

				}

				

				p = add(p, mul(mv, sub(v[mini], p) ) );

			}

			

			mv *= 0.5;

		}

		

		printf("%.10f\n", minr);

	}

}

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

using namespace std;



long long f(long long a[],long long x)

{

    if(x==a[x]);

    else a[x]=f(a,a[x]);

    return a[x];

}

long long a[200010];

long long b[200010];

long long c[200010];

long long d[200010];

int e[200010];

int main()

{



    long long n,m,k;

    long long x,y,i;

    scanf("%lld%lld%lld",&n,&m,&k);

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

    {

        a[i]=i;

        b[i]=i;

    }

    while(m--)

    {

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

        x=f(a,x);

        y=f(a,y);

        a[x]=y;

    }

    while(k--)

    {

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

        x=f(b,x);

        y=f(b,y);

        b[x]=y;

    }

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

    {

        c[i]=f(a,i)+(n+1)*f(b,i);

        d[i]=c[i];

    }

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

    memset(e,0,sizeof(e));

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

    {

        y=lower_bound(d+1,d+n+1,c[i])-d;

        e[y]++;

    }

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

    {

        y=lower_bound(d+1,d+n+1,c[i])-d;

        if(i==n)printf("%d\n",e[y]);

        else printf("%d ",e[y]);

    }

    return 0;

}


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

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

const int N=2e5+5;

int f1[N],f2[N];

int find1(int x){

    if(f1[x]==x)

        return x;

    return f1[x]=find1(f1[x]);

}

int find2(int x){

    if(f2[x]==x)

        return x;

    return f2[x]=find2(f2[x]);

}

map<pair<int,int>,int>p;

int main()

{

    int n,k,l;

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

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

        f1[i]=f2[i]=i;

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

        int u,v;

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

        int a=find1(u),b=find1(v);

        f1[a]=b;

    }

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

        int u,v;

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

        int a=find2(u),b=find2(v);

        f2[a]=b;

    }

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

        p[make_pair(find1(i),find2(i))]++;

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

        printf("%d ",p[make_pair(f1[i],f2[i])]);

}


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

using namespace std;

#define INF 0x3f3f3f3f

#define maxn 212345

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

class UMS

{

public:

    int f[maxn];

    UMS()

    {

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

        {

            f[i] = i;

        }

    }

    int getf(int u)

    {

        if(u == f[u])

            return f[u];

        else

        {

            f[u] = getf(f[u]);

            return f[u];

        }

    }

    void Merge(int u, int v)

    {

        int f1 = getf(u);

        int f2 = getf(v);

        if(f1 != f2)

        {

            f[f1] = f2;

        }

    }

};

vector<int> vec[maxn];

map<int, int> q;

int main()

{

    UMS u1, u2;

    int n, k, l, u, v;

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

    while(k--)

    {

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

        u1.Merge(u, v);

    }

    while(l--)

    {

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

        u2.Merge(u, v);

    }

    int vis[maxn];

    met(vis, 0);

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

    {

        int fa = u1.getf(i);

        vec[fa].push_back(i);

    }

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

    {

        q.clear();

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

        {

            q[u2.getf(vec[i][j])] ++;

        }

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

        {

            vis[vec[i][j]] += q[u2.getf(vec[i][j])];

        }



    }

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

    {

        printf("%d", vis[i]);

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

        else printf(" ");

    }

    return 0;

}


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

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

const int N=2e5+5;

int f1[N],f2[N];

int find1(int x){

    if(f1[x]==x)

        return x;

    return f1[x]=find1(f1[x]);

}

int find2(int x){

    if(f2[x]==x)

        return x;

    return f2[x]=find2(f2[x]);

}

map<pair<int,int>,int>p;

int main()

{

    int n,k,l;

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

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

        f1[i]=f2[i]=i;

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

        int u,v;

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

        int a=find1(u),b=find1(v);

        f1[a]=b;

    }

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

        int u,v;

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

        int a=find2(u),b=find2(v);

        f2[a]=b;

    }

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

        p[make_pair(find1(i),find2(i))]++;

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

        printf("%d ",p[make_pair(f1[i],f2[i])]);

}


// Fastest known solution for this problem: