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:
from collections import defaultdict
n,k,l=map(int,input().split())
d,d2=defaultdict(list),defaultdict(list)
for sss in range(k):
  a,b=map(int,input().split())
  d[a].append(b)
  d[b].append(a)
for sss in range(1,n+1):
  for ttt in d[sss]:
    for rrr in d[ttt]:
      if sss!=rrr:
        d[sss].append(rrr)
      d[sss]=list(set(d[sss]))
    break
for sss in range(l):
  a,b=map(int,input().split())
  d2[a].append(b)
  d2[b].append(a)
for sss in range(1,n+1):
  for ttt in d2[sss]:
    for rrr in d2[ttt]:
      if sss!=rrr:
        d2[sss].append(rrr)
      d2[sss]=list(set(d2[sss]))
    break
#print(d)
#print(d2)
ans=[]
for ttt in range(1,n+1):
  x=len(d[ttt])+len(d2[ttt])
  y=len(list(set(d[ttt]+d2[ttt])))
  if y<x:ans.append("2")
  else:ans.append("1")
print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
def dfs(r, c, g, color):
    s = [r]
    color[r] = c
    while len(s) != 0:
        u = s.pop()
        for i in range(len(g[u])):
            v = g[u][i]
            if color[v] is None:
                color[v] = c
                s.append(v)


def assignColor(n, g, color):
    color_id = 1
    for u in range(n):
        if color[u] is None:
            dfs(u, color_id, g, color)
            color_id += 1


