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: Accepted

Solution code:
import sys
from collections import defaultdict


def input(): return sys.stdin.readline().rstrip()


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():

    N, K, L = map(int, input().split())
    highway = UnionFind(N)
    railroad = UnionFind(N)

    for _ in range(K):
        a, b = map(int, input().split())
        highway.unite(a - 1, b - 1)

    for _ in range(L):
        a, b = map(int, input().split())
        railroad.unite(a - 1, b - 1)

    d = defaultdict(int)
    for i in range(N):
        d[highway.root(i), railroad.root(i)] += 1
    print(*(d[highway.root(i), railroad.root(i)] for i in range(N)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N,K,L=map(int,input().split())
drive = [-1] * N;train = [-1] * N
def find(List,x):
  if List[x] < 0:
    return x
  List[x] = find(List,List[x])
  return List[x]
def unite(List,x,y):
  if find(List,x) != find(List,y):
    List[find(List,y)] = find(List,x)
for i in range(K+L):
  a, b = map(int,input().split())
  unite(drive if i < K else train,a-1, b-1)
pair = [(find(drive,i), find(train,i)) for i in range(N)]
c =Counter(pair)
print(*[c[pair[i]] for i in range(N)])

Submission status: Accepted

Solution code:
import collections
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n

    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

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

def main():
    n,k,l = tuple([int(t)for t in input().split()])

    uf_k = UnionFind(n)
    uf_l = UnionFind(n)


    pq = [[int(t)-1 for t in input().split()]for _ in [0]*k]
    for p,q in pq:
        uf_k.unite(p,q)

    rs = [[int(t)-1 for t in input().split()]for _ in [0]*l]
    for r,s in rs:
        uf_l.unite(r,s)

    pair = []
    for i in range(n):
        pair.append((uf_k.root(i),uf_l.root(i)))
    counter = collections.Counter(pair)
    
    ans = []
    for a in pair:
        ans.append(counter[a])
    print(*ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n

    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

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

def main():
    n,k,l = tuple([int(t)for t in input().split()])

    uf_k = UnionFind(n)
    uf_l = UnionFind(n)


    pq = [[int(t)-1 for t in input().split()]for _ in [0]*k]
    for p,q in pq:
        uf_k.unite(p,q)

    rs = [[int(t)-1 for t in input().split()]for _ in [0]*l]
    for r,s in rs:
        uf_l.unite(r,s)

    pair = []
    for i in range(n):
        pair.append((uf_k.root(i),uf_l.root(i)))
    counter = collections.Counter(pair)
    
    ans = []
    for a in pair:
        ans.append(counter[a])
    print(*ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, K, L = list(map(int, input().split()))
uf_road = UnionFind(N)
uf_train = UnionFind(N)

for i in range(K):
    node1, node2 = map(int, input().split())
    uf_road.union(node1 - 1, node2 - 1)

for i in range(L):
    node1, node2 = map(int, input().split())
    uf_train.union(node1 - 1, node2 - 1)

# 全メンバ列挙は遅い
# ans = [len(set(uf_road.members(i)) & set(uf_train.members(i))) for i in range(N)]
d = defaultdict(int)
for i in range(N):
    d[uf_road.find(i), uf_train.find(i)] += 1
print(*(d[uf_road.find(i), uf_train.find(i)] for i in range(N)))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, k, l = map(int, input().split())
uf_k = UnionFind(n)
uf_l = UnionFind(n)
for i in range(k):
    p, q = map(int, input().split())
    uf_k.union(p - 1, q - 1)
for i in range(l):
    r, s = map(int, input().split())
    uf_l.union(r - 1, s - 1)
d = defaultdict(int)
for i in range(n):
    d[uf_k.find(i), uf_l.find(i)] += 1
print(*(d[uf_k.find(i), uf_l.find(i)] for i in range(n)))

Submission status: Accepted

Solution code:

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

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

uf_road = UnionFind(n)
uf_train = UnionFind(n)

for _ in range(k):
  p, q = map(lambda x:int(x)-1, input().split())
  uf_road.Unite(p, q)

for _ in range(l):
  r, s = map(lambda x:int(x)-1, input().split())
  uf_train.Unite(r, s)

root_road = [0]*n 
root_train = [0]*n 

for i in range(n):
  root_road[i] = uf_road.Find_Root(i)
  root_train[i] = uf_train.Find_Root(i)

from collections import defaultdict
pair = defaultdict(int)
for i in range(n):
  pair[(root_road[i], root_train[i])] += 1 

for i in range(n):
  print(pair[(root_road[i], root_train[i])], end=" ")

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def renketu(n , k , l , pqli , rsli):

    from collections import defaultdict

    ans = []
    pquf = UnionFind(n)
    rsuf = UnionFind(n)

    [pquf.unite(p - 1 , q - 1) for q , p in pqli]
    [rsuf.unite(r - 1 , s - 1) for r , s in rsli]

    ansdict = defaultdict(int)

    for i in range(n):
        ansdict[(pquf.find(i) , rsuf.find(i))] += 1

    for i in range(n):
        ans.append(ansdict[(pquf.find(i) , rsuf.find(i))])

    return ans

def main():
    n, k, l = map(int, input().split())
    pqli = [list(map(int , input().split())) for i in range(k)]
    rsli = [list(map(int , input().split())) for i in range(l)]
    ans = renketu(n , k , l , pqli , rsli)

    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def size(self, x):
        return -self.parents[self.root(x)]
    
    def members(self, x):
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())

def main():
    N, K, L = map(int, input().split())
    uf_road = UnionFind(N)
    uf_railway = UnionFind(N)
    pq = [tuple(map(int, input().split())) for i in range(K)]

    [uf_road.unite(p-1, q-1) for p, q in pq]

    rs = [tuple(map(int, input().split())) for i in range(L)]


    [uf_railway.unite(r-1, s-1) for r, s in rs]
    
    d = defaultdict(int)
    
    for i in range(N):
        d[(uf_road.root(i), uf_railway.root(i))] += 1
    
    for i in range(N):
        print(d[(uf_road.root(i), uf_railway.root(i))])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def size(self, x):
        return -self.parents[self.root(x)]
    
    def members(self, x):
        x_root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == x_root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())

def main():
    N, K, L = map(int, input().split())
    uf_road = UnionFind(N)
    uf_railway = UnionFind(N)
    pq = [tuple(map(int, input().split())) for i in range(K)]
    for p, q in pq:
        uf_road.unite(p-1, q-1)
    rs = [tuple(map(int, input().split())) for i in range(L)]
    for r, s in rs:
        uf_railway.unite(r-1, s-1)
    
    d = defaultdict(int)
    for i in range(N):
        d[(uf_road.root(i), uf_railway.root(i))] += 1
    
    for i in range(N):
        print(d[(uf_road.root(i), uf_railway.root(i))])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1

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

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

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


N, K, L = map(int, input().split())

uf_tree1 = UnionFind(N)
uf_tree2 = UnionFind(N)

for _ in range(K):
    p, q = map(int, input().split())
    p -= 1; q -= 1;
    uf_tree1.unite(p, q)

for _ in range(L):
    r, s = map(int, input().split())
    r -= 1; s -= 1;
    uf_tree2.unite(r, s)

d = {}
for i in range(N):
    pair = (uf_tree1.root(i), uf_tree2.root(i))
    d[pair] = d.get(pair, 0) + 1

for i in range(N):
    pair = (uf_tree1.root(i), uf_tree2.root(i))
    print(d[pair], end = "")
    print("\n" if i == N-1 else " ", end = "")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, K, L = map(int,input().split())
    road = UnionFind(N)
    train = UnionFind(N)

    for k in range(K):
        p, q = map(int,input().split())
        p -= 1
        q -= 1
        road.union(p,q)

    for k in range(L):
        r, s = map(int,input().split())
        r -= 1
        s -= 1
        train.union(r,s)


    D = dict()
    P = [0]*N
    for k in range(N):
        t = (10**6)*(train.find(k)+1)+road.find(k)
        P[k] = t
        if t in D:
            D[t] += 1
        else:
            D[t] = 1
    ans = []
    for k in range(N):
        ans.append(D[P[k]])
    print(*ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:


    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:self.parent[x] = self.find(self.parent[x])
        x = self.parent[x]
        return x
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

from sys import stdin
def main():
    N,K,L = map(int,stdin.readline().split())
    uf = UnionFind(N)
    uf1 = UnionFind(N)

    for _ in range(K):
        p,q = map(int,stdin.readline().split())
        uf.union(p-1,q-1)
    for _ in range(L):
        r,s = map(int,stdin.readline().split())
        uf1.union(r-1,s-1)
    d = defaultdict(int)
    for i in range(N):
        d[(uf.find(i),uf1.find(i))] += 1
    print(*(d[uf.find(i),uf1.find(i)]for i in range(N)))
    #print(l)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:


    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

from sys import stdin
def main():
    N,K,L = map(int,stdin.readline().split())
    uf = UnionFind(N)
    uf1 = UnionFind(N)

    for _ in range(K):
        p,q = map(int,stdin.readline().split())
        uf.union(p-1,q-1)
    for _ in range(L):
        r,s = map(int,stdin.readline().split())
        uf1.union(r-1,s-1)
    d = defaultdict(int)
    for i in range(N):
        d[(uf.find(i),uf1.find(i))] += 1
    print(*(d[uf.find(i),uf1.find(i)]for i in range(N)))
    #print(l)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N, K, L = lmi()
pq = llmi(K)
rs = llmi(L)


class _UnionFind(object):
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


class UnionFind(_UnionFind):
    pass


uf_road = UnionFind(N)
for p, q in pq:
    uf_road.union(p - 1, q - 1)
uf_train = UnionFind(N)
for p, q in rs:
    uf_train.union(p - 1, q - 1)
# road_dict = collections.defaultdict(set)  # parent node -> set of member
# train_dict = collections.defaultdict(set)
# for i in range(N):
#     road_dict[uf_road.find(i)].add(i)
#     train_dict[uf_train.find(i)].add(i)
#
# print(' '.join(str(len(road_dict[uf_road.find(i)]&train_dict[uf_train.find(i)])) for i in range(N)))

d = collections.defaultdict(int)
for i in range(N):
    key = uf_road.find(i), uf_train.find(i)
    d[key] += 1

print(' '.join(str(d[(uf_road.find(i), uf_train.find(i))]) for i in range(N)))

Submission status: Accepted

Solution code:


def main():
    import sys
    input = sys.stdin.readline

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))

    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

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

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

        def size(self, x):
            return -self.parents[self.find(x)]

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

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            arr=[]
            for r in range(self.roots()):
                arr.append(set(self.members(r)))
            return arr

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
################
    mod=10**9+7
    N,K,L=MI()
    uf1 = UnionFind(N)
    uf2 = UnionFind(N)
    ans=[0]*N

    for i in range(K):
        p,q=MI()
        p-=1
        q-=1
        uf1.union(p,q)
        
    for i in range(L):
        p,q=MI()
        p-=1
        q-=1
        uf2.union(p,q)
        
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N):
        a=uf1.find(i)
        b=uf2.find(i)
        dd[(a,b)]+=1
        
    for i in range(N):
        a=uf1.find(i)
        b=uf2.find(i)
        ans[i]=dd[(a,b)]
        
    print(' '.join(map(str, ans)))
    
    
    
        
        
    


main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def sample():
    uf = UnionFind(6)
    print(uf.parents)
    uf.union(0, 2)
    print(uf.parents)
    uf.union(1, 3)
    print(uf.parents)
    uf.union(4, 5)
    print(uf.parents)

def atc001():
    n, q = map(int, input().split())
    uf = UnionFind(n)
    for i in range(q):
        p, a, b = map(int, input().split())
        if p == 0:
            uf.union(a, b)
        else:
            if uf.same(a, b):
                print("Yes")
            else:
                print("No")

def abc049():
    n, k, l = map(int, input().split())
    road = UnionFind(n)
    train = UnionFind(n)
    for i in range(k):
        p, q = map(int, input().split())
        road.union(p - 1, q - 1)
    for i in range(l):
        p, q = map(int, input().split())
        train.union(p - 1, q - 1)

    pair = []
    pair_cnt = {}
    for i in range(n):
        t, r = road.find(i), train.find(i)
        pair.append([t, r])
        key = t * (10 ** 6) + r
        if key in pair_cnt:
            pair_cnt[key] += 1
        else:
            pair_cnt[key] = 1

    for i in range(n):
        [t, r] = pair[i]
        key = t * (10 ** 6) + r
        print(pair_cnt[key], end = " ")

abc049()