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:
class UnionFind:
    
    def __init__(self,n):
        self.p = [i for i in range(n)]
        self.component = n
    
    def root(self,x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def union(self,x,y):
        x,y = self.root(x),self.root(y)
        if x > y:
            self.p[x] = y
            self.component -=1
        elif x<y:
            self.p[y] = x
            self.component -=1

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

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

for _ in range(k):
    p,q = map(int,input().split())
    K.union(p-1,q-1)
for _ in range(l):
    r,s = map(int,input().split())
    L.union(r-1,s-1)
from collections import defaultdict
dic = defaultdict(int)
ans = []
res = []
for i in range(n):
    dic[(K.p[i],L.p[i])]+=1
    ans.append((K.p[i],L.p[i]))
for a in ans:
    res.append(str(dic[a]))
print(' '.join(res))

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        news=[]
        p=self._parents
        y=p[x]
        while y>=0:
            news.append(x);x,y=y,p[y]
        if len(news)!=1:
            for P in news:p[P]=x
        return x

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(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 size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
road=UnionFind(1,n)
rail=UnionFind(1,n)
greatconnectivity=UnionFind(1,n)
for i in range(k):
    road.unite(*map(int,input().split()))
for i in range(l):
    a,s=map(int,input().split())
    rail.unite(a,s)
    if road.same(a,s):greatconnectivity.unite(a,s)
cnt=[0]*(1+n)
for i, v in enumerate(greatconnectivity._parents):
    if v<0:cnt[i]=-v
print(*[cnt[greatconnectivity.find(i)]for i in range(1,n+1)])

Submission status: Wrong Answer

Solution code:
import sys

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_road = UnionFind(N)
uf_train = UnionFind(N)

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

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

pair_list = []
for i in range(N):
    pair_list.append((uf_road.find(i), uf_train.find(i), i))

pair_list.sort()
ans = [1] * N

pair = (pair_list[0][0], pair_list[0][1])
num = pair_list[0][2]
for i in range(1,N):
    if pair == (pair_list[i][0], pair_list[i][1]):
        ans[num] += 1
        ans[pair_list[i][2]] += 1
    else:
        pair = (pair_list[i][0], pair_list[i][1])
        num = pair_list[i][2]
        

for i in range(N):
    print(ans[i], end=" ")

Submission status: Wrong Answer

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

par = [i for i in range(N)]
size = [1] * N


def find(x, P):
    if P[x] == x:
        a = x
        return x
    else:
        b = find(P[x], P)
        P[x] = b
        return b

def unite(x, y, P):
    root_x = find(x, P)
    root_y = find(y, P)
    if root_y > root_x:
        P[root_x] = root_y
    else:
        P[root_y] = root_x

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if y >= x:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s
    else:

        par2[y] = x
        s = size[x] + size[y]
        size[x] = s

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




#find(0,par)

#print(par)

for _ in range(L):
    p, q = map(int, input().split())
    s = find(p-1, par)
    t = find(q-1, par)
    if s == t:
        unite(p-1, q-1, par2)
#print(par2)

r=[]
for i in range(N):
    r.append((find(i,par), find(i, par2)))
import collections

count = collections.Counter(r)
#print(count)

for i in range(N):
  ans = count[r[i]]
  if i == N-1:
    print(ans)
  else:
    print(ans, end=' ')

Submission status: Wrong Answer

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

par = [i for i in range(N)]
size = [1] * N


def find(x, P):
    if P[x] == x:
        a = x
        return x
    else:
        b = find(P[x], P)
        P[x] = b
        return b

def unite(x, y):
    root_x = find(x, par)
    root_y = find(y, par)
    if root_y > root_x:
        par[root_x] = root_y
    else:
        par[root_y] = root_x

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if y >= x:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s
    else:

        par2[y] = x
        s = size[x] + size[y]
        size[x] = s

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




#find(0,par)

#print(par)

for _ in range(L):
    p, q = map(int, input().split())
    s = find(p-1, par)
    t = find(q-1, par)
    if s == t:
        unite2(p-1, q-1)

#print(par2)

for i in range(N-1):
    p = find(i, par2)
    print(size[p], end=' ')
print(size[find(N-1, par2)])

Submission status: Wrong Answer

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    root_x = find(x, par)
    root_y = find(y, par)
    if root_y > root_x:
        par[root_x] = root_y
    else:
        par[root_y] = root_x

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if y >= x:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s
    else:

        par2[y] = x
        s = size[x] + size[y]
        size[x] = s

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


root =[find(i, par) for i in range(N)]

#print(root)

#find(0,par)

#print(par)

for _ in range(L):
    p, q = map(int, input().split())
    s = root[p-1]
    t = root[q-1]
    if s == t:
        unite2(p-1, q-1)

#print(par2)

for i in range(N-1):
    p = find(i, par2)
    print(size[p], end=' ')
print(size[find(N-1, par2)])

Submission status: Wrong Answer

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    root_x = find(x, par)
    root_y = find(y, par)
    if root_y > root_x:
        par[root_x] = root_y
    else:
        par[root_y] = root_x

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

for _ in range(K):
    p, q = map(int, input().split())
    find(q-1, par)

    unite(p-1, q-1)

Submission status: Wrong Answer

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        pass
        #par[x] = y

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

for _ in range(K):
    p, q = map(int, input().split())
    find(q-1, par)

    unite(p-1, q-1)

Submission status: Wrong Answer

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        par[x] = y

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

for _ in range(K):
    p, q = map(int, input().split())
    find(q-1, par)

Submission status: Wrong Answer

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

par = [i for i in range(N)]
size = [1] * N


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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        # xとyの属している集合が異なる時
        par[x] = y

par2 = [i for i in range(N)]
def unite2(x, y):

    x = find(x, par2)
    y = find(y, par2)

    if x != y:
        # xとyの属している集合が異なる時
        par2[x] = y
        s = size[x] + size[y]
        size[y] = s

for _ in range(K):
    p, q = map(int, input().split())
    find(p, par)

Submission status: Wrong Answer

Solution code:
N, K, L = map(int, input().split())
for _ in range(K):
    p, q = map(int, input().split())
for _ in range(L):
    p, q = map(int, input().split())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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


# union-findを実装
root_road = [-1] * N
root_train = [-1] * N


def find_road(x):
    if root_road[x] < 0:
        return x

    root_road[x] = find_road(root_road[x])
    return root_road[x]


def union_road(x, y):
    x = find_road(x)
    y = find_road(y)
    if x == y:
        return

    root_road[x] += root_road[y]
    root_road[y] = x


def same_road(x, y):
    return find_road(x) == find_road(y)


def find_train(x):
    if root_train[x] < 0:
        return x

    root_train[x] = find_train(root_train[x])
    return root_train[x]


def union_train(x, y):
    x = find_train(x)
    y = find_train(y)
    if x == y:
        return

    root_train[x] += root_train[y]
    root_train[y] = x


def same_train(x, y):
    return find_train(x) == find_train(y)


dc = defaultdict(list)
dt = defaultdict(list)
for _ in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    dc[p].append(q)
    dc[q].append(p)
    union_road(p, q)

for _ in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    dt[r].append(s)
    dt[s].append(r)
    union_train(r, s)

# print(root_road, root_train)
ans = [0] * N
for i in range(N):
    if len(dt[i]) != 0 and len(dc[i]) != 0:
        for j in dt[i]:
            if same_road(i, j):
                ans[i] = 2

        for j in dc[i]:
            if same_train(i, j):
                ans[i] = 2
        if ans[i] != 2:
            ans[i] = 1

    elif len(dt[i]) != 0 or len(dc[i]) != 0:
        ans[i] = 1
    else:
        continue

print(*ans)

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)

    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()))
