Problem:


Score : 400 points

Problem Statement

There are N cities. There are also K roads and L railways, extending between the cities.
The i-th road bidirectionally connects the p_i-th and q_i-th cities, and the i-th railway bidirectionally connects the r_i-th and s_i-th cities.
No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads.
We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

2 ≦ N ≦ 2*10^5

1 ≦ K, L≦ 10^5

1 ≦ p_i, q_i, r_i, s_i ≦ N

p_i < q_i

r_i < s_i

When i ≠ j, (p_i, q_i) ≠ (p_j, q_j)

When i ≠ j, (r_i, s_i) ≠ (r_j, s_j)

Input

The input is given from Standard Input in the following format:

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1, respectively.

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Sample Output 3

1 1 2 1 2 2 2



Sample input:
4 3 1
1 2
2 3
3 4
2 3


Sample output:
1 2 2 1

Submission status: Wrong Answer

Solution code:
class UnionFind(object):

    def __init__(self, n):
        # 親のnodeを表す
        self.par = [i for i in range(n)]

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            # 経路圧縮
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

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

        self.par[x] = y


class UnionFindRankCount(UnionFind):

    def __init__(self, n):
        UnionFind.__init__(self, n)

        self.rank = [0 for _ in range(n)]
        self.count = [1 for _ in range(n)]

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

def _abc049_d():
    """連結"""

    N, K, L = list(map(int, input().split(' ')))
    ur = UnionFindRankCount(N)
    for _ in range(K):
        p, q = list(map(int, input().split(' ')))
        p -= 1
        q -= 1
        ur.union(p, q)

    ut = UnionFindRankCount(N)
    for _ in range(L):
        r, s = list(map(int, input().split(' ')))
        r -= 1
        s -= 1
        if ur.same(r, s):
            ut.union(r, s)

    for n in range(N):
        print(ut.count[ut.root(n)], end=' ')