N, K, L = [int(v) for v in input().split()]
road = [[] for i in range(N)]
train = [[] for i in range(N)]
for i in range(K):
    p, q = [int(v) - 1 for v in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in range(L):
    r, s = [int(v) - 1 for v in input().split()]
    train[r].append(s)
    train[s].append(r)

road_color = [None] * N
train_color = [None] * N
assignColor(N, road, road_color)
assignColor(N, train, train_color)

print(' '.join([str(v) for v in road_color]))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    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 same_check(self, x, y):
        return self.find(x) == self.find(y)

n,k,l = (int(i) for i in input().split())
ufr = UnionFind(n-1)
uft = UnionFind(n-1)
for i in range(k):
  tmp1,tmp2 = (int(i) for i in input().split())
  ufr.union(tmp1-1,tmp2-1)
for j in range(l):
  tmp1,tmp2 = (int(i) for i in input().split())
  if ufr.same_check(tmp1-1,tmp2-1):
   uft.union(tmp1-1,tmp2-1)

ans = [1]*n
for i in range(n):
  if uft.par.count(uft.par[i]) >= 2:
    ans[i] += 1
print(*ans)

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
def maketree(n,k):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road[p]={p,q}
            roadidx[p]=p
            roadidx[q]=p
        elif pidx==-1 and qidx!=-1:
            road[qidx]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[pidx]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            road[pidx]=road[pidx]|road[qidx]
            for j in road[qidx]:
                roadidx[j]=pidx
            road.pop(qidx)
    return road,roadidx

def makeresult(n,l,roadtree,roadidx):
    result=[1 for _ in range(n)]
    from collections import defaultdict
    metro=defaultdict(set)
    metroidx=[-1 for _ in range(n)]
    for i in range(l):
        r,s=map(int,input().split())
        r-=1
        s-=1
        rridx=roadidx[r]
        sridx=roadidx[s]
        rmidx=metroidx[r]
        smidx=metroidx[s]
        if rridx!=-1 and sridx!=-1 and rridx==sridx:
            if result[r]==1 and result[s]==1:
                result[r]+=1
                result[s]+=1
                metro[r]={r,s}
                metroidx[r]=r
                metroidx[s]=r
            elif result[r]>1 and result[s]==1:
                result[r]+=1
                result[s]=result[r]
                metro[rmidx]|={s,}
                metroidx[s]=rmidx
            elif result[r]==1 and result[s]>1:
                result[s]+=1
                result[r]=result[s]
                metro[smidx]|={r,}
                metroidx[r]=smidx
            elif result[r]>1 and result[s]>1:
                if rmidx!=smidx:
                    x=result[r]+result[s]
                    result[r]=x
                    result[s]=x
                    metro[rmidx]=metro[rmidx]|metro[smidx]
                    for j in metro[smidx]:
                        metroidx[j]=rmidx
                    metro.pop(smidx)
    return result
                    
                
                
        
        
roadtree,roadidx=maketree(n,k)
result=makeresult(n,l,roadtree,roadidx)

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

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
from collections import defaultdict
road=defaultdict(set)
metro=defaultdict(set)
for i in range(k):
    p,q=map(int,input().split())
    road[p]|={q,}
for j in range(l):
    r,s=map(int,input().split())
    metro[r]|={s,}

city={i for i in range(1,n+1)}
def maketree(n,target):
    city={i for i in range(1,n+1)}
    tree=[]
    now=1
    block={now,}
    city-={now,}
    block|=target[now]
    count=0
    while len(city)>0:
        for i in target[now]:
            block|=target[i]
            city-={i,}
        next=city & block
        
        if len(next)>0:
            now=next.pop()
            block|=target[now]
            city-={now,}
        elif len(next)==0:
            tree.append(block)
            if len(city)!=0:
                now=city.pop()
                block={now,}
                city-={now,}
                block|=target[now]
                if len(city)==0:tree.append(block)
    return tree
roadtree=maketree(n,road)
metrotree=maketree(n,metro)

ans=[]
for i in roadtree:
    for j in metrotree:
        ans.append(i & j)

result=[1 for i in range(n)]
while len(ans)>0:
    x=ans.pop()
    for i in x:
        result[i-1]=len(x)
        
res=''
for i in range(n):
    res=res+str(result[i])+' '
print(res)

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
from collections import defaultdict
road=defaultdict(set)
metro=defaultdict(set)
for i in range(k):
    p,q=map(int,input().split())
    road[p]|={q,}
for j in range(l):
    r,s=map(int,input().split())
    metro[r]|={s,}

city={i for i in range(1,n+1)}
def maketree(n,target):
    city={i for i in range(1,n+1)}
    tree=[]
    now=1
    block={now,}
    city-={now,}
    block|=target[now]
    count=0
    while len(city)>0:
        for i in target[now]:
            block|=target[i]
            city-={i,}
        next=city & block
        
        if len(next)>0:
            now=next.pop()
            block|=target[now]
            city-={now,}
        elif len(next)==0:
            tree.append(block)
            if len(city)!=0:
                now=city.pop()
                block={now,}
                city-={now,}
                block|=target[now]
                if len(city)==0:tree.append(block)
    return tree
roadtree=maketree(n,road)
metrotree=maketree(n,metro)

ans=[]
for i in roadtree:
    for j in metrotree:
        ans.append(i & j)

result=[1 for i in range(n)]
while len(ans)>0:
    x=ans.pop()
    for i in x:
        result[i-1]=len(x)
        
res=''
for i in range(n):
    res=res+str(result[i])+' '

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)
class UnionFind:
    def __init__(self, n):
        self.p=[i for i in range(n)]
        self.r=[0 for i in range(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 uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.r[x]<self.r[y]:
            self.p[x]=y
        else:
            self.p[y]=x
            if self.r[x]==self.r[y]:
                self.r[x]+=1
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

n,k,l=map(int,input().split())
uf_d=UnionFind(n)
uf_m=UnionFind(n)
for i in range(k):
    a,b=map(int,input().split())
    uf_d.uni(a-1,b-1)
for i in range(l):
    a,b=map(int,input().split())
    uf_m.uni(a-1,b-1)
dic={}
d=[]
for i in range(n):
    ky=(uf_d.p[i],uf_m.p[i])
    if ky in dic:
        dic[ky]+=1
    else:
        dic[ky]=1
    d.append(ky)
for i in range(n):
    print(dic[d[i]],end=' 'if i!=n-1 else '\n')

Submission status: Wrong Answer

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

"""
参考：https://img.atcoder.jp/arc065/editorial.pdf
・Union-Find木
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

from collections import Counter

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    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
            # 木の高さが同じなら片方を1増やす
            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 = map(int, input().split())
uf1 = UnionFind(N)
uf2 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p, q)
for i in range(L):
    p, q = map(int, input().split())
    uf2.union(p, q)

# (道路グループ番号, 鉄道グループ番号) のペアを各都市について作る
pairs = [None] * N
for i in range(N):
    pairs[i] = (uf1.par[i+1], uf2.par[i+1])

# 同じ内容のペアについて数える
c = Counter(pairs)

ans = [0] * N
for i in range(N):
    # 自分のペアのカウント数を各都市について取得
    ans[i] = c[pairs[i]]
print(*ans)

Submission status: Wrong Answer

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

"""
参考：https://img.atcoder.jp/arc065/editorial.pdf
・Union-Find木
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

from collections import Counter

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    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
            # 木の高さが同じなら片方を1増やす
            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 = map(int, input().split())
uf1 = UnionFind(N)
uf2 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p, q)
for i in range(L):
    p, q = map(int, input().split())
    uf2.union(p, q)

# (道路グループ番号, 鉄道グループ番号) のペアを各都市について作る
pairs = [None] * N
for i in range(N):
    pairs[i] = (uf1.par[i+1], uf2.par[i+1])

# 同じ内容のペアについて数える
c = Counter(pairs)

ans = [0] * N
for i in range(N):
    # 自分のペアのカウント数を各都市について取得
    ans[i] = c[(uf1.par[i+1], uf2.par[i+1])]
print(*ans)

Submission status: Wrong Answer

Solution code:
import collections
N,K,L = map(int, input().split())
p = []
q = []
for i in range(K):#h:高さ
    pi, qi = map(int, input().split())
    p.append(pi)
    q.append(qi)
r = []
s = []
for i in range(L):#h:高さ
    ri, si = map(int, input().split())
    r.append(ri)
    s.append(si)

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n + 1)

    # 検索
    # 根ならその番号を返す
    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
        # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(N)