Network = UnionFind(N)

for i in range(K):
    p,q = list(map(int,input().split()))
    Network.union(p-1,q-1)

out=[1]*N
for i in range(L):
    r,s = list(map(int,input().split()))
    if Network.same(r-1,s-1)==True:
        out[r-1]+=1
        out[s-1]+=1

print(*out)

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)
    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())
    p = [list(map(int, input().split())) for _ in range(k)]
    r = [list(map(int, input().split())) for _ in range(l)]
    uf1 = UnionFind(n)
    for a, b in p:
        uf1.union(a-1, b-1)
    uf2 = UnionFind(n)
    for a, b in r:
        if uf1.same(a-1, b-1):
            uf2.union(a-1, b-1)
    for i in range(n):
        print(uf2.size(i), end=" ")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

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 = LI()
pq = [LI() for _ in range(K)]
rs = [LI() for _ in range(L)]

road = UnionFind(N)
for r in pq:
    f = r[0]-1
    t = r[1]-1
    road.union(f,t)

rail = UnionFind(N)
for r in rs:
    f = r[0]-1
    t = r[1]-1
    if road.same(f,t):
        rail.union(f,t)


ans = []
for i in range(N):
    ans.append(rail.size(i))

print(*ans)

Submission status: Wrong Answer

Solution code:
n,k,l = map(int,input().split())
car = [int(0) for i in range(n+1)]
train = [int(0) for i in range(n+1)]
for i in range(k):
    p,q = map(int,input().split())
    car[p] += 1
    car[q] += 1
