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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

road = {}
train = {}
node_seen_road = set()
node_seen_train = set()
road_belong_group = {}
train_belong_group = {}
road_group = {}
train_group = {}
group_num_road = 0
group_num_train = 0
city_without_road = set()

def dfs_road(t_node):
    global road_group, road_belong_group, node_seen_road
    road_belong_group[t_node] = group_num_road
    road_group[group_num_road].add(t_node)
    node_seen_road.add(t_node)
    next_nodes = set(road[t_node]) - node_seen_road
    if len(next_nodes) == 0:
        return
    else:
        for nextnr in next_nodes:
            dfs_road(nextnr)

def dfs_train(t_node):
    global node_seen_train, train_group, train_belong_group
    train_belong_group[t_node] = group_num_train
    train_group[group_num_train].add(t_node)
    node_seen_train.add(t_node)
    next_nodes = set(train[t_node]) - node_seen_train
    next_nodes = next_nodes.intersection(node_seen_road)
    if len(next_nodes) == 0:
        return
    else:
        for nextnt in next_nodes:
            dfs_train(nextnt)


def main():
    global road, train, node_seen, road_group, train_group, node_all, road_belong_group,train_belong_group, group_num_road, group_num_train, city_without_road
    # 入力
    n, k, l = map(int, input().split())
    #node_all = set([i for i in range(1, n + 1)])
    road = {e: [] for e in range(1, n + 1)}
    train = {e: [] for e in range(1, n + 1)}
    road_belong_group = {e: -1 for e in range(1, n + 1)}
    train_belong_group = {e: -1 for e in range(1, n + 1)}

    for _ in range(k):
        p, q = map(int, input().split())
        road[p].append(q)
        road[q].append(p)

    for _ in range(l):
        s, t = map(int, input().split())
        train[s].append(t)
        train[t].append(s)

    # 処理
    ## 道路

    group_num_road = 1
    for i_road in range(1, n + 1):
        if road_belong_group[i_road] != -1:
            continue
        if not road[i_road]:
            continue
        road_group[group_num_road] = set()
        dfs_road(i_road)
        group_num_road += 1
    #city_without_road = set([ci for ci in road_belong_group if road_belong_group[ci] == -1])

    ## 鉄道

    group_num_train = 1
    for i_train in range(1, n + 1):
        if train_belong_group[i_train] != -1 or i_train not in node_seen_road:
            continue
        if not train[i_train]:
            continue
        train_group[group_num_train] = set()
        dfs_train(i_train)
        group_num_train += 1

    # 出力
    for i in range(1, n + 1):
        rg = road_belong_group[i]
        tg = train_belong_group[i]
        if rg == -1 or tg == -1:
            print(1, end= ' ')
        else:
            linked_city = len(road_group[rg].intersection(train_group[tg]))
            if linked_city == 0:
                linked_city += 1
            print(linked_city, end = ' ')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

road = {}
train = {}
node_seen = set()
road_belong_group = {}
train_belong_group = {}
road_group = {}
train_group = {}
group_num_road = 0
group_num_train = 0
city_without_road = set()

def dfs_road(t_node):
    global road_group, road_belong_group, node_seen
    road_belong_group[t_node] = group_num_road
    road_group[group_num_road].add(t_node)
    node_seen.add(t_node)
    next_nodes = set(road[t_node]) - node_seen
    if len(next_nodes) == 0:
        return
    else:
        for nextnr in next_nodes:
            dfs_road(nextnr)

def dfs_train(t_node):
    global node_seen, train_group, train_belong_group
    train_belong_group[t_node] = group_num_train
    train_group[group_num_train].add(t_node)
    node_seen.add(t_node)
    next_nodes = set(train[t_node]) - node_seen - city_without_road
    if len(next_nodes) == 0:
        return
    else:
        for nextnt in next_nodes:
            dfs_train(nextnt)