for i in range(K):
    u.union(p[i],q[i])


u2 = UnionFind(N)
for i in range(L):
    u2.union(r[i],s[i])

li = [None]*(N)
liw = [None]*(N)
for i in range(N):
    li[i] = (u.par[i + 1], u2.par[i + 1], i + 1)
    liw[i] = (u.par[i + 1], u2.par[i + 1])
#li.sort(key=lambda x:(x[0], x[1]))

liws = collections.Counter(liw)

ansli = [0]*(N+1)
for i in range(N):
    ansli[i + 1] = liws[(li[i][0], li[i][1])]

for i in range(1, N + 1):
    print(ansli[i], "", end="")

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split())
p = []
q = []
for i in range(K):#h:高さ
    pi, qi = map(int, input().split())
    p.append(pi)
    q.append(qi)
r = []
s = []
for i in range(L):#h:高さ
    ri, si = map(int, input().split())
    r.append(ri)
    s.append(si)

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n + 1)

    # 検索
    # 根ならその番号を返す
    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
        # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(N)
for i in range(K):
    u.union(p[i],q[i])

keep = set()
ansli = [1]*(N + 1)
for i in range(L):
    if u.same_check(r[i], s[i]):
        ansli[r[i]] += 1
        ansli[s[i]] += 1
        keep.add((r[i], s[i]))


u2 = UnionFind(N)
for i in range(L):
    u2.union(r[i],s[i])

for i in range(K):
    if u2.same_check(p[i], q[i]) and (p[i], q[i]) not in keep:
        ansli[p[i]] += 1
        ansli[q[i]] += 1


for i in range(1, N + 1):
    print(ansli[i], "", end = "")

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split())
p = []
q = []
for i in range(K):#h:高さ
    pi, qi = map(int, input().split())
    p.append(pi)
    q.append(qi)
r = []
s = []
for i in range(L):#h:高さ
    ri, si = map(int, input().split())
    r.append(ri)
    s.append(si)

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n + 1)

    # 検索
    # 根ならその番号を返す
    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
        # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

