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

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 int_(num_str):
    return int(num_str) - 1

N, K, L = map(int, input().split())
uf1 = UnionFind(N)
for i in range(K):
    p, q = map(int_, input().split())
    uf1.union(p, q)
ans = [1]*N
for i in range(L):
    r, s = map(int_, input().split())
    if uf1.same(r, s):
        ans[r] += 1
        ans[s] += 1
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 same(self, x, y):
        return self.find(x) == self.find(y)

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

from sys import stdin
nii=lambda: list(map(int,stdin.readline().split()))

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

uf_k=UnionFind(n)
for i in range(k):
  p,q=nii()
  p-=1
  q-=1
  uf_k.union(p,q)

uf_l=UnionFind(n)
for i in range(l):
  r,s=nii()
  r-=1
  s-=1
  if uf_k.same(r,s):
    uf_l.union(r,s)

ans=[]
for i in range(n):
  ans.append(uf_l.size(i))

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): #要素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): #要素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())

#print(list(uf.all_group_members().values())) #グループ一覧を表示

def main():
    n,k,l=map(int,input().split())
    ufr=UnionFind(n)
    ans=[1]*n
    for i in range(k):
        x,y=map(int,input().split())
        ufr.union(x-1,y-1)
    for i in range(l):
        x,y=map(int,input().split())
        if ufr.same(x-1,y-1):
            ans[x-1]+=1
            ans[y-1]+=1
    print(*ans)
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline

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

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

"""
uniteでまとめ、findで見つける。
n(要素数)だけ最初に付け加えること。
"""

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

ans = [1]*n

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

print(*ans)

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
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]
uf1=UnionFind(n)
uf2=UnionFind(n)
for i in range(k):
  p,q=map(int,input().split())
  uf1.union(p-1,q-1)
ans=[0]*n
for i in range(l):
  r,s=map(int,input().split())
  if uf1.same(r-1,s-1):
    uf2.union(r-1,s-1)
for i in range(n):
  ans[i]=uf2.size(i)
print(*ans)

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
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]
uf=UnionFind(n)
for i in range(k):
  p,q=map(int,input().split())
  uf.union(p-1,q-1)
ans=[1]*n
for i in range(l):
  r,s=map(int,input().split())
  if uf.same(r-1,s-1):
    a,b=ans[r-1],ans[s-1]
    ans[r-1]+=b
    ans[s-1]+=a
print(*ans)

Submission status: Wrong Answer

Solution code:
n,k,l=map(int,input().split())
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]
uf=UnionFind(n)
for i in range(k):
  p,q=map(int,input().split())
  uf.union(p-1,q-1)
ans=[1]*n
for i in range(l):
  r,s=map(int,input().split())
  if uf.same(r-1,s-1):
    ans[r-1]+=1
    ans[s-1]+=1
print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[]
        self.dict=defaultdict(lambda:[])

        for i in range(self.n):
            self.roots.append(i)
            self.dict[i].append(i)

    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.dict[self.root(y)]=self.dict[self.root(y)]+self.dict[self.root(x)]
                self.dict[self.root(x)]=[]
                self.roots[self.root(x)]=self.root(y)
                self.allunite(self.root(x),self.root(y))
            else:
                self.roots[self.root(y)]=self.root(x)
                self.allunite(self.root(y),self.root(x))
    def find(self,x):
        return self.dict[x]
    def allunite(self,x,y):
        unit=self.find(x)
        for i in range(len(unit)):
            self.roots[unit[i]]=y
            return
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)


road_g=road.roots
train_g=train.roots

count=defaultdict(lambda:0)
for i in range(N):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(N):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]
    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
list1=[]
list2=[]
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    list1.append([p-1,q-1])
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    list2.append([r-1,s-1])
list1.sort()
list2.sort()
for i in range(K):
    road.unite(list1[i][0],list1[i][1])
for i in range(L):
    train.unite(list2[i][0],list2[i][1])

road_g=road.roots
train_g=train.roots

count=defaultdict(lambda:0)
for i in range(N):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(N):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]
    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.root(x)>self.root(y):
                self.roots[self.root(x)]=self.root(y)
            else:
                self.roots[self.root(y)]=self.root(x)
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
list1=[]
list2=[]
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)

road_g=road.roots
train_g=train.roots

count=defaultdict(lambda:0)
for i in range(N):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(N):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]
    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            self.roots[self.root(y)]=self.root(x)
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
list1=[]
list2=[]
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    list1.append([p,q])
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    list2.append([r,s])
list1.sort()
list2.sort()
for i in range(K):
    road.unite(list1[i][0]-1,list1[i][1]-1)
for i in range(L):
    train.unite(list2[i][0]-1,list2[i][1]-1)

road_g=road.roots
train_g=train.roots