def main():
    global road, train, node_seen, road_group, train_group, node_all, road_belong_group,train_belong_group, group_num_road, group_num_train, city_without_road
    # 入力
    n, k, l = map(int, input().split())
    #node_all = set([i for i in range(1, n + 1)])
    road = {e: [] for e in range(1, n + 1)}
    train = {e: [] for e in range(1, n + 1)}
    road_belong_group = {e: -1 for e in range(1, n + 1)}
    train_belong_group = {e: -1 for e in range(1, n + 1)}

    for _ in range(k):
        p, q = map(int, input().split())
        road[p].append(q)
        road[q].append(p)

    for _ in range(l):
        s, t = map(int, input().split())
        train[s].append(t)
        train[t].append(s)

    # 処理
    ## 道路

    group_num_road = 1
    for i_road in range(1, n + 1):
        if road_belong_group[i_road] != -1:
            continue
        if not road[i_road]:
            continue
        road_group[group_num_road] = set()
        dfs_road(i_road)
        group_num_road += 1
    city_without_road = set([ci for ci in road_belong_group if road_belong_group[ci] == -1])

    ## 鉄道
    node_seen = set([])
    group_num_train = 1
    for i_train in range(1, n + 1):
        if train_belong_group[i_train] != -1 or road_belong_group[i_train] == -1:
            continue
        if not train[i_train]:
            continue
        train_group[group_num_train] = set()
        dfs_train(i_train)
        group_num_train += 1

    # 出力
    for i in range(1, n + 1):
        rg = road_belong_group[i]
        tg = train_belong_group[i]
        if rg == -1 or tg == -1:
            print(1, end= ' ')
        else:
            linked_city = len(road_group[rg].intersection(train_group[tg]))
            if linked_city == 0:
                linked_city += 1
            print(linked_city, end = ' ')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

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)


N, K, L = map(int, input().split(" "))
uf_road = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split(" "))
    uf_road.union(p - 1, q - 1)

uf = UnionFind(N)
for _ in range(L):
    r, s = map(int, input().split(" "))
    if uf_road.same(r - 1, s - 1):
        uf.union(r - 1, s - 1)

print(' '.join([str(uf.size(i)) for i in range(N)]))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self):
        self.par = []
        self.rank = []

    def init(self, n):
        for i in range(n):
            self.par.append(i)
            self.rank.append(0)

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

    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

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

N, K, L = list(map(int, input().split()))
road = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(K)]
railway = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(L)]

uf_road = UnionFind()
uf_road.init(N)
for i in range(K):
    uf_road.unite(road[i][0], road[i][1])

uf_railway = UnionFind()
uf_railway.init(N)
for i in range(L):
    uf_railway.unite(railway[i][0], railway[i][1])

