Problem:


Score : 400 points

Problem Statement

There are N cities. There are also K roads and L railways, extending between the cities.
The i-th road bidirectionally connects the p_i-th and q_i-th cities, and the i-th railway bidirectionally connects the r_i-th and s_i-th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

2 ≦ N ≦ 2*10^5

1 ≦ K, L≦ 10^5

1 ≦ p_i, q_i, r_i, s_i ≦ N

p_i < q_i

r_i < s_i

When i ≠ j, (p_i, q_i) ≠ (p_j, q_j)

When i ≠ j, (r_i, s_i) ≠ (r_j, s_j)

Input

The input is given from Standard Input in the following format:

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1, respectively.

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Sample Output 3

1 1 2 1 2 2 2



Sample input:
4 3 1
1 2
2 3
3 4
2 3


Sample output:
1 2 2 1

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

    def same(self, x, y):
        return self.root(x)==self.root(y)

    def root(self, x):
        if self.par[x]<0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:
            return

        if self.par[x]>self.par[y]:
            x,y = y,x

        self.par[x] += self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.root(x)]

n,k,l = map(int, input().split())
road = UnionFind(n)
for _ in range(k):
    p,q = map(int, input().split())
    road.unite(p-1, q-1)

rail = UnionFind(n)
for _ in range(l):
    r,s = map(int, input().split())
    if road.same(r-1, s-1):
        rail.unite(r-1, s-1)

res = [rail.size(i) for i in range(n)]
print(*res)