count=defaultdict(lambda:0)
for i in range(N):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(N):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
class Unionfind:
    def __init__(self,n):
        self.n=n
        self.roots=[i for i in range(self.n)]
    def root(self,x):
        if self.roots[x]==x:
            return x
        else:
            self.roots[x]=self.root(self.roots[x])
            return self.roots[x]
    def unite(self,x,y):
        if self.root(x)==self.root(y):
            return
        else:
            if self.roots[self.root(y)]>self.root(x):
                self.roots[self.root(y)]=self.root(x)
    def same(self,x,y):
        return self.root(x)==self.root(y)

N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=Unionfind(N)
train=Unionfind(N)
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road.unite(p-1,q-1)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train.unite(r-1,s-1)

road_g=road.roots
train_g=train.roots

count=defaultdict(lambda:0)
for i in range(N):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(N):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=defaultdict(lambda:[])
train=defaultdict(lambda:[])
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road[p].append(q)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train[r].append(s)

def deep_search(dict):
    stack=[] 
    mem=[0 for i in range(N+1)]
    group={}
    for v in range(1,N+1):
        if mem[v]==0:
            mem[v]=1
            stack.append(v)
            while stack!=[]:
                w=stack.pop()
                group[w]=v
                for ww in dict[w]:
                    if mem[ww]==0:
                        mem[ww]=1
                        group[ww]=v
                        stack.append(ww)
    return group

road_g=deep_search(road)
train_g=deep_search(train)
count=defaultdict(lambda:0)
for i in range(1,N+1):
    l=[road_g[i],train_g[i]]
    count[str(l)]+=1
for i in range(1,N+1):
    l=[road_g[i],train_g[i]]
    print(count[str(l)],end=" ")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,K,L=list(input().split(" "))
N=int(N)
K=int(K)
L=int(L)
road=defaultdict(lambda:[])
train=defaultdict(lambda:[])
for i in range(K):
    p,q=map(int,list(input().split(" ")))
    road[p].append(q)
for i in range(L):
    r,s=map(int,list(input().split(" ")))
    train[r].append(s)

def deep_search(dict):
    stack=[] 
    mem=[0 for i in range(N+1)]
    group={}
    for v in list(dict):
        if mem[v]==0:
            stack.append(v)
            while stack!=[]:
                w=stack.pop()
                mem[v]=1
                group[w]=v
                for ww in dict[w]:
                    if mem[ww]==0:
                        mem[ww]=1
                        group[ww]=v
                        stack.append(ww)
    return group

road_g=deep_search(road)
train_g=deep_search(train)
count=defaultdict(lambda:0)
for i in range(1,N+1):
    if i in road_g.keys() and i in train_g.keys():
        l=[road_g[i],train_g[i]]
        count[str(l)]+=1
for i in range(1,N+1):
    if i in road_g.keys() and i in train_g.keys():
        l=[road_g[i],train_g[i]]
        print(count[str(l)],end=" ")
    else:
        print(1,end=" ")

Submission status: Wrong Answer

Solution code:
from sys import stdin
nii=lambda: list(map(int,stdin.readline().split()))

def root(x):
  if par[x]==-1:
   return x
  par[x]=root(par[x])
  return par[x]

def unite(x,y):
  if root(x)==root(y):
    return
  if x<y:
    x,y=y,x
  par[y]=x

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

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

par=[-1]*(n+1)
ans=[1]*(n+1)

for i in range(k):
 p,q=nii()
 unite(p,q)

for i in range(l):
 r,s=nii()
 judge=same(r,s)
 if judge:
  ans[r]+=1
  ans[s]+=1
print(*ans[1:])

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.size = [1]*size

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parent[x] = y
        else:
            self.size[x] += self.size[y]
            self.parent[y] = x
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def sizeofset(self, x):
        return self.size[self.find(x)]