connect = [0 for _ in range(N)]
connect_road = [0 for _ in range(N)]
connect_railway = [0 for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if uf_road.same(i, j):
            connect_road[i] = 1
            connect_road[j] = 1
        if uf_railway.same(i, j):
            connect_railway[i] = 1
            connect_railway[j] = 1

for i in range(N):
    connect[i] = connect_road[i] + connect_railway[i]

print(' '.join(map(str, connect)))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,k,l=map(int,input().split())
city1=[i for i in range(n)]
city2=[i for i in range(n)]
def root(c,x):
  if x==c[x]:
    return x
  else:
    c[x]=root(c,c[x])
    return c[x]
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx>ry:
    c[x]=ry
  else:
    c[y]=rx
for i in range(k):
  a,b=map(int,input().split())
  union(city1,a-1,b-1)
for i in range(l):
  a,b=map(int,input().split())
  union(city2,a-1,b-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for i in range(k)]
train=[list(map(int,input().split())) for i in range(l)]
city1=[i for i in range(n)]
city2=[i for i in range(n)]
def root(c,x):
  if x==c[x]:
    return x
  else:
    c[x]=root(c,c[x])
    return c[x]
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx>ry:
    c[x]=ry
  else:
    c[y]=rx
for i in range(k):
  union(city1,road[i][0]-1,road[i][1]-1)
for i in range(l):
  union(city2,train[i][0]-1,train[i][1]-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for i in range(k)]
train=[list(map(int,input().split())) for i in range(l)]
city1=[i for i in range(n)]
city2=[i for i in range(n)]
def root(c,x):
  if x==c[x]:
    return x
  else:
    c[x]=root(c,c[x])
    return c[x]
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx==ry:
    return
  else:
    if rx>ry:
      c[x]=ry
    else:
      c[y]=rx
for i in range(k):
  union(city1,road[i][0]-1,road[i][1]-1)
for i in range(l):
  union(city2,train[i][0]-1,train[i][1]-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for i in range(k)]
train=[list(map(int,input().split())) for i in range(l)]
city1=[i for i in range(n)]
city2=[i for i in range(n)]
def root(c,x):
  if x==c[x]:
    return x
  else:
    return root(c,c[x])
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx==ry:
    return
  else:
    if rx>ry:
      c[x]=ry
    else:
      c[y]=rx
for i in range(k):
  union(city1,road[i][0]-1,road[i][1]-1)
for i in range(l):
  union(city2,train[i][0]-1,train[i][1]-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for i in range(k)]
train=[list(map(int,input().split())) for i in range(l)]

city1=[[i for i in range(n)]]
city2=[[i for i in range(n)]]
rank1=[0 for i in range(n)]
rank2=[0 for i in range(n)]
city1.append(rank1)
city2.append(rank2)
def root(c,x):
  if x==c[0][x]:
    return x
  else:
    c[0][x]=root(c,c[0][x])
    return c[0][x]
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx==ry:
    return
  else:
    if c[1][x]>c[1][y]:
      c[0][y]=rx
    elif c[1][y]>c[1][x]:
      c[0][x]=ry
    else:
      c[0][x]=ry
      c[1][y]+=1
for i in range(k):
  union(city1,road[i][0]-1,road[i][1]-1)
for i in range(l):
  union(city2,train[i][0]-1,train[i][1]-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n-1:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for i in range(k)]
train=[list(map(int,input().split())) for i in range(l)]

city1=[[i for i in range(n)]]
city2=[[i for i in range(n)]]
rank1=[0 for i in range(n)]
rank2=[0 for i in range(n)]
city1.append(rank1)
city2.append(rank2)
def root(c,x):
  if x==c[0][x]:
    return x
  else:
    c[0][x]=root(c,c[0][x])
    return c[0][x]
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx==ry:
    return
  else:
    if c[1][x]>c[1][y]:
      c[0][y]=rx
    elif c[1][y]>c[1][x]:
      c[0][x]=ry
    else:
      c[0][x]=ry
      c[1][x]+=1
for i in range(k):
  union(city1,road[i][0]-1,road[i][1]-1)
for i in range(l):
  union(city2,train[i][0]-1,train[i][1]-1)
r=[]
for i in range(n):
  r.append((root(city1,i),root(city2,i)))
c=Counter(r)
for i in range(n):
  ans=c[r[i]]
  if i==n:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for i in range(k)]
train=[list(map(int,input().split())) for i in range(l)]

city1=[[i for i in range(n)]]
city2=[[i for i in range(n)]]
rank1=[0 for i in range(n)]
rank2=[0 for i in range(n)]
s1=[{i} for i in range(n)]
s2=[{i} for i in range(n)]
city1.append(rank1)
city1.append(s1)
city2.append(rank2)
city2.append(s2)
def root(c,x):
  if x==c[0][x]:
    return x
  else:
    c[0][x]=root(c,c[0][x])
    return c[0][x]
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx==ry:
    return
  else:
    if c[1][x]>c[1][y]:
      c[0][y]=rx
      c[2][rx]=c[2][rx]|c[2][ry]
    elif c[1][y]>c[1][x]:
      c[0][x]=ry
      c[2][ry]=c[2][rx]|c[2][ry]
    else:
      c[0][x]=ry
      c[1][x]+=1
      c[2][ry]=c[2][rx]|c[2][ry]