Submission status: Wrong Answer

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

    def __root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.__root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.__root(a)
        r2 = self.__root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.__root(a) == self.__root(b)

    def size(self, a):
        return self.__size[self.__root(a)]

    def groups(self):
        groups = {}
        for k in self.__parent_of.keys():
            r = self.__root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, K, L = map(int, input().split())
    uft = UnionFindTree(range(N))
    for _ in range(K):
        p, q = map(int, input().split())
        uft.unite(p-1, q-1)
    uft2 = UnionFindTree(range(N))
    for _ in range(L):
        r, s = map(int, input().split())
        if uft.is_same(r-1, s-1):
            uft2.unite(r-1, s-1)
    ans = [uft2.size(i) for i in range(N)]
    print(" ".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def root(x,d):
    if d[x]==x:
        return x
    x=d[x]
    return root(d[x],d)
def unite(x,y,h):
    x=root(x,h)
    y=root(y,h)
    if x!=y:
        h[x]=min(x,y)
        h[y]=h[x]
from collections import defaultdict
n,k,l=map(int,input().split())
a=[i for i in range(n+1)]
b=[i for i in range(n+1)]
for i in range(k):
    s,t=map(int,input().split())
    unite(s,t,a)
for i in range(l):
    s,t=map(int,input().split())
    unite(s,t,b)
d=defaultdict(int)
l=""
for i in range(1,n+1):
    d[(a[i],b[i])]+=1
for i in range(1,n+1):
    l+=str(d[(a[i],b[i])])+" "
print(l[:-1])

Submission status: Wrong Answer

Solution code:
def root(x,d):
    if d[x]==x:
        return x
    x=d[x]
    return root(d[x],d)
def unite(x,y,h):
    x=root(x,h)
    y=root(y,h)
    if x!=y:
        h[x]=min(x,y)
        h[y]=h[x]
from collections import Counter
n,k,l=map(int,input().split())
a=[i for i in range(n+1)]
b=[i for i in range(n+1)]
for i in range(k):
    s,t=map(int,input().split())
    unite(s,t,a)
for i in range(l):
    s,t=map(int,input().split())
    unite(s,t,b)
k=list(zip(a,b))[1:]
d=Counter(k)
l=""
for i in range(n):
    l+=str(d[k[i]])+" "
print(l[:-1])

Submission status: Wrong Answer

Solution code:
def root(x,d):
    if d[x]==x:
        return x
    x=d[x]
    return root(d[x],d)
def unite(x,y,h,d):
    x=root(x,h)
    y=root(y,h)
    if x!=y:
        if d[x]<d[y]:
            h[x]=y
            d[y]+=1
        else:
            h[y]=x
            d[x]+=1
from collections import Counter
n,k,l=map(int,input().split())
a=[i for i in range(n+1)]
b=[i for i in range(n+1)]
u=[1]*(n+1)
r=[1]*(n+1)
for i in range(k):
    s,t=map(int,input().split())
    unite(s,t,a,u)
for i in range(l):
    s,t=map(int,input().split())
    unite(s,t,b,r)
k=list(zip(a,b))[1:]
d=Counter(k)
l=""
for i in range(n):
    l+=str(d[k[i]])+" "
print(l[:-1])

Submission status: Wrong Answer

Solution code:
def root(x,d):
    if d[x]==x:
        return x
    x=d[x]
    return root(d[x],d)
def unite(x,y,h,d):
    x=root(x,h)
    y=root(y,h)
    if x!=y:
        if h[x]<h[y]:
            h[x]=y
            d[y]+=1
        else:
            h[y]=x
            d[x]+=1
from collections import Counter
n,k,l=map(int,input().split())
a=[i for i in range(n+1)]
b=[i for i in range(n+1)]
u=[1]*(n+1)
r=[1]*(n+1)
for i in range(k):
    s,t=map(int,input().split())
    unite(s,t,a,u)
for i in range(l):
    s,t=map(int,input().split())
    unite(s,t,b,r)
k=list(zip(a,b))[1:]
d=Counter(k)
l=""
for i in range(n):
    l+=str(d[k[i]])+" "
print(l[:-1])

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, K, L = [int(i) for i in input().split()]
par = [i for i in range(N)]
rank = [1 for i in range(N)]

def find(x):
    if par[x] == x:
        return x
    else:
        return par[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]


def find_2(x):
    if par_2[x] == x:
        return x
    else:
        return par_2[x]

def unite_2(x, y, is_incre=True):
    x = find_2(x)
    y = find_2(y)
    if x == y:
        pass
    else:
        if rank_2[x] > rank_2[y]:
            par_2[y] = x
            if is_incre:
                rank_2[x] += rank_2[y]
        else:
            par_2[x] = par_2[y]
            if is_incre:
                rank_2[y] += rank_2[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

def is_same_2(x, y):
    if find_2(x) == find_2(y):
        return True
    else:
        return False

for i in range(K):
    p, q = [int(i)-1 for i in input().split()]
    if is_same(p, q):
        continue
    else:
        unite(p, q)

rank_2 = [1 for i in range(N)]
par_2 = [i for i in range(N)]
for l in range(L):
    r, s = [int(i)-1 for i in input().split()]
    if is_same_2(r, s):
        pass
    else:
        unite_2(r, s)

par_ls = list()
for i in range(N):
    ar = find(i)
    br = find_2(i)
    par_ls.append((ar, br))
ct = Counter(par_ls)

for i in range(N):
    print(ct[par_ls[i]])

Submission status: Wrong Answer

Solution code:
N, K, L = [int(i) for i in input().split()]
par = [i for i in range(N)]
rank = [1 for i in range(N)]

def find(x):
    if par[x] == x:
        return x
    else:
        return par[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]


def find_2(x):
    if par_2[x] == x:
        return x
    else:
        return par_2[x]

def unite_2(x, y):
    x = find_2(x)
    y = find_2(y)
    if x == y:
        pass
    else:
        if rank_2[x] > rank_2[y]:
            par_2[y] = x
            rank_2[x] += rank_2[y]
        else:
            par_2[x] = par_2[y]
            rank_2[y] += rank_2[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

for i in range(K):
    p, q = [int(i)-1 for i in input().split()]
    if is_same(p, q):
        continue
    else:
        unite(p, q)

rank_2 = [1 for i in range(N)]
par_2 = [i for i in range(N)]
for i in range(L):
    r, s = [int(i)-1 for i in input().split()]
    if is_same(r, s):
        unite_2(r, s)
    else:
        continue

for i in range(N):
    print(rank_2[find_2(i)])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif aroot>broot:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])

Submission status: Wrong Answer

Solution code:
import sys


par1 , rank1 = [],[] 
par2 , rank2 = [],[]


def find(x,par,rank):
    if par[x] == x : return x
    else:
        par[x] = find(par[x],par,rank)
        return par[x]

def unite(x,y,par,rank): 
    x = find(x,par,rank)
    y = find(y,par,rank)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

def same(x,y,par,rank):
    return (find(x,par,rank) == find(y,par,rank)) 

n,k,l = map(int,input().split())

for i in range(n): 
    par1.append(i)
    rank1.append(0)
    par2.append(i)
    rank2.append(0)

for i in range(k):
    pp,qq = map(int,input().split())
    unite(pp-1,qq-1,par1,rank1)

for i in range(l):
    rr,ss = map(int,input().split())
    if (same(rr-1,ss-1,par1,rank1)) : unite(rr-1,ss-1,par2,rank2)

dic = {}
parlis = []
for i in range(n):
    p1 = find(i,par2,rank2)
    parlis.append(p1)
    if p1 in dic:
        dic[p1] += 1
    else: 
        dic[p1] = 1

ans = []

for i in range(n):
    ans.append(dic[parlis[i]])

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys


par1 , rank1 = [],[] 
par2 , rank2 = [],[]


def find(x,par,rank):
    if par[x] == x : return x
    else:
        par[x] = find(par[x],par,rank)
        return par[x]

def unite(x,y,par,rank): 
    x = find(x,par,rank)
    y = find(y,par,rank)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

def same(x,y,par,rank):
    return (find(x,par,rank) == find(y,par,rank)) 

n,k,l = map(int, sys.stdin.readline().split())

for i in range(n): 
    par1.append(i)
    rank1.append(0)
    par2.append(i)
    rank2.append(0)

for i in range(k):
    pp,qq = map(int, sys.stdin.readline().split())
    unite(pp-1,qq-1,par1,rank1)

for i in range(l):
    rr,ss = map(int, sys.stdin.readline().split())
    if (same(rr-1,ss-1,par1,rank1)) : unite(rr-1,ss-1,par2,rank2)

dic = {}
parlis = []
for i in range(n):
    p1 = find(i,par2,rank2)
    parlis.append(p1)
    if p1 in dic:
        dic[p1] += 1
    else: 
        dic[p1] = 1

ans = []

for i in range(n):
    ans.append(dic[parlis[i]])

print(*ans)

Submission status: Wrong Answer

Solution code:
import sys


par1 , rank1 = [],[] 
par2 , rank2 = [],[]


def find(x,par,rank):
    if par[x] == x : return x
    else:
        par[x] = find(par[x],par,rank)
        return par[x]

def unite(x,y,par,rank): 
    x = find(x,par,rank)
    y = find(y,par,rank)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

def same(x,y,par,rank):
    return (find(x,par,rank) == find(y,par,rank)) 

n,k,l = map(int, sys.stdin.readline().split())

for i in range(n): 
    par1.append(i)
    rank1.append(0)
    par2.append(i)
    rank2.append(0)

for i in range(k):
    pp,qq = map(int, sys.stdin.readline().split())
    unite(pp-1,qq-1,par1,rank1)

for i in range(l):
    rr,ss = map(int, sys.stdin.readline().split())
    if (same(rr-1,ss-1,par1,rank1)) : unite(rr-1,ss-1,par2,rank2)

dic = {}
parlis = []
for i in range(n):
    p1 = find(i,par2,rank2)
    parlis.append(p1)
    if p1 in dic:
        dic[p1] += 1
    else: 
        dic[p1] = 1

ans = str(dic[parlis[0]])

for i in range(1,n):
    ans = ans + " " + str(dic[parlis[i]])

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""

#D
def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2)
d = {}
for i in range(n):
    k = (par1[i],par2[i])
    if k in d:
        d[k] += 1
    else:
        d[k] = 1