_abc049_d()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K, L = map(int, input().split())
roads = [list(map(int, input().split())) for i in range(K)]
trains = [list(map(int, 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 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)


road_uf = UnionFind(N)
train_uf = UnionFind(N)

for p, q in roads:
    road_uf.union(p, q)

for r, s in trains:
    train_uf.union(r, s)

road_par = road_uf.par
train_par = train_uf.par

ans = []
d = defaultdict(int)
for i in range(1, N+1):
    d[road_par[i], train_par[i]] += 1
ans = (d[road_par[i], train_par[i]] for i in range(1, N+1))

print(' '.join(str(i) for i in ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K, L = map(int, input().split())
roads = [list(map(int, input().split())) for i in range(K)]
trains = [list(map(int, 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 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)


road_uf = UnionFind(N)
train_uf = UnionFind(N)

for p, q in roads:
    road_uf.union(p, q)

for r, s in trains:
    train_uf.union(r, s)

road_par = road_uf.par
train_par = train_uf.par

ans = []
d = defaultdict(int)
for i in range(1, N+1):
    d[road_par[i], train_par[i]] += 1
print(d)
ans = (d[road_par[i], train_par[i]] for i in range(1, N+1))

print(' '.join(str(i) for i in ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K, L = map(int, input().split())
roads = [list(map(int, input().split())) for i in range(K)]
trains = [list(map(int, 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:
            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)


road_uf = UnionFind(N)
train_uf = UnionFind(N)

for p, q in roads:
    road_uf.union(p, q)

for r, s in trains:
    train_uf.union(r, s)

road_par = road_uf.par
train_par = train_uf.par

ans = []
d = defaultdict(int)
for i in range(1, N+1):
    d[road_par[i], train_par[i]] += 1
ans = (d[road_par[i], train_par[i]] for i in range(1, N+1))

print(' '.join(str(i) for i in ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N, K, L = map(int, input().split())
roads = [list(map(int, input().split())) for i in range(K)]
trains = [list(map(int, 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:
            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)


road_uf = UnionFind(N)
train_uf = UnionFind(N)

for p, q in roads:
    road_uf.union(p, q)

for r, s in trains:
    train_uf.union(r, s)

road_par = road_uf.par
train_par = train_uf.par

ans = []
d = defaultdict(int)
for i in range(N):
    d[road_par[i], train_par[i]] += 1
ans = (d[road_par[i], train_par[i]] for i in range(N))

print(' '.join(str(i) for i in ans))

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter

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

nl=[ [] for i in range(N+1) ]

c1=set()

for i in range(K):
	p,q=map(int, raw_input().split())
	nl[p].append(q)
	nl[q].append(p)
	c1.add(p)
	c1.add(q)



nl2=[ [] for i in range(N+1) ]
c2=set()

for i in range(L):
	p,q=map(int, raw_input().split())
	nl2[p].append(q)
	nl2[q].append(p)
	c2.add(p)
	c2.add(q)


v1=[ None for i in range(N+1) ]
v2=[ None for i in range(N+1) ]
l=[ "" for i in range(N+1) ]

def bfs(start,nl,V,num):
	q = deque([]) 
	V[start]=1
	l[start]+=str(num)
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				l[i]+=str(num)
			
	return V


num=1	#group number
for i in c1:
	if v1[i] is None:
		bfs(i,nl,v1,num)
		num+=1
for i in c2:
	if v2[i] is None:
		bfs(i,nl2,v2,num)
		num+=1


C=Counter(l)

ans=[]
for i in range(1,N+1):
	if len(l[i])==1:
		ans.append(str(1))
	else:
		ans.append(str(C[l[i]]))


print " ".join(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter

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

nl=[ [] for i in range(N+1) ]

c1=set()

for i in range(K):
	p,q=map(int, raw_input().split())
	nl[p].append(q)
	nl[q].append(p)
	c1.add(p)
	c1.add(q)



nl2=[ [] for i in range(N+1) ]
c2=set()

for i in range(L):
	p,q=map(int, raw_input().split())
	nl2[p].append(q)
	nl2[q].append(p)
	c2.add(p)
	c2.add(q)


v1=[ None for i in range(N+1) ]
v2=[ None for i in range(N+1) ]
l=[ "" for i in range(N+1) ]

def bfs(start,nl,V,num):
	q = deque([]) 
	V[start]=1
	l[start]+=str(num)
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				l[i]+=str(num)
			
	return V


num=1	#group number
for i in c1:
	if v1[i] is None:
		bfs(i,nl,v1,num)
		num+=1
for i in c2:
	if v2[i] is None:
		bfs(i,nl2,v2,num)
		num+=1

C=Counter(l)


for i in range(1,N+1):
	if len(l[i])==1:
		print 1,
	else:
		print C[ l[i] ],

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter

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

nl=[ [] for i in range(N+1) ]

c1=set()

for i in range(K):
	p,q=map(int, raw_input().split())
	nl[p].append(q)
	nl[q].append(p)
	c1.add(p)
	c1.add(q)



nl2=[ [] for i in range(N+1) ]
c2=set()

for i in range(L):
	p,q=map(int, raw_input().split())
	nl2[p].append(q)
	nl2[q].append(p)
	c2.add(p)
	c2.add(q)


v1=[ None for i in range(N+1) ]
v2=[ None for i in range(N+1) ]
l=[ "" for i in range(N+1) ]

def bfs(start,nl,V):
	q = deque([]) 
	V[start]=1
	l[start]+=str(start)
	q.append(start)

	while len(q)!=0:
		v=q.popleft()
		for i in nl[v]:
			if V[i] is None:
				V[i]=1
				q.append(i)
				l[i]+=str(start)
			
	return V



for i in c1:
	if v1[i] is None:
		bfs(i,nl,v1)

for i in c2:
	if v2[i] is None:
		bfs(i,nl2,v2)

C=Counter(l)


for i in range(1,N+1):
	if len(l[i])==1:
		print 1,
	else:
		print C[ l[i] ],

Submission status: Wrong Answer

Solution code:
N, K, L = map(int, input().split())
u1, u2 = list(range(N+1)), list(range(N+1))

def root(u, r):
    if u[r] == r:
        return r
    u[r] = root(u, u[r])
    return u[r]

def update(u, r, n):
    u[n] = root(u, r)

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

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

c = {}
rs = [(root(u1, i), root(u2, i)) for i in range(1, N+1)]
for r in rs:
    if r in c:
        c[r] += 1
    else:
        c[r] = 1
 
print(' '.join(map(str, [c[r] for r in rs])))

Submission status: Wrong Answer

Solution code:
N, K, L = map(int, input().split())
u1, u2 = list(range(N+1)), list(range(N+1))

def root(u, r):
    if u[r] == r:
        return r
    u[r] = root(u, u[r])
    return u[r]

def update(u, r, n):
    u[n] = root(u, r)

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

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

c = {}
for i in range(1, N+1):
    t = root(u1, i), root(u2, i)
    if t in c:
        c[t] += 1
    else:
        c[t] = 1
 
print(' '.join(map(str, [c[root(u1, i), root(u2, i)] for i in range(1, N+1)])))

Submission status: Wrong Answer

Solution code:
N, K, L = map(int, input().split())
u1, u2 = list(range(N+1)), list(range(N+1))

def root(u, r):
    if u[r] == r:
        return r
    u[r] = root(u, u[r])
    return u[r]

def update(u, r, n):
    u[n] = root(u, r)
    return u[n]

for i in range(K):
    p, q = map(int, input().split())
    u1[p] = update(u1, p, q)

for i in range(L):
    r, s = map(int, input().split())
    u2[r] = update(u2, r, s)

for i in range(1, N+1):
    u1[i] = root(u1, i)
    u2[i] = root(u2, i)

c = {}
for i in range(1, N+1):
    t = u1[i], u2[i]
    if t in c:
        c[t] += 1
    else:
        c[t] = 1
 
print(' '.join(map(str, [c[u1[i], u2[i]] for i in range(1, N+1)])))

Submission status: Wrong Answer

Solution code:
N, K, L = map(int, input().split())
u1, u2 = list(range(N+1)), list(range(N+1))

def root(u, r):
    if u[r] == r:
        return r
    u[r] = root(u, u[r])
    return u[r]

def update(u, r, n):
    u[n] = root(u, r)

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

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

for i in range(1, N+1):
    u1[i] = root(u1, i)
    u2[i] = root(u2, i)

c = {}
for i in range(1, N+1):
    t = u1[i], u2[i]
    if t in c:
        c[t] += 1
    else:
        c[t] = 1
print(' '.join(map(str, [c[u1[i], u2[i]] for i in range(1, N+1)])))

Submission status: Wrong Answer

Solution code:
N, K, L = map(int, input().split())
u1 = [i for i in range(N)]
u2 = [i for i in range(N)]

def root(u, n):
    if u[n] == n:
        return n
    else:
        t = root(u, u[n])
        u[n] = t
        return t

def update(u, r, n):
    u[n] = root(u, r)

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

for i in range(L):
    r, s = map(int, input().split())
    r -= 1
    s -= 1
    update(u2, r, s)

p = [(root(u1, i), root(u2, i)) for i in range(N)]
ans = {}
for x in p:
    if x not in ans:
        ans[x] = 1
    else:
        ans[x] += 1
print(' '.join(map(str, [ans[x] for x in p])))

Submission status: Wrong Answer

Solution code:
N, K, L = map(int, input().split())
u1 = [i for i in range(N+1)]
u2 = [i for i in range(N+1)]

def root(u, n):
    if u[n] == n:
        return n
    else:
        t = root(u, u[n])
        u[n] = t
        return t

def update(u, r, n):
    u[n] = root(u, r)

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

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

p = [(root(u1, i), root(u2, i)) for i in range(1, N+1)]
ans = {}
for i in range(N):
    if p[i] not in ans:
        ans[p[i]] = 1
    else:
        ans[p[i]] += 1
print(' '.join(map(str, [ans[p[i]] for i in range(N)])))

Submission status: Wrong Answer

Solution code:
n,k,l=[int(x) for x in input().split()]
from collections import deque
road=[[i] for i in range(n)]
rail=[[i] for i in range(n)]
for i in [0]*k:
    p,q=[int(x)-1 for x in input().split()]
    road[p].append(q)
    road[q].append(p)
for i in [0]*l:
    r,s=[int(x)-1 for x in input().split()]
    rail[r].append(s)
    rail[s].append(r)
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(road[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        for j in road[tmp]:
            if flag[j] ==0:
                d.append(j)
                road[i].append(j)
                flag[j]=1
    for k in road[i]:
        road[k]=road[i]
flag=[0]*n
for i in range(n):
    if flag[i]==1:
        continue
    flag[i]=1
    d=deque(rail[i])
    while d:
        tmp=d.popleft()
        if flag[tmp]==1:
            continue
        flag[tmp]=1
        for j in rail[tmp]:
            if flag[j] ==0:
                d.append(j)
                rail[i].append(j)
                flag[j]=1
    for k in rail[i]:
        rail[k]=rail[i]
ans=[]
for i,j in zip(road,rail):
    ans.append(str(len(set(i)&set(j))))
print(" ".join(ans))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 5 + 1)


class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))

    def is_same_set(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

    def union_set(self, x: int, y: int):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return

        self.parent[x] = y

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


def main():
    N, K, L = map(int, input().split())
    uf1 = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        uf1.union_set(p, q)

    uf2 = UnionFind(N)
    for _ in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        if uf1.is_same_set(r, s):
            uf2.union_set(r, s)

    for x in range(N):
        uf2.find_root(x)

    d = defaultdict(int)
    for x in uf2.parent:
        d[x] += 1

    print(" ".join([str(d[uf2.parent[x]]) for x in range(N)]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 1)


class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))

    def is_same_set(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

    def union_set(self, x: int, y: int):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return

        self.parent[x] = y

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


def main():
    N, K, L = map(int, input().split())
    uf1 = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        uf1.union_set(p, q)

    uf2 = UnionFind(N)
    for _ in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        if uf1.is_same_set(r, s):
            uf2.union_set(r, s)

    d = defaultdict(int)
    for x in uf2.parent:
        d[x] += 1

    print(" ".join([str(d[uf2.parent[x]]) for x in range(N)]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K,L=map(int,input().split())
pq=[list(map(int,input().split())) for i in range(K)]
rs=[list(map(int,input().split())) for i in range(L)]
dict_load={i+1:i+1 for i in range(N)}
dict_rail={i+1:i+1 for i in range(N)}

for i in range(K):
  if dict_load[pq[i][0]]!=dict_load[pq[i][1]]:
    for j in range(N):
      if dict_load[j+1]==max(dict_load[pq[i][0]],dict_load[pq[i][1]]):
        dict_load[j+1]=min(dict_load[pq[i][0]],dict_load[pq[i][1]])
for i in range(L):
  if dict_rail[rs[i][0]]!=dict_rail[rs[i][1]]:
    for j in range(N):
      if dict_rail[j+1]==max(dict_rail[rs[i][0]],dict_rail[rs[i][1]]):
        dict_rail[j+1]=min(dict_rail[rs[i][0]],dict_rail[rs[i][1]])

#group=[[dict_load[j+1],dict_rail[j+1]] for j in range(N)]
#dict_load_rail={}
#for j in range(N):
#  if (dict_load[j+1],dict_rail[j+1]) in dict_load_rail:
#    dict_load_rail[(dict_load[j+1],dict_rail[j+1])]+=1
#  else:
#    dict_load_rail[(dict_load[j+1],dict_rail[j+1])]=1
#for j in range(N):
#  print(dict_load_rail[(dict_load[j+1],dict_rail[j+1])])

Submission status: Wrong Answer

Solution code:
N,K,L=map(int,input().split())
pq=[list(map(int,input().split())) for i in range(K)]
rs=[list(map(int,input().split())) for i in range(L)]
dict_load={i+1:i+1 for i in range(N)}
dict_rail={i+1:i+1 for i in range(N)}

for i in range(K):
  if dict_load[pq[i][0]]!=dict_load[pq[i][1]]:
    for j in range(N):
      if dict_load[j+1]==max(dict_load[pq[i][0]],dict_load[pq[i][1]]):
        dict_load[j+1]=min(dict_load[pq[i][0]],dict_load[pq[i][1]])
for i in range(L):
  if dict_rail[rs[i][0]]!=dict_rail[rs[i][1]]:
    for j in range(N):
      if dict_rail[j+1]==max(dict_rail[rs[i][0]],dict_rail[rs[i][1]]):
        dict_rail[j+1]=min(dict_rail[rs[i][0]],dict_rail[rs[i][1]])

group=[[dict_load[j+1],dict_rail[j+1]] for j in range(N)]
dict_load_rail={}
for j in range(N):
  if (dict_load[j+1],dict_rail[j+1]) in dict_load_rail:
    dict_load_rail[(dict_load[j+1],dict_rail[j+1])]+=1
  else:
    dict_load_rail[(dict_load[j+1],dict_rail[j+1])]=1
#for j in range(N):
#  print(dict_load_rail[(dict_load[j+1],dict_rail[j+1])])

Submission status: Wrong Answer

Solution code:
from collections import Counter

class Sets:
  def __init__(self, n):
    self.alias = [i for i in range(n)]
  def get_id(self, e):
    i = e
    while(self.alias[i] < i):
      i = self.alias[i]
    return i
  def add_same_pair(self, a, b): # 0 <= a < b < N
    self.alias[b] = min(self.get_id(b), a)
  def get_ids(self):
    return [self.get_id(i) for i in range(len(self.alias))]
  def __str__(self):
    return str(self.alias)

N,K,L = map(int, raw_input().split())
road_sets = Sets(N)
rail_sets = Sets(N)

for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  road_sets.add_same_pair(p,q)

for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  rail_sets.add_same_pair(r,s)

road_ids = road_sets.get_ids()
rail_ids = rail_sets.get_ids()

combi_list = []
for i in range(N):
  combi_list.append((road_ids[i], rail_ids[i]))
stats = Counter(combi_list)

result = [1 for i in range(N)]
for i in range(N):
  result[i] = stats[(road_ids[i],rail_ids[i])]
print ' '.join(map(str, result))

Submission status: Wrong Answer

Solution code:
from collections import Counter

class Sets:
  def __init__(self, n):
    self.alias = [i for i in range(n)]
  def get_id(self, e):
    i = e
    while(self.alias[i] < i):
      i = self.alias[i]
    return i
  def add_same_pair(self, a, b): # 0 <= a < b < N
    self.alias[b] = min(self.alias[b], a)
  def get_ids(self):
    return [self.get_id(i) for i in range(len(self.alias))]
  def __str__(self):
    return str(self.alias)

N,K,L = map(int, raw_input().split())
road_sets = Sets(N)
rail_sets = Sets(N)

for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  road_sets.add_same_pair(p,q)

for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  rail_sets.add_same_pair(r,s)

road_ids = road_sets.get_ids()
rail_ids = rail_sets.get_ids()

combi_list = []
for i in range(N):
  combi_list.append((road_ids[i], rail_ids[i]))
stats = Counter(combi_list)

result = [1 for i in range(N)]
for i in range(N):
  result[i] = stats[(road_ids[i],rail_ids[i])]
print ' '.join(map(str, result))

Submission status: Wrong Answer

Solution code:
from collections import Counter

class Sets:
  def __init__(self, n):
    self.alias = [i for i in range(n)]
  def get_id(self, e):
    i = e
    while(self.alias[i] < i):
      i = self.alias[i]
    return i
  def add_same_pair(self, a, b): # 0 <= a < b < N
    self.alias[b] = a
  def get_ids(self):
    return [self.get_id(i) for i in range(len(self.alias))]
  def __str__(self):
    return str(self.alias)

N,K,L = map(int, raw_input().split())
road_sets = Sets(N)
rail_sets = Sets(N)

for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  road_sets.add_same_pair(p,q)

for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  rail_sets.add_same_pair(r,s)

road_ids = road_sets.get_ids()
rail_ids = rail_sets.get_ids()

combi_list = []
for i in range(N):
  combi_list.append((road_ids[i], rail_ids[i]))
stats = Counter(combi_list)

result = [1 for i in range(N)]
for i in range(N):
  result[i] = stats[(road_ids[i],rail_ids[i])]
print ' '.join(map(str, result))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, raw_input().split())
roads = [-1 for i in range(N)]
rails = [-1 for i in range(N)]
same_roads = {}
same_rails = {}

max_road_id = -1
for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  if roads[p] < 0 and roads[q] < 0:
    max_road_id += 1
    roads[p] = max_road_id
    roads[q] = max_road_id
  elif roads[p] == roads[q]:
    continue
  elif roads[p] >= 0 and roads[q] < 0:
    roads[q] = roads[p]
  elif roads[q] < 0 and roads[q] >= 0:
    roads[p] = roads[q]
  else:
    same_roads[max(roads[p],roads[q])] = min(roads[p],roads[q]) 
distinct_roads = [i for i in range(max_road_id + 1)]
for road_id in range(max_road_id, -1, -1):
  if road_id in same_roads:
    distinct_roads[road_id] = same_roads[road_id]
 
max_rail_id = -1
for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  if rails[r] < 0 and rails[s] < 0:
    max_rail_id += 1
    rails[r] = max_rail_id
    rails[s] = max_rail_id
  elif rails[r] == rails[s]:
    continue
  elif rails[r] >= 0 and rails[s] < 0:
    rails[s] = rails[r]
  elif rails[r] < 0 and rails[s] >= 0:
    rails[r] = rails[s]
  else:
    same_rails[max(rails[r],rails[s])] = min(rails[r],rails[s])
distinct_rails = [i for i in range(max_rail_id + 1)]
for rail_id in range(max_rail_id, -1, -1):
  if rail_id in same_rails:
    distinct_rails[rail_id] = same_rails[rail_id]

combi_counts = {}
for i in range(N):
  if roads[i] < 0 or rails[i] < 0:
    continue
  d_road = distinct_roads[roads[i]]
  d_rail = distinct_rails[rails[i]] 
  if (d_road,d_rail) in combi_counts:
    combi_counts[(d_road,d_rail)] += 1
  else:
    combi_counts[(d_road,d_rail)] = 1

result = []
for i in range(N):
  if roads[i] < 0 or rails[i] < 0:
    result.append(1)
  else:
    d_road = distinct_roads[roads[i]]
    d_rail = distinct_rails[rails[i]] 
    result.append(combi_counts[(d_road,d_rail)])
print ' '.join(map(str, result))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, raw_input().split())
roads = [-1 for i in range(N)]
rails = [-1 for i in range(N)]
same_roads = {}
same_rails = {}

road_id = 0
for i in range(K):
  p,q = map(int, raw_input().split())
  p -= 1
  q -= 1
  if roads[p] < 0 and roads[q] < 0:
    road_id += 1
    roads[p] = road_id
    roads[q] = road_id
  elif roads[p] == roads[q]:
    continue
  elif roads[p] >= 0 and roads[q] < 0:
    roads[q] = roads[p]
  elif roads[q] < 0 and roads[q] >= 0:
    roads[p] = roads[q]
  else:
    same_roads[max(roads[p],roads[q])] = min(roads[p],roads[q])
for k in sorted(same_roads.keys(), reverse=True):
  for i in range(N):
    if roads[i] == k: roads[i] = same_roads[k]

rail_id = 0
for i in range(L):
  r,s = map(int, raw_input().split())
  r -= 1
  s -= 1
  if rails[r] < 0 and rails[s] < 0:
    rail_id += 1
    rails[r] = rail_id
    rails[s] = rail_id
  elif roads[r] == roads[s]:
    continue
  elif rails[r] >= 0 and rails[s] < 0:
    rails[s] = rails[r]
  elif rails[r] < 0 and rails[s] >= 0:
    rails[r] = rails[s]
  else:
    same_rails[max(rails[r],rails[s])] = min(rails[r],rails[s])
for k in sorted(same_rails.keys(), reverse=True):
  for i in range(N):
    if rails[i] == k: rails[i] = same_rails[k]

combi_counts = {}
for i in range(N):
  if (roads[i],rails[i]) in combi_counts:
    combi_counts[(roads[i],rails[i])] += 1
  else:
    combi_counts[(roads[i],rails[i])] = 1

result = []
for i in range(N):
  if roads[i] < 0 or rails[i] < 0:
    result.append(1)
  else:
    result.append(combi_counts[(roads[i],rails[i])])
print ' '.join(map(str, result))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, K, L = map(int, input().split())
    Adj_r = [[] for i in range(N)]
    Adj_t = [[] for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p, q = p-1, q-1
        Adj_r[p].append(q)
        Adj_r[q].append(p)

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

    col = 0
    v_cols = [None] * N

    for u in range(N):
        if v_cols[u] is None:
            bfs_color(N, Adj_r, v_cols, u, col)
            col += 1

    # debug(v_cols, locals())

    checked = [False] * N
    renketu = []

    for u in range(N):
        if not checked[u]:
            renketu.append(bfs_renketu(N, Adj_t, v_cols, checked, u))

    # debug(renketu, locals())

    ans = [None] * N

    for lst in renketu:
        for u in lst:
            ans[u] = len(lst)

    print(*ans)

def bfs_color(N, Adj_r, v_cols, u, col):
    v_cols[u] = col
    nxts = deque([u])

    while nxts:
        v = nxts.popleft()

        for w in Adj_r[v]:
            if v_cols[w] is None:
                v_cols[w] = col
                nxts.append(w)


def bfs_renketu(N, Adj_t, v_cols, checked, u):
    checked[u] = True
    res = [u]
    nxts = deque([u])

    while nxts:
        v = nxts.popleft()

        for w in Adj_t[v]:
            if not checked[w] and v_cols[v] == v_cols[w]:
                checked[w] = True
                nxts.append(w)
                res.append(w)

    return res

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, K, L = map(int, input().split())
    Adj_r = [[] for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p, q = p-1, q-1
        Adj_r[p].append(q)
        Adj_r[q].append(p)

    col = 0
    v_cols = [None] * N

    for u in range(N):
        if v_cols[u] is None:
            bfs_color(N, Adj_r, v_cols, u, col)
            col += 1

    # debug(v_cols, locals())

    Adj_t = [[] for i in range(N)]

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

    checked = [False] * N
    renketu = []

    for u in range(N):
        if not checked[u]:
            renketu.append(bfs_renketu(N, Adj_t, v_cols, checked, u))

    # debug(renketu, locals())

    ans = [0] * N

    for lst in renketu:
        for u in lst:
            ans[u] = len(lst)

    print(*ans)

def bfs_color(N, Adj_r, v_cols, u, col):
    v_cols[u] = col
    nxts = deque([u])

    while nxts:
        v = nxts.popleft()

        for w in Adj_r[v]:
            if v_cols[w] is None:
                v_cols[w] = col
                nxts.append(w)


def bfs_renketu(N, Adj_t, v_cols, checked, u):
    checked[u] = True
    res = [u]
    nxts = deque([u])

    while nxts:
        v = nxts.popleft()

        for w in Adj_t[v]:
            if not checked[w] and v_cols[v] == v_cols[w]:
                checked[w] = True
                nxts.append(w)
                res.append(w)

    return res

if __name__ == '__main__':
    solve()