for i in range(k):
  union(city1,road[i][0]-1,road[i][1]-1)
for i in range(l):
  union(city2,train[i][0]-1,train[i][1]-1)
for i in range(n):
  ans=len(city1[2][root(city1,i)] & city2[2][root(city2,i)])
  if i==n:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
road=[list(map(int,input().split())) for i in range(k)]
train=[list(map(int,input().split())) for i in range(l)]

city1=[[i for i in range(n)]]
city2=[[i for i in range(n)]]
rank1=[0 for i in range(n)]
rank2=[0 for i in range(n)]
s1=[{i} for i in range(n)]
s2=[{i} for i in range(n)]
city1.append(rank1)
city1.append(s1)
city2.append(rank2)
city2.append(s2)
def root(c,x):
  if x==c[0][x]:
    return x
  else:
    return root(c,c[0][x])
def union(c,x,y):
  rx=root(c,x)
  ry=root(c,y)
  if rx==ry:
    return
  else:
    if c[1][x]>c[1][y]:
      c[0][y]=rx
      c[2][rx]=c[2][rx]|c[2][ry]
    elif c[1][y]>c[1][x]:
      c[0][x]=ry
      c[2][ry]=c[2][rx]|c[2][ry]
    else:
      c[0][x]=ry
      c[1][x]+=1
      c[2][ry]=c[2][rx]|c[2][ry]
for i in range(k):
  union(city1,road[i][0]-1,road[i][1]-1)
for i in range(l):
  union(city2,train[i][0]-1,train[i][1]-1)