ans = []
for i in range(n):
    k = (par1[i],par2[i])
    ans.append(d[k])
print(*ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""

#D
def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2)
d = {}
for i in range(n):
    k = par1[i]*n+par2[i]
    if k in d:
        d[k] += 1
    else:
        d[k] = 1
ans = []
for i in range(n):
    k = par1[i]*n+par2[i]
    ans.append(d[k])
print(*ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""

#D
def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2)
d = defaultdict(int)
for i in range(n):
    d[par1[i]*100000000000000000000000000000000000000+par2[i]] += 1
for i in range(n-1):
    print(d[par1[i]*100000000000000000000000000000000000000+par2[i]],end = " ")
print(d[par1[n-1]*100000000000000000000000000000000000000+par2[n-1]])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""

#D
def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2)
d = defaultdict(int)
for i in range(n):
    d[par1[i]*1000000000+par2[i]] += 1
for i in range(n-1):
    print(d[par1[i]*1000000000+par2[i]],end = " ")
print(d[par1[n-1]*1000000000+par2[n-1]])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""

#D
def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2)
d = defaultdict(int)
for i in range(n):
    d[par1[i]*n+par2[i]] += 1
for i in range(n-1):
    print(d[par1[i]*n+par2[i]],end = " ")
print(d[par1[n-1]*n+par2[n-1]])
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""