if __name__ == "__main__":
    N,K,L = map(int,input().split())
    uf_road = UnionFind(N)
    uf_both = UnionFind(N)
    for _ in range(K):
        p,q = map(int,input().split())
        p -= 1
        q -= 1
        uf_road.unite(p,q)
    for _ in range(L):
        r,s = map(int,input().split())
        r -= 1
        s -= 1
        if uf_road.same(r,s):
            uf_both.unite(r,s)
    
    print(" ".join([str(uf_both.sizeofset(i)) for i in range(N)]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

s=input()

WL=['dream','dreamer','erase', 'eraser']
WLE5=['dream','eamer','erase','raser']
WD={'dream':5, 'eamer':7,'erase':5, 'raser':6}
def hantei(s):
    while True:
        if len(s)==0:
            return True
        elif len(s)<=4:
            return False
        elif len(s)==5:
            if s in WL:
                return True
            else:
                return False
        elif len(s)==6:
            if s=='eraser':
                return True
            else:
                return False
        elif len(s)==7:
            if s=='dreamer':
                return True
            else:
                False
        saigo=s[-5:]
        if saigo in WLE5:
            num=WD[saigo]
            s=s[:-num]
        else:
            return False
print('YES' if hantei(s) else 'NO')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)

s=input()

WL=['dream','dreamer','erase', 'eraser']
WLE5=['dream','eamer','erase','raser']
WD={'dream':5, 'eamer':7,'erase':5, 'raser':6}
def hantei(s):
    while True:
        if len(s)==0:
            return True
        elif len(s)<=4:
            return False
        saigo=s[-5:]
        if saigo in WLE5:
            num=WD[saigo]
            if len(s)<num:
                return False
            s=s[:-num]
        else:
            return False
print('YES' if hantei(s) else 'NO')

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,k,l=map(int,input().split())
#union-find
par1=[-1]*(n+1)
par2=[-1]*(n+1)

def find1(x):
    if par1[x]<0:
        return x
    else:
        par1[x]=find1(par1[x])
        return par1[x]
def find2(x):
    if par2[x]<0:
        return x
    else:
        par2[x]=find2(par2[x])
        return par2[x]
def size1(x):
    return -par1[find1(x)]
def size2(x):
    return -par2[find2(x)]
def unite1(x,y):
    if find1(x)==find1(y):
        return False
    else:
        if size1(x)<size1(y):
            x,y=y,x
        X=find1(x)
        Y=find1(y)
        par1[X]-=size1(Y)
        par1[Y]=X
        return True
def unite2(x,y):
    if find2(x)==find2(y):
        return False
    else:
        if size2(x)<size2(y):
            x,y=y,x
        X=find2(x)
        Y=find2(y)
        par2[X]-=size2(Y)
        par2[Y]=X
        return True
def is_same1(x,y):
    return find1(x)==find1(y)
def is_same2(x,y):
    return find2(x)==find2(y)

for _ in range(k):
    p,q=map(int,input().split())
    unite1(p,q)
for _ in range(l):
    r,s=map(int,input().split())
    if is_same1(r,s):
        unite2(r,s)
ans=[0]*(n)
for i in range(1,n+1):
    ans[i-1]=size2(i)
print(*ans, sep=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque

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

graphs = [[[] for _ in range(n)], [[] for _ in range(n)]]
cands = [set(), set()]
for _ in range(k):
    x, y = map(int, input().split())
    graphs[0][x - 1].append(y - 1)
    graphs[0][y - 1].append(x - 1)
    cands[0].add(x - 1)
for _ in range(l):
    x, y = map(int, input().split())
    graphs[1][x - 1].append(y - 1)
    graphs[1][y - 1].append(x - 1)
    cands[1].add(x - 1)

groups = [[], []]
groups_inv = [[-1] * n, [-1] * n]
def dfs(start, case, num):
    q = deque()
    q.append(start)
    used = {start}
    groups[case].append(used)
    groups_inv[case][start] = num
    while q:
        node = q.popleft()
        for to in graphs[case][node]:
            if to in used:
                continue
            q.append(to)
            used.add(to)
            groups_inv[case][to] = num

for i in range(2):
    count = 0
    for node in cands[i]:
        if groups_inv[i][node] == -1:
            dfs(node, i, count)
            count += 1

print(0)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

graphs = [[[] for _ in range(n)], [[] for _ in range(n)]]
cands = [set(), set()]
for _ in range(k):
    x, y = map(int, input().split())
    graphs[0][x - 1].append(y - 1)
    graphs[0][y - 1].append(x - 1)
    cands[0].add(x - 1)
for _ in range(l):
    x, y = map(int, input().split())
    graphs[1][x - 1].append(y - 1)
    graphs[1][y - 1].append(x - 1)
    cands[1].add(x - 1)

groups = [[], []]
groups_inv = [[-1] * n, [-1] * n]
def dfs(start, size, type, num):
    q = deque(maxlen=size)
    q.append(start)
    used = {start}
    groups[type].append(used)
    groups_inv[type][start] = num
    while q:
        node = q.popleft()
        for to in graphs[i][node]:
            if to in used:
                continue
            q.append(to)
            used.add(to)
            groups_inv[type][to] = num

counts = [0, 0]
for i in range(2):
    for node in cands[i]:
        if groups_inv[i][node] == -1:
            dfs(node, n, i, counts[i])
            counts[i] += 1

ret = [1] * n
ret_inv = [[-1] * counts[1] for _ in range(counts[0])]
for i in range(n):
    if groups_inv[0][i] == -1 or groups_inv[1][i] == -1:
        continue
    if ret_inv[groups_inv[0][i]][groups_inv[1][i]] == -1:
        size = len(groups[0][groups_inv[0][i]] & groups[1][groups_inv[1][i]])
        ret_inv[groups_inv[0][i]][groups_inv[1][i]] = size
    ret[i] = size

print(*ret)

Submission status: Wrong Answer

Solution code:
N, K, L = [int(x) for x in input().split()]
in_K = [[int(x) for x in input().split()] for i in range(K)]
in_L = [[int(x) for x in input().split()] for i in range(L)]

in_K.sort()
in_L.sort()

ar = {}
br = {}
val = 0
for i in range(K):
    p, q = in_K[i]
    if not p in ar.keys() and not q in ar.keys():
        val += 1
        ar[p] = val
        ar[q] = val
    else:
        if p in ar.keys():
            ar[q] = ar[p]
        else:
            ar[p] = ar[q]
for i in range(1, N + 1):
    if not i in ar.keys():
        val += 1
        ar[i] = val
val = 0
for i in range(L):
    p, q = in_L[i]
    if not p in br.keys() and not q in br.keys():
        val += 1
        br[p] = val
        br[q] = val
    else:
        if p in br.keys():
            br[q] = br[p]
        else:
            br[p] = br[q]
for i in range(1, N + 1):
    if not i in br.keys():
        val += 1
        br[i] = val
ab_dict = {}
for i in range(1, N + 1):
    if not (ar[i], br[i]) in ab_dict.keys():
        ab_dict[(ar[i], br[i])] = 1
    else:
        ab_dict[(ar[i], br[i])] += 1
ans = []
for i in range(1, N + 1):
    ans.append(ab_dict[(ar[i], br[i])])
print(*ans)

Submission status: Wrong Answer

Solution code:
N, K, L = [int(x) for x in input().split()]
in_K = [[int(x) for x in input().split()] for i in range(K)]
in_L = [[int(x) for x in input().split()] for i in range(L)]

in_K.sort()
in_L.sort()

set_lst = []
set_lst2 = []
first = True
for i in range(K):
    if first:
        set_lst.append(set(in_K[i]))
        first = False
    else:
        j = 0
        f = False
        while j < len(set_lst):
            if not len(set(in_K[i]) & set_lst[j]) == 0:
                f = True
                break
            j += 1
        if f:
            set_lst[j].update(in_K[i])
        else:
            set_lst.append(set(in_K[i]))
first = True
for i in range(L):
    if first:
        set_lst2.append(set(in_L[i]))
        first = False
    else:
        j = 0
        f = False
        while j < len(set_lst2):
            if not len(set(in_L[i]) & set_lst2[j]) == 0:
                f = True
                break
            j += 1
        if f:
            set_lst2[j].update(in_L[i])
        else:
            set_lst2.append(set(in_L[i]))
ans_lst = []
for i in range(1, N + 1):
    j = 0
    f1 = False
    while j < len(set_lst):
        if i in set_lst[j]:
            f1 = True
            break
        j += 1
    k = 0
    f2 = False
    while k < len(set_lst2):
        if i in set_lst2[k]:
            f2 = True
            break
        k += 1
    if f1 and f2:
        ans_lst.append(len(set_lst[j] & set_lst2[k]))
    else:
        ans_lst.append(1)
print(*ans_lst)

Submission status: Wrong Answer

Solution code:
N, K, L = [int(x) for x in input().split()]
in_K = [[int(x) for x in input().split()] for i in range(K)]
in_L = [[int(x) for x in input().split()] for i in range(L)]

in_K.sort()
in_L.sort()

set_lst = []
set_lst2 = []
first = True
for i in range(K):
    if first:
        set_lst.append(set(in_K[i]))
        first = False
    else:
        j = 0
        f = False
        while j < len(set_lst):
            if not len(set(in_K[i]) & set_lst[j]) == 0:
                f = True
                break
            j += 1
        if f:
            set_lst[j].update(in_K[i])
        else:
            set_lst.append(set(in_K[i]))
first = True
for i in range(L):
    if first:
        set_lst2.append(set(in_L[i]))
        first = False
    else:
        j = 0
        f = False
        while j < len(set_lst2):
            if not len(set(in_L[i]) & set_lst2[j]) == 0:
                f = True
                break
            j += 1
        if f:
            set_lst2[j].update(in_L[i])
        else:
            set_lst2.append(set(in_L[i]))
ans_lst = []
for i in range(1, N + 1):
    j = 0
    f1 = False
    while j < len(set_lst):
        if i in set_lst[j]:
            f1 = True
            break
        j += 1
    k = 0
    f2 = False
    while k < len(set_lst2):
        if i in set_lst2[k]:
            f2 = True
            break
        k += 1
    if f1 and f2:
        ans_lst.append(len(set_lst[j] & set_lst2[k]))
    else:
        ans_lst.append(1)
print(ans_lst)