for i in range(n):
  ans=len(city1[2][root(city1,i)] & city2[2][root(city2,i)])
  if i==n:
    print(ans)
  else:
    print(ans,end=' ')

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        # * Access m-th node by index `m`, not `m - 1`.
        # * If roots[x] < 0, x is a root node
        #   and the negative value represents the number of elements in the tree.
        self.roots = [-1 for _ in range(n + 1)]
        self.ranks = [0 for _ in range(n + 1)]

    def find_root(self, node):
        root_node = self.roots[node]
        if root_node < 0:
            return node
        else:
            new_root_node = self.find_root(root_node)
            self.roots[node] = new_root_node  # reduction
            return new_root_node

    def union(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        if one_root == other_root:
            return
        if self.ranks[one_root] < self.ranks[other_root]:
            self.roots[other_root] += self.roots[one_root]  # add size
            self.roots[one_root] = other_root
        else:
            self.roots[one_root] += self.roots[other_root]  # add size
            self.roots[other_root] = one_root
            if self.ranks[one_root] == self.ranks[other_root]:
                self.ranks[one_root] += 1

    def is_same_group(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        return one_root == other_root

    def group_size(self, node):
        root_node = self.find_root(node)
        return - self.roots[root_node]


def main():
    N, K, L = list(map(int, input().split(' ')))
    road_tree = UnionFind(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        road_tree.union(p, q)
    road_train_tree = UnionFind(N)
    for _ in range(L):
        r, s = list(map(int, input().split(' ')))
        if not road_tree.is_same_group(r, s):
            continue
        road_train_tree.union(r, s)
    answer = ' '.join([str(road_train_tree.group_size(node)) for node in range(1, N + 1)])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        # access m-th node by index `m`, not `m - 1`
        self.roots = [i for i in range(n + 1)]
        self.ranks = [0 for _ in range(n + 1)]
        self.group_sizes = [1 for _ in range(n + 1)]

    def find_root(self, node):
        root_node = self.roots[node]
        if node == root_node:
            return root_node
        else:
            new_root_node = self.find_root(root_node)
            self.roots[node] = new_root_node  # reduction
            return new_root_node

    def union(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        if one_root == other_root:
            return
        if self.ranks[one_root] < self.ranks[other_root]:
            self.roots[one_root] = other_root
            self.group_sizes[other_root] += self.group_sizes[one_root]
        else:
            self.roots[other_root] = one_root
            self.group_sizes[one_root] += self.group_sizes[other_root]
            if self.ranks[one_root] == self.ranks[other_root]:
                self.ranks[one_root] += 1

    def is_same_group(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        return one_root == other_root

    def group_size(self, node):
        root_node = self.find_root(node)
        return self.group_sizes[root_node]


def main():
    N, K, L = list(map(int, input().split(' ')))
    road_tree = UnionFind(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        road_tree.union(p, q)
    road_train_tree = UnionFind(N)
    for _ in range(L):
        r, s = list(map(int, input().split(' ')))
        if not road_tree.is_same_group(r, s):
            continue
        road_train_tree.union(r, s)
    answer = ' '.join([str(road_train_tree.group_size(node)) for node in range(1, N + 1)])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        # access m-th node by index `m`, not `m - 1`
        self.roots = [i for i in range(n + 1)]
        self.ranks = [0 for _ in range(n + 1)]
        self.group_sizes = [1 for _ in range(n + 1)]

    def find_root(self, node):
        root_node = self.roots[node]
        if node == root_node:
            return root_node
        else:
            new_root_node = self.find_root(root_node)
            self.roots[node] = new_root_node  # reduction
            return new_root_node

    def union(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        if one_root == other_root:
            return
        if self.ranks[one_root] < self.ranks[other_root]:
            self.roots[one_root] = other_root
            self.group_sizes[other_root] += self.group_sizes[one_root]
        else:
            self.roots[other_root] = one_root
            self.group_sizes[one_root] += self.group_sizes[other_root]
            if self.ranks[one_root] == self.ranks[other_root]:
                self.ranks[other_root] += 1

    def is_same_group(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        return one_root == other_root

    def group_size(self, node):
        root_node = self.find_root(node)
        return self.group_sizes[root_node]


def main():
    N, K, L = list(map(int, input().split(' ')))
    road_tree = UnionFind(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        road_tree.union(p, q)
    road_train_tree = UnionFind(N)
    for _ in range(L):
        r, s = list(map(int, input().split(' ')))
        if not road_tree.is_same_group(r, s):
            continue
        road_train_tree.union(r, s)
    answer = ' '.join([str(road_train_tree.group_size(node)) for node in range(1, N + 1)])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        # access m-th node by index `m`, not `m - 1`
        self.parents = [i for i in range(n + 1)]
        self.ranks = [0 for _ in range(n + 1)]
        self.group_sizes = [1 for _ in range(n + 1)]

    def find_root(self, node):
        parent_node = self.parents[node]
        if node == parent_node:
            return parent_node
        else:
            root_node = self.find_root(parent_node)
            self.parents[node] = root_node  # reduction
            return root_node

    def union(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        if self.ranks[one_root] < self.ranks[other_root]:
            self.parents[one_root] = other_root
            self.group_sizes[other_root] += self.group_sizes[one_root]
        else:
            self.parents[other_root] = one_root
            self.group_sizes[one_root] += self.group_sizes[other_root]
            if self.ranks[one_root] == self.ranks[other_root]:
                self.ranks[other_root] += 1

    def is_same_group(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        return one_root == other_root

    def group_size(self, node):
        root_node = self.find_root(node)
        return self.group_sizes[root_node]


def main():
    N, K, L = list(map(int, input().split(' ')))
    road_tree = UnionFind(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        road_tree.union(p, q)
    road_train_tree = UnionFind(N)
    for _ in range(L):
        r, s = list(map(int, input().split(' ')))
        if not road_tree.is_same_group(r, s):
            continue
        road_train_tree.union(r, s)
    answer = ' '.join([str(road_train_tree.group_size(node)) for node in range(1, N + 1)])
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    def find(self, x):  #要素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が属するグループと要素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):   #要素xと要素yが同じグループかどうか
        return self.find(x) == self.find(y)

    def members(self, x):   #要素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 = UnionFind(n)

p, q = [0] * k, [0] * k
for i in range(k):
    pp, qq = map(int, input().split())
    p[i] = pp - 1 
    q[i] = qq - 1
    uf.union(pp - 1, qq - 1)

uuff = UnionFind(n)
r, s = [0] * l, [0] * l
for i in range(l):
    rr, ss = map(int, input().split())
    r[i] = rr - 1
    s[i] = ss - 1
    uuff.union(rr - 1, ss - 1)
dic = defaultdict(int)
for i in range(n):
    print(uf.find(i),uuff.find(i))
    dic[(uf.find(i), uuff.find(i))] += 1

ans = []
for i in range(n):
    ans.append(dic[uf.find(i), uuff.find(i)])

for i in ans:
    print(i,end=" ")

Submission status: Wrong Answer

Solution code:
class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """要素xを含む集合の要素数を求める"""
        return -self.parent[self.root(x)]


n, k, l = map(int, input().split())
info_k = [list(map(int, input().split())) for i in range(k)]
info_l = [list(map(int, input().split())) for i in range(l)]

ufk = UnionFind(n)
ufl = UnionFind(n)
uf_total = UnionFind(n)

for a, b in info_k:
    a -= 1
    b -= 1
    ufk.merge(a, b)

for a, b in info_l:
    a -= 1
    b -= 1
    ufl.merge(a, b)

for a, b in info_k:
    a -= 1
    b -= 1
    if ufl.is_same(a, b):
        uf_total.merge(a, b)
        
for a, b in info_l:
    a -= 1
    b -= 1
    if ufk.is_same(a, b):
        uf_total.merge(a, b)  
        
print(*[uf_total.get_size(i) for i in range(n)])

Submission status: Wrong Answer

Solution code:
class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """要素xを含む集合の要素数を求める"""
        return -self.parent[self.root(x)]


n, k, l = map(int, input().split())
info_k = [list(map(int, input().split())) for i in range(k)]
info_l = [list(map(int, input().split())) for i in range(l)]

ufk = UnionFind(n)
ufl = UnionFind(n)

for a, b in info_k:
    a -= 1
    b -= 1
    ufk.merge(a, b)

for a, b in info_l:
    a -= 1
    b -= 1
    if ufk.is_same(a, b):
        ufl.merge(a, b)

print(*[ufl.get_size(i) for i in range(n)])

Submission status: Wrong Answer

Solution code:
N,K,L=map(int,input().split())
ansK=[]
ansL=[]
ans=[]
for i in range(N):
    ansK+=[1]
for i in range(N):
    ansL+=[1]
for i in range(K):
    a,b=map(int,input().split())
    ansK[a-1]+=1
    ansK[b-1]+=1
for i in range(L):
    a,b=map(int,input().split())
    ansL[a-1]+=1
    ansL[b-1]+=1
for i in range(N):
    ans+=[min(ansK[i],ansL[i])]
print(*ans)

Submission status: Wrong Answer

Solution code:
N,K,L=map(int,input().split())
ansK=[]
ansL=[]
ans=[]
for i in range(N):
    ansK+=[1]
for i in range(N):
    ansL+=[1]
for i in range(K):
    a,b=map(int,input().split())
    ansK[a-1]+=1
    ansK[b-1]+=1
for i in range(L):
    a,b=map(int,input().split())
    ansL[a-1]+=1
    ansL[b-1]+=1
for i in range(N):
    ansK[i]=min(ansK[i],ansL[i])
print(*ansK)