#D
def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank,s):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
        s[y] += s[x]
        s[x] = []
    else:
        par[y] = x
        s[x] += s[y]
        s[y] = []
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
s1 = [[i] for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
s2 = [[i] for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1,s1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2,s2)
for i in range(n-1):
    print(len(set(s1[par1[i]])&set(s2[par2[i]])),end = " ")
print(len(set(s1[par1[n-1]])&set(s2[par2[n-1]])))
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
s = input()
while s:
    if s[:11] == "dreameraser":
        s = s[11:]
    elif s[:10] == "dreamerase":
        s = s[10:]
    elif s[:7] == "dreamer":
        s = s[7:]
    elif s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "dream":
        s = s[5:]
    elif s[:5] == "erase":
        s = s[5:]
    else:
        print("NO")
        quit()
print("YES")
"""

#D
def root(x,par,rank):
    if x == par[x]:
        return x
    par[x] = root(par[x],par,rank)
    return par[x]
def unite(x,y,par,rank,s):
    x = root(x,par,rank)
    y = root(y,par,rank)
    if x == y:return
    if rank[x] < rank[y]:
        par[x] = y
        s[par[y]] += s[x]
        s[x] = []
    else:
        par[y] = x
        s[par[x]] += s[y]
        s[y] = []
        if rank[x] == rank[y]:
            rank[x] += 1
n,k,l = LI()
par1 = [i for i in range(n)]
rank1 = [0 for i in range(n)]
s1 = [[i] for i in range(n)]
par2 = [i for i in range(n)]
rank2 = [0 for i in range(n)]
s2 = [[i] for i in range(n)]
for i in range(k):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par1,rank1,s1)
for i in range(l):
    p,q = LI()
    p -= 1
    q -= 1
    unite(p,q,par2,rank2,s2)
for i in range(n-1):
    print(len(set(s1[par1[i]])&set(s2[par2[i]])),end = " ")
print(len(set(s1[par1[n-1]])&set(s2[par2[n-1]])))
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    #xとyが同じ集合に属するかを判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    
N, K, L = map(int, input().split())
    
p = [list(map(int, input().split())) for _ in range(K)]

r = [list(map(int, input().split())) for _ in range(L)]

res = [1 for _ in range(N)]
    
load = UnionFind(N)
train = UnionFind(N)

for i in range(K):
    load.unite(p[i][0]-1, p[i][1]-1)
    
for i in range(L):
    train.unite(r[i][0]-1, r[i][1]-1)
    
    if load.same(r[i][0]-1, r[i][1]-1):
        res[r[i][0]-1] += 1
        res[r[i][1]-1] += 1

result = ''
for i in range(N):
    result += str(res[i]) + ' '
    
print(result)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,k,l=map(int,input().split())
d,d2=defaultdict(list),defaultdict(list)
for sss in range(k):
  a,b=map(int,input().split())
  d[a].append(b)
  d[b].append(a)
for sss in d:
  for ttt in d[sss]:
    d[sss].extend([rrr for rrr in d[ttt] if rrr!=sss])
    d[sss]=list(set(d[sss]))
    break
for sss in range(l):
  a,b=map(int,input().split())
  d2[a].append(b)
  d2[b].append(a)
for sss in d2:
  for ttt in d2[sss]:
    d2[sss].extend([rrr for rrr in d2[ttt] if rrr!=sss])
    d2[sss]=list(set(d2[sss]))
    break
#print(d)
#print(d2)
ans=[]
for i in range(1,n+1):
  if set(d[i])&set(d2[i]):ans.append("2")
  else:ans.append("1")
print(" ".join(ans))