for j in range(l):
    r,s = map(int,input().split())
    train[r] += 1
    train[s] += 1
#print(car)
#print(train)
ans = ''
for i in range(1,n+1):
    if car[i]>0 and train[i]>0:
        ans += '2 '
    else:
        ans += '1 '
print(ans[:-1])

Submission status: Wrong Answer

Solution code:
from collections import *
N, K, L = map(int,input().split())

def f(m):
    *a, = range(N)
    def g(i):
        if a[i] == i:
            return i
        a[i] = g(a[i])
        return a[i]
    for _ in range(m):
        p, q = map(int,input().split())
        a[g(q-1)] = g(p-1)
    return g

x, y = f(K), f(L)
c = Counter((x(i),y(i)) for i in range(N))
print(c)
print(*((c[x(i),y(i)]) for i in range(N)))

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = [-1 for _ in range(n)]  # 各要素の親 自分が根の場合は -1 * (木の要素数)

    def root(self, x):  # xが属する木の根を返す
        if self.parents[x] < 0:  # 自分が根の場合
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def merge(self, x, y):  # xが属する木とyが属する木を合体する
        x_root = self.root(x)  # xの根
        y_root = self.root(y)  # yの根

        if x_root == y_root:  # 同じ木に属する
            return

        if abs(self.parents[x_root]) >= abs(self.parents[y_root]):  # 要素数の比較
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

    def size(self, x):  # xが属する木の要素数
        return -self.parents[self.root(x)]

    def same(self, x, y):  # xとyが同じ木に属するか判定
        return self.root(x) == self.root(y)

    def roots(self):  # すべての根を求める
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # 木が何個あるか
        return len(self.roots())


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

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

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

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

    ans = [1 for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if uf_road.root(i) == uf_road.root(j) and uf_train.root(i) == uf_train.root(j):
                ans[i] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,K,L = [int(a) for a in input().split()]
roads = [0 for i in range(N)]
rails = [0 for i in range(N)]

for i in range(K):
  a,b = [int(a) for a in input().split()]
  if roads[a-1] == 0:
    roads[a-1] = 1
  if roads[b-1] == 0:
    roads[b-1] = 1

for i in range(L):
  a,b = [int(a) for a in input().split()]
  if rails[a-1] < 2:
    rails[a-1] = 1
  if rails[b-1] < 2:
    rails[b-1] = 1
    
tot = [rails[i] + roads[i] for i in range(N)]
print(*tot,sep=" ")

Submission status: Wrong Answer

Solution code:
N, K, L = map(int, input().split())
links1 = [tuple(map(int, input().split())) for _ in range(K)]
links2 = [tuple(map(int, input().split())) for _ in range(L)]


def pop_linked_cities(directly_linked: dict, i: int) -> set:
    """Pop linked city set recursively."""
    if not i in directly_linked:
        return set()
    linked = directly_linked.pop(i)
    undirectly_linked = [pop_linked_cities(directly_linked, c)
                         for c in linked]
    for l in undirectly_linked:
        linked = linked.union(l)
    return linked


def calculate_linked_set(links: list) -> dict:
    """Calculate linked city sets."""
    linked = {i: set([i]) for i in range(1, N + 1)}
    for p, q in links:
        linked[p].add(q)

    sets = {}
    for i in range(1, N + 1):
        if not i in linked:
            continue
        ret = pop_linked_cities(linked, i)
        for j in ret:
            sets[j] = ret
    return sets


linked1 = calculate_linked_set(links1)
linked2 = calculate_linked_set(links2)

counts = []
for n in range(1, N + 1):
    set1 = linked1[n]
    set2 = linked2[n]
    counts.append(str(len(set1.intersection(set2))))

print(' '.join(counts))

Submission status: Wrong Answer

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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, k, l = map(int, input().split())
    a = UnionFind(n)
    b = UnionFind(n)
    for _ in range(k):
        p, q = map(int, input().split())
        a.union(p-1, q-1)
    for _ in range(l):
        r, s = map(int, input().split())
        b.union(r-1, s-1)
    for i in range(n):
        if a.find(b.table[i], a.table[i]):
            print(2, end=" ")
        else:
            print(1, end=" ")


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, k, l = map(int, input().split())
roads = list(range(n))
railways = list(range(n))
ans = []
for _ in range(k):
    a, b = map(lambda x : int(x) - 1, input().split())
    i = min(roads[a], roads[b])
    roads[roads[a]] = i
    roads[roads[b]] = i
    roads[a] = i
    roads[b] = i
for _ in range(l):
    a, b = map(lambda x : int(x) - 1, input().split())
    i = min(railways[a], railways[b])
    railways[railways[a]] = i
    railways[railways[b]] = i
    railways[a] = i
    railways[b] = i
'''
roads_dic = dict()
railways_dic = dict()
for i in range(n):  
    if roads[i] == i:
        roads_dic[i] = {i}
    else:
        roads_dic[roads[i]].add(i)
    if railways[i] == i:
        railways_dic[i] = {i}
    else:
        railways_dic[railways[i]].add(i)
ans = [len(roads_dic[roads[i]] & railways_dic[railways[i]]) for i in range(n)]
'''
counter = dict()
for i in range(n):
    p = (roads[i], railways[i])
    if not p in counter:
        counter[p] = 1
    else:
        counter[p] += 1

ans = [counter[(roads[i], railways[i])] for i in range(n)]
print(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
n, k, l = map(int, input().split())
roads = list(range(n))
railways = list(range(n))
ans = []
for _ in range(k):
    a, b = map(lambda x : int(x) - 1, input().split())
    i = min(roads[a], roads[b])
    roads[roads[a]] = roads[a] = i
    roads[roads[b]] = roads[b] = i
for _ in range(l):
    a, b = map(lambda x : int(x) - 1, input().split())
    i = min(railways[a], railways[b])
    railways[railways[a]] = railways[a] = i
    railways[railways[b]] = railways[b] = i
'''
roads_dic = dict()
railways_dic = dict()
for i in range(n):  
    if roads[i] == i:
        roads_dic[i] = {i}
    else:
        roads_dic[roads[i]].add(i)
    if railways[i] == i:
        railways_dic[i] = {i}
    else:
        railways_dic[railways[i]].add(i)
ans = [len(roads_dic[roads[i]] & railways_dic[railways[i]]) for i in range(n)]
'''
counter = dict()
for i in range(n):
    p = (roads[i], railways[i])
    if not p in counter:
        counter[p] = 1
    else:
        counter[p] += 1

ans = [counter[(roads[i], railways[i])] for i in range(n)]
print(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:

class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())

n,k,l=map(int,input().split())
uf=UnionFind(n)
uf2=UnionFind(n)
for i in range(k):
    p,q=map(int,input().split())
    p-=1;q-=1
    uf.union(p,q)
for i in range(l):
    p,q=map(int,input().split())
    p-=1;q-=1
    if uf.same(p,q):
        uf2.union(p,q)

ANS=[0]*n 
for i in range(n):
    ANS[i]= uf2.size(i)
print(*ANS)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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())

N, K, L = mapint()
uf_road = UnionFind(N)
for _ in range(K):
    x, y = mapint()
    uf_road.union(x-1, y-1)

uf_rail = UnionFind(N)
for _ in range(L):
    x, y = mapint()
    uf_rail.union(x-1, y-1)
from collections import Counter
lis = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    lis.append(road*(10**5)+rail)
c = Counter(lis)
ans = []
for i in range(N):
    road = uf_road.find(i)
    rail = uf_rail.find(i)
    ans.append(str(c[(road*(10**5)+rail)]))
print(' '.join(ans))