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
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
class unionfind:#早いunionfind,class[i]のように要素指定すると親を得ることができる
    def __init__(self, elements=None):#elementsで初期化
        if elements is None:
            elements = ()
        self.parents = {}
        self.weights = {}
        for x in elements:
            self.weights[x] = 1
            self.parents[x] = x

    def __getitem__(self, i):
        # check for previously unknown i
        if i not in self.parents:
            self.parents[i] = i
            self.weights[i] = 1
            return i
        path = [i]
        root = self.parents[i]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]
        for ancestor in path:#縮約
            self.parents[ancestor] = root
        return root

    def __iter__(self):#for parent in Class:
        return iter(self.parents)

    def union(self, *objects):#オブジェクトをすべて結合
        roots = [self[x] for x in objects]
        heaviest = max(roots, key=lambda r: self.weights[r])
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest

    def __len__(self):
        return len(self.parents)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K, L = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    train=unionfind(range(N))
    rail=unionfind(range(N))
    for i in range(K):#木の場合M=N-1
        a,b = map(int,input().split())
        train.union(a-1,b-1)

    for i in range(L):#木の場合M=N-1
        a,b = map(int,input().split())
        a-=1
        b-=1
        if train[a]==train[b]:
            rail.union(a,b)
    ans=[0]*N
    for i in range(N):
        ans[i]=rail.weights[rail[i]]
    print(*ans)
        
    





if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def root(x, par):
    while par[x] >= 0:
        x = par[x]
    return x

def unite(x,y,par):
    rx = root(x,par)
    ry = root(y,par)
    if rx != ry:
        if rx > ry:
            rx, ry = ry, rx
        par[rx] += par[ry]
        par[ry] = rx

def same(x,y,par):
    rx = root(x,par)
    ry = root(y,par)
    return rx == ry

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

N, K, L = map(int, input().split())
par1 = [-1]*N
par2 = [-1]*N

for i in range(K):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    unite(A, B, par1)

for i in range(L):
    C, D = map(int, input().split())
    C, D = C-1, D-1
    if same(C, D, par1):
        unite(C, D, par2)

for i in range(N):
    print(size(i, par2), end=" ")

Submission status: Wrong Answer

Solution code:
def root(x, par):
    while par[x] >= 0:
        x = par[x]
    return x

def unite(x,y,par):
    rx = root(x,par)
    ry = root(y,par)
    if rx != ry:
        if rx > ry:
            rx, ry = ry, rx
        par[rx] += par[ry]
        par[ry] = rx

N, K, L = map(int, input().split())
par1 = [-1]*N
par2 = [-1]*N

for i in range(K):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    unite(A, B, par1)

for i in range(L):
    C, D = map(int, input().split())
    C, D = C-1, D-1
    unite(C, D, par2)

for i in range(N):
    c = 0
    if par1[i] != -1:
        c += 1
    if par2[i] != -1:
        c += 1
    print(c, end=" ")

Submission status: Wrong Answer

Solution code:
import copy
N,K,L = map(int,input().split())
dctK = {}
dctL = {}
for n in range(1,N + 1):
    dctK[n] = {n:0}
    dctL[n] = {n:0}
for k in range(K):
    p,q = map(int,input().split())
    dctK[p][q] = 0
    dctK[q][p] = 0
for l in range(L):
    r,s = map(int,input().split())
    dctL[r][s] = 0
    dctL[s][r] = 0
for k1 in dctK:
    dctK1 = dctK[k1]
    k2 = copy.copy(dctK1)
    while len(k2) > 0:
        dctAdd = {}
        for k3 in k2:
            if k3 in dctK1:
                continue
            dctAdd[k3] = 0
            dctK1[k3] = 0
        k2 = dctAdd
for l1 in dctL:
    dctL1 = dctL[l1]
    l2 = copy.copy(dctL1)
    while len(l2) > 0:
        dctAdd = {}
        for l3 in l2:
            if l3 in dctL1:
                continue
            dctAdd[l3] = 0
            dctL1[l3] = 0
        l2 = dctAdd
lstCnt = []
for n in range(1,n + 1):
    cnt = 0
    for k in dctK[n]:
        if k in dctL[n]:
            cnt += 1
    lstCnt.append(cnt)
m = map(str,lstCnt)
print(" ".join(m))

Submission status: Wrong Answer