u = UnionFind(N)
for i in range(K):
    u.union(p[i],q[i])

ansli = [1]*(N + 1)
for i in range(L):
    if u.same_check(r[i], s[i]):
        ansli[r[i]] += 1
        ansli[s[i]] += 1

for i in range(1, N + 1):
    print(ansli[i], "", end = "")

Submission status: Wrong Answer

Solution code:
N, K, L = [int(_) for _ in input().split()]


def find(a, x):
    stack = []
    if a[x] != x:
        stack += [x]
        x = a[x]
    while stack:
        a[stack.pop()] = x
    return x


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]


a_road = [i for i in range(N)]
for _ in range(K):
    p, q = [int(_) - 1 for _ in input().split()]
    unite(a_road, p, q)
a_railway = [i for i in range(N)]
for _ in range(L):
    r, s = [int(_) - 1 for _ in input().split()]
    unite(a_railway, r, s)
memo = {}
for i in range(N):
    memo[a_road[i], a_railway[i]] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

print(' '.join(str(memo[a_road[i], a_railway[i]]) for i in range(N)))

Submission status: Wrong Answer

Solution code:
N, K, L = [int(_) for _ in input().split()]
V1 = [[int(_) - 1 for _ in input().split()] for i in range(K)]
V2 = [[int(_) - 1 for _ in input().split()] for i in range(L)]


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

    # 検索
    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 x != 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 same_check(self, x, y):
        return self.find(x) == self.find(y)


uf1 = UnionFind(N)
uf2 = UnionFind(N)
for p, q in V1:
    uf1.union(p, q)

for r, s in V2:
    if uf1.same_check(r, s):
        uf2.union(r, s)

count_table = [0] * N
for i in range(N):
    count_table[uf2.find(i)] += 1

for i in range(N):
    print(count_table[uf2.find(i)], end=' ')
print()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,K,L = map(int,input().split())
 
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    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 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 check(self, x, y):
        return self.find(x) == self.find(y)

# 道路
A = UnionFind(N)
for i in range(K):
    x,y = map(int,input().split())
    A.unite(x,y)

# 鉄道
B = UnionFind(N)
for i in range(L):
    x,y = map(int,input().split())
    B.unite(x,y)

print(A.par)

dic = defaultdict(int)
for i in range(1,N+1):
    dic[A.find(i),B.find(i)] += 1

Ans = list(dic[A.par[i],B.par[i]] for i in range(1,N+1))
print(" ".join(map(str,Ans)))

Submission status: Wrong Answer

Solution code:
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

    def findSet(self, x):
        if(x != self.p[x]):
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

from collections import Counter
N, K, L = map(int, input().split())

ds = DisjointSet()
ds2 = DisjointSet()
for i in range(N):
    ds.makeSet(i+1)
    ds2.makeSet(i+1)

for i in range(K):
    p, q = map(int, input().split())
    ds.unite(p,q)

for i in range(L):
    r, s = map(int, input().split())
    ds2.unite(r, s)

a = [(ds.p[i], ds2.p[i]) for i in range(1, N+1)]
c = Counter(a)

print(' '.join([str(c[i]) for i in a]))

Submission status: Wrong Answer

Solution code:
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

    def findSet(self, x):
        if(x != self.p[x]):
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

from collections import defaultdict
N, K, L = map(int, input().split())

ds = DisjointSet()
ds2 = DisjointSet()
for i in range(N):
    ds.makeSet(i+1)
    ds2.makeSet(i+1)

for i in range(K):
    p, q = map(int, input().split())
    ds.unite(p,q)

for i in range(L):
    r, s = map(int, input().split())
    ds2.unite(r, s)


d1 = defaultdict(set)
d2 = defaultdict(set)

for k, v in ds.p.items():
    d1[v].add(k)
    
for k, v in ds2.p.items():
    d2[v].add(k)

ans = []
cache = defaultdict(tuple)
for i in range(1, N+1):
    a = ds.p[i]
    b = ds2.p[i]
    k = (a,b) if a > b else (b, a)
    if cache[k] == ():
        cache[k] = str(len(d1[a] & d2[b]))
    ans.append(cache[k])

