Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
    return root[x]

def UnionFind(N,branch):
    root=[-1*inf]*(N+1)
    tree=dict()
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if root[aroot]<-1*N and root[broot]<-1*N:
            tree[-1*a]={a,b}
            root[a]=-1*a
            root[b]=a
        elif root[broot]<-1*N and root[aroot]>=-1*N:
            tree[root[aroot]]|={b,}
            root[broot]=aroot
        elif root[aroot]<-1*N and root[broot]>=-1*N:
            tree[root[broot]]|={a,}
            root[aroot]=broot
        elif root[aroot]==root[broot]:
            continue
        elif root[aroot]!=root[broot]:
            tree[root[aroot]]|=tree[root[broot]]
            tree.pop(root[broot])
            root[broot]=aroot
    return root,tree

r_root,r_tree=UnionFind(N,road)
m_root,m_tree=UnionFind(N,metro)
ans=''
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    if r_root[ri]<-1*N or m_root[mi]<-1*N:
        ans+='1 '
    else:
        ans+=str(len(r_tree[r_root[ri]]&m_tree[m_root[mi]]))+' '
print(ans[:-1])

Fixed submission:
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])

Buggy python submission (verdict: Time Limit Exceeded):
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 roadidx

def renew(idx):
    count=0
    for i in range(len(idx)):
        if idx[i]==-1:
            idx[i]-=count
            count+=1
    return idx
roadidx=renew(maketree(n,k))
metroidx=renew(maketree(n,l))


idx=[]
for i in range(n):
    idx.append((roadidx[i],metroidx[i]))
res=''
for i in range(n):
    res=res+str(idx.count(idx[i]))+' '
print(res)
###https://img.atcoder.jp/arc065/editorial.pdf

Fixed submission:
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])

Buggy python submission (verdict: Time Limit Exceeded):
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

roadtree,roadidx=maketree(n,k)
metrotree,metroidx=maketree(n,l)

result=[1 for i in range(n)]
for i in roadtree:
    target=roadtree[i]
    check=target.copy()
    while len(check)>0:
        now=check.pop()
        if metroidx[now]!=-1:
            x=target & metrotree[metroidx[now]]
            if len(x)!=0:
                for j in x:
                    result[j]=len(x)
        else:x={now,}
        check-=x

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

Fixed submission:
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,k,l=map(int,input().split())
def maketree(n,k,target):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(len(target)):
        p=target[i][0]
        q=target[i][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:
            x=road[pidx]|road[qidx]
            y=min(pidx,qidx)
            z=max(pidx,qidx)
            road[y]=x
            road.pop(z)
            for j in x:
                roadidx[j]=y
    resroad=[]
    idx=[-1 for _ in range(n)]
    count=0
    for i in road:
        resroad.append(road[i])
        for j in road[i]:
            idx[j]=count
        count+=1
    return resroad,idx

road = []
for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        road.append([p,q])
metro=[]
for i in range(l):
        r,s=map(int,input().split())
        r-=1
        s-=1
        metro.append([r,s])
roadtree,roadidx=maketree(n,k,road)
metrotree,metroidx=maketree(n,l,metro)

result=[1 for i in range(n)]
for i in roadtree:
    check=i.copy()
    while len(check)>0:
        now=check.pop()
        if metroidx[now]!=-1:
            x=i & metrotree[metroidx[now]]
            if len(x)!=0:
                for j in x:
                    result[j]=len(x)
        else:x={now,}
        check-=x

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

Fixed submission:
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,k,l=map(int,input().split())
def maketree(n,k,target):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(len(target)):
        p=target[i][0]
        q=target[i][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:
            x=road[pidx]|road[qidx]
            y=min(pidx,qidx)
            z=max(pidx,qidx)
            road[y]=x
            road.pop(z)
            for j in x:
                roadidx[j]=y
    resroad=[]
    for i in road:
        resroad.append(road[i])
    return resroad

road = []
for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        road.append([p,q])
metro=[]
for i in range(l):
        r,s=map(int,input().split())
        r-=1
        s-=1
        metro.append([r,s])
roadtree=maketree(n,k,road)
metrotree=maketree(n,l,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]=len(x)
        
res=''
for i in range(n):
    res=res+str(result[i])+' '
print(res)

Fixed submission:
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,k,l=map(int,input().split())
def maketree(n,k,target):
    road=[]
    roadidx=[-1 for _ in range(n)]
    for i in range(len(target)):
        p=target[i][0]
        q=target[i][1]
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road.append({p,q})
            roadidx[p]=len(road)-1
            roadidx[q]=len(road)-1
        elif pidx==-1 and qidx!=-1:
            road[roadidx[q]]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[roadidx[p]]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            x=road[roadidx[p]]|road[roadidx[q]]
            y=min(pidx,qidx)
            z=max(pidx,qidx)
            road[y]=x
            road[z]=x
            for j in x:
                roadidx[j]=y
    resroad=[]
    for i in road:
        if i not in resroad:resroad.append(i)
    return resroad

road = []
for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        road.append([p,q])
metro=[]
for i in range(l):
        r,s=map(int,input().split())
        r-=1
        s-=1
        metro.append([r,s])
roadtree=maketree(n,k,road)
metrotree=maketree(n,l,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]=len(x)
        
res=''
for i in range(n):
    res=res+str(result[i])+' '
print(res)

Fixed submission:
import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])