Solution code:
class Uninonfind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
    def check(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False
    def find(self, x):
        if x == self.parent[x]:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n, k, l = map(int, input().split())
uf = Uninonfind(n)
group = [1 for _ in range(n)]
for _ in range(k):
    p, q = map(int, input().split())
    uf.union(p-1, q-1)
for _ in range(l):
    r, s = map(int, input().split())
    if uf.check(r-1, s-1):
        group[r-1] += 1
        group[s-1] += 1
print(*group)

Submission status: Wrong Answer

Solution code:
from collections import deque

N, K, L = [int(s) for s in input().split()]
edge_road = [[int(s) - 1 for s in input().split()] for _ in range(K)]
edge_train = [[int(s) - 1 for s in input().split()] for _ in range(L)]
graph_road = [[] for _ in range(N)]
graph_train = [[] for _ in range(N)]

for i, j in edge_road:
    graph_road[i].append(j)
    graph_road[j].append(i)

for i, j in edge_train:
    graph_train[i].append(j)
    graph_train[j].append(i)

completed = [False] * N

road = {}
train = {}

group_road = [0] * N
group_num = 0

visited = [False]*N

for i in range(N):
    if not visited[i]:
        continue
    dq = deque([i])
    while(dq):
        search_obj = dq.pop()
        for candidate_obj in graph_road[search_obj]:
            if not visited[candidate_obj]:
                group_road[candidate_obj] = group_num
                dq.appendleft(search_obj)
                visited[candidate_obj] = True
    group_num += 1


group_train = [0] * N
group_num = 0

visited = [False]*N

for i in range(N):
    if not visited[i]:
        continue
    dq = deque([i])
    while(dq):
        search_obj = dq.pop()
        for candidate_obj in graph_train[search_obj]:
            if not visited[candidate_obj]:
                group_train[candidate_obj] = group_num
                dq.appendleft(search_obj)
                visited[candidate_obj] = True
    group_num += 1

group_count = {}

for gr, gt in zip(group_road, group_train):
    if (gr, gt) in group_count.keys():
        group_count[(gr, gt)] += 1
    else:
        group_count[(gr, gt)] = 1


for gr, gt in zip(group_road, group_train):
    print(group_count[(gr, gt)] - 1, end=' ')

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
    
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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 sama_check(self, x, y):
        return self.find(x) == self.find(y)


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

un_load = UnionFind(n)
un_train = UnionFind(n)

for i in range(k):
    p, q = map(lambda x: int(x) - 1, input().split())
    
    if not un_load.sama_check(p, q):
        un_load.union(p, q)

for i in range(l):
    r, s = map(lambda x: int(x) - 1, input().split())
    
    if not un_train.sama_check(r, s):
        un_train.union(r, s)

load_train = {}
for i in range(n):
    comb = (un_load.par[i], un_train.par[i])
    
    if comb in load_train:
        load_train[comb] += 1
    else:
        load_train[comb] = 1

for i in range(n):
    print(load_train[(un_load.par[i], un_train.par[i])])

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
    
    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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 sama_check(self, x, y):
        return self.find(x) == self.find(y)


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

un_load = UnionFind(n)
un_train = UnionFind(n)

for i in range(k):
    p, q = map(lambda x: int(x) - 1, input().split())
    
    if not un_load.sama_check(p, q):
        un_load.union(p, q)

for i in range(l):
    r, s = map(lambda x: int(x) - 1, input().split())
    
    if not un_train.sama_check(p , q):
        un_train.union(p, q)

print(un_train.par)
rela = []
for i in range(n):
    load = un_load.par[i]
    train = un_train.par[i]
    rela.append([load, train])

print(rela)

Submission status: Wrong Answer

Solution code:
from collections import deque

def bfs():
    q = deque()
    color1 = [-1] * (n + 1)
    color2 = [-1] * (n + 1)
    for i in range(1, n + 1):
        if color1[i] == -1:
            color1[i] = i
            q.append(i)
            while q:
                p = q.popleft()
                for j in G[p]:
                    if color1[j] == -1:
                        color1[j] = color1[p]
                        q.append(j)
        if color2[i] == -1:
            color2[i] = i
            q.append(i)
            while q:
                p = q.popleft()
                for j in H[p]:
                    if color2[j] == -1:
                        color2[j] = color2[p]
                        q.append(j)
    group = [color1[i] + 100000 * color2[i] for i in range(n + 1)]
    return group

n, k, l = map(int, input().split())
G = [[] for _ in range(n + 1)]
H = [[] for _ in range(n + 1)]
for _ in range(k):
    p, q = map(int, input().split())
    G[p].append(q)
    G[q].append(p)
for _ in range(l):
    r, s = map(int, input().split())
    H[r].append(s)
    H[s].append(r)
group = bfs()
d = {}
for i in range(1, n + 1):
    if group[i] in d:
        d[group[i]] += 1
    else:
        d[group[i]] = 1
ans = [0] * n
for i in range(1, n + 1):
    ans[i - 1] = d[group[i]]
print(" ".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int,input().split())
road = [[] for _ in range(N+1)]
bridge = [[] for _ in range(N+1)]
for _ in range(K):
    p,q = map(int,input().split())
    road[p].append(q)
    road[q].append(p)
for _ in range(L):
    r,s = map(int,input().split())
    bridge[r].append(s)
    bridge[s].append(r)
from collections import deque
rd = [0 for _ in range(N+1)]
bd = [0 for _ in range(N+1)]
for i in range(N+1):
    queuer = deque([i])
    v = queuer.popleft()
    for j in road[v]:
        if rd[j] == 0:
            rd[j]=1
            queuer.append(j)
    queueb = deque([i])
    w = queueb.popleft()
    for j in bridge[w]:
        if bd[j] == 0:
            bd[j]=1
            queueb.append(i)
ans = []
for k in range(1,N+1):
    ans.append(rd[k]+bd[k])
print(" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int,input().split())
road = [[] for _ in range(N+1)]
bridge = [[] for _ in range(N+1)]
for _ in range(K):
    p,q = map(int,input().split())
    road[p].append(q)
    road[q].append(p)
for _ in range(L):
    r,s = map(int,input().split())
    bridge[r].append(s)
    bridge[s].append(r)
from collections import deque
rd = [0 for _ in range(N+1)]
bd = [0 for _ in range(N+1)]
for i in range(N+1):
    queuer = deque([i])
    v = queuer.popleft()
    for j in road[v]:
        if rd[j] == 0:
            rd[j]=1
            queuer.append(j)
    queueb = deque([i])
    w = queueb.popleft()
    for j in bridge[w]:
        if bd[j] == 0:
            bd[j]=1
            queueb.append(i)
print(rd)
print(bd)
ans = []
for k in range(1,N+1):
    ans.append(rd[k]+bd[k])
print(" ".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
a=[list(map(int,input().split()))for i in range(k)]
b=[list(map(int,input().split()))for i in range(l)]
c=[0]*n
a1=list(set(sum(a, [])))
b1=list(set(sum(b, [])))
c=[0]*n
for i in b1:
  c[i-1]+=1
for i in a1:
  c[i-1]+=1
print(*c)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

    def is_same(self, x, y):
        return self.link[x] == self.link[y]

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

# from union_find import *

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

u1 = UnionFind(n)
u2 = UnionFind(n)


for i in range(k):
    p, q = map(lambda x: int(x) - 1, readline().split())
    u1.unite(p, q)

for i in range(l):
    r, s = map(lambda x: int(x) - 1, readline().split())
    u2.unite(r, s)

c = defaultdict(int)

for i in range(n):
    c[(u1.find(i), u2.find(i))] += 1

for i in range(n):
    print(c[u1.find(1), u2.find(i)])

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

    def is_same(self, x, y):
        return self.link[x] == self.link[y]

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

# from union_find import *

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

u1 = UnionFind(n)
u2 = UnionFind(n)


for i in range(k):
    p, q = map(lambda x: int(x) - 1, readline().split())
    u1.unite(p, q)

for i in range(l):
    r, s = map(lambda x: int(x) - 1, readline().split())
    if u1.is_same(r, s):
        u2.unite(r, s)

for v in range(n - 1):
    print(u2.get_size(v), end=" ")
print(u2.get_size(n - 1))

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

    def is_same(self, x, y):
        return self.link[x] == self.link[y]

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]

# from union_find import *

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

u1 = UnionFind(n)

ans = [1 for _ in range(n)]

for i in range(k):
    p, q = map(lambda x: int(x) - 1, readline().split())
    u1.unite(p, q)

for i in range(l):
    p, q = map(lambda x: int(x) - 1, readline().split())
    if u1.is_same(p, q):
        ans[p] += 1
        ans[q] += 1

for v in ans[:-1]:
    print(v, end=" ")
print(ans[-1])

Submission status: Wrong Answer

Solution code:
# UnionFind
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.parent[x] = y

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

N, K, L = map(int, input().split())
un = UnionFind(N)
ans = [1]*N
for i in range(K):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    un.unite(p, q)
for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    if un.same(r, s):
        ans[r] += 1
        ans[s] += 1
print(*ans)

Submission status: Wrong Answer

Solution code:
#UNIONFIND
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[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
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
 
 
if __name__ == '__main__':
    n,k,l=map(int,input().split())
    pq=UnionFind(n+1)
    rs=UnionFind(n+1)
    for i in range(k):
        p,q=map(int,input().split())
        pq.union(p,q)
    for i in range(l):
        r,s=map(int,input().split())
        rs.union(r,s)
    sameroot=[]
    for i in range(1,n+1):
        sameroot.append([pq._root(i),rs._root(i),i])
    sameroot.sort()
    sameroot.append([0,0,n+1])
    cnt=[0]*(n+1)
    bx,by=0,0
    samelist=[]
    for x,y,i in sameroot:
        if bx==x and by==y:
            samelist.append(i)
        else:
            k=len(samelist)
            if k>0:
                for j in samelist:
                    cnt[j]=k
            samelist=[i]
            bx,by=x,y
    print(cnt[1:])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
from collections import deque
from copy import deepcopy

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 & road_group[road_belong_group[t_node]]
    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)}
    #city_list_forroad = deque([j for j in range(1, n + 1)])
    #city_list_fortrain = deepcopy(city_list_forroad)


    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 i_road in node_seen_road:
            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 i_train in node_seen_train 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.buffer.readline
sys.setrecursionlimit(10**6)
from collections import deque
from copy import deepcopy

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(road_group[road_belong_group[t_node]])
    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)}
    #city_list_forroad = deque([j for j in range(1, n + 1)])
    #city_list_fortrain = deepcopy(city_list_forroad)


    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 i_road in node_seen_road:
            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 i_train in node_seen_train 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()