print(' '.join(ans))

Submission status: Wrong Answer

Solution code:
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

    def findSet(self, x):
        if(x != self.p[x]):
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]

from collections import defaultdict
N, K, L = map(int, input().split())

ds = DisjointSet()
ds2 = DisjointSet()
for i in range(N):
    ds.makeSet(i+1)
    ds2.makeSet(i+1)

for i in range(K):
    p, q = map(int, input().split())
    ds.unite(p,q)

for i in range(L):
    r, s = map(int, input().split())
    ds2.unite(r, s)


d1 = defaultdict(set)
d2 = defaultdict(set)

for k, v in ds.p.items():
    d1[v].add(k)
    
for k, v in ds2.p.items():
    d2[v].add(k)

ans = []
for i in range(1, N+1):
    a = ds.p[i]
    b = ds2.p[i]
    ans.append(str(len(d1[a] & d2[b])))

print(' '.join(ans))

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(N, path, res):
    is_visited = [False for i in range(N + 1)]
    for i in range(1, N + 1):
        if is_visited[i] == True:
            continue
        que = deque([i])
        res[i] = set([i])
        while 1:
            if len(que) <= 0:
                break

            p = que.popleft()
            is_visited[p] = True

            for q in path[p]:
                if is_visited[q] == False:
                    is_visited[q] = True
                    res[i].add(q)
                    res[q] = res[i]
                    que.append(q)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K, L] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    road = {}
    train = {}
    for i in range(1, N + 1):
        road[i] = []
        train[i] = []

    for i in range(K):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        road[p].append(q)
        road[q].append(p)
    res_road = {}
    bfs(N, road, res_road)

    for i in range(L):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        train[p].append(q)
        train[q].append(p)

    res_train = {}
    bfs(N, train, res_train)

    for i in range(1, N + 1):
        print len(res_road[i]),




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(N, path, res):
    is_visited = [False for i in range(N + 1)]
    for i in range(1, N + 1):
        if is_visited[i] == True:
            continue
        que = deque([i])
        res[i] = set([i])
        while 1:
            if len(que) <= 0:
                break

            p = que.popleft()
            is_visited[p] = True

            for q in path[p]:
                if is_visited[q] == False:
                    is_visited[q] = True
                    res[i].add(q)
                    res[q] = res[i]
                    que.append(q)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K, L] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    road = {}
    train = {}
    for i in range(1, N + 1):
        road[i] = []
        train[i] = []

    for i in range(K):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        road[p].append(q)
        road[q].append(p)
    res_road = {}
    bfs(N, road, res_road)

    for i in range(L):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        train[p].append(q)
        train[q].append(p)

    res_train = {}
    bfs(N, train, res_train)

    for i in range(1, N + 1):
        print len(res_road[i]) + len(res_train[1]) - len(res_road[i] | res_train[1]),




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def bfs(N, path, res):
    is_visited = [False for i in range(N + 1)]
    for i in range(1, N + 1):
        if is_visited[i] == True:
            continue
        que = deque([i])
        res[i] = set([i])
        while 1:
            if len(que) <= 0:
                break

            p = que.popleft()
            is_visited[p] = True

            for q in path[p]:
                if is_visited[q] == False:
                    is_visited[q] = True
                    res[i].add(q)
                    res[q] = res[i]
                    que.append(q)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K, L] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    road = {}
    train = {}
    for i in range(1, N + 1):
        road[i] = []
        train[i] = []

    for i in range(K):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        road[p].append(q)
        road[q].append(p)
    res_road = {}
    bfs(N, road, res_road)

    for i in range(L):
        input_raw = read_func().strip().split()
        [p, q] = [int(input_raw[0]), int(input_raw[1])]
        train[p].append(q)
        train[q].append(p)

    res_train = {}
    bfs(N, train, res_train)

    for i in range(1, N + 1):
        print i, 
        #print len(res_road[i] & res_train[1]),




if __name__ == '__main__':
    main()