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
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] & 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:
                    print q
                    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] & res_train[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])
        is_visited[i] = True
        res[i] = set([i])
        while 1:
            print que
            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])]
        if p not in road:
            road[p] = [q]
        else:
            road[p].append(q)

        if q not in road:
            road[q] = [p]
        else:
            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])]
        if p not in train:
            train[p] = [q]
        else:
            train[p].append(q)

        if q not in train:
            train[q] = [p]
        else:
            train[q].append(p)

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

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




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split())

#print(N,K,L,D,T)

list_D = [list([i]) for i in range(N)]
list_T = [list([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

def execOne(num, list, root):
    for _ in range(num):
        d0, d1 = map(int, input().split())
        d0 = d0 - 1
        d1 = d1 - 1
        r0 = root[d0]
        r1 = root[d1]
        for l in list[r1]:
            root[l] = r0
        list[r0].extend(list[r1])
        #print(d0, d1, list, root)

execOne(K, list_D, root_D)
execOne(L, list_T, root_T)

#和集合
res = [0] * N

print(" ".join([str(i) for i in res]))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split())

#print(N,K,L,D,T)

list_D = [set([i]) for i in range(N)]
list_T = [set([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

#print(list_D)

for _ in range(K):
    d0, d1 = map(int, input().split())
    d0 = d0 - 1
    d1 = d1 - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    list_D[r0] = list_D[r0] | list_D[r1]
    root_D[r1] = r0
    root_D[d1] = r0
    #print(list_D, root_D)

for _ in range(L):
    t0, t1 = map(int, input().split())
    t0 = t0 - 1
    t1 = t1 - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    list_T[r0] = list_T[r0] | list_T[r1]
    root_T[r1] = r0
    root_T[t1] = r0
    #print(list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = list_D[rd]
    t = list_T[rt]
    res[i] = len(d & t)
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(K)]
T = [list(map(int, input().split())) for _ in range(L)]

#print(N,K,L,D,T)

list_D = [set([i]) for i in range(N)]
list_T = [set([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

#print(list_D)

for d in D:
    d0 = d[0] - 1
    d1 = d[1] - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    list_D[r0] = list_D[r0] | list_D[r1]
    root_D[r1] = r0
    root_D[d1] = r0
    #print(list_D, root_D)

for t in T:
    t0 = t[0] - 1
    t1 = t[1] - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    list_T[r0] = list_T[r0] | list_T[r1]
    root_T[r1] = r0
    root_T[t1] = r0
    #print(list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = list_D[rd]
    t = list_T[rt]
    res[i] = len(d & t)
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(K)]
T = [list(map(int, input().split())) for _ in range(L)]

#print(N,K,L,D,T)

list_D = [set([i]) for i in range(N)]
list_T = [set([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

#print(list_D)

for d in D:
    d0 = d[0] - 1
    d1 = d[1] - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    a = list_D[r0]
    b = list_D[r1]
    c = a | b
    list_D[r0] = c
    root_D[r1] = r0
    root_D[d1] = r0
    #print(list_D, root_D)

for t in T:
    t0 = t[0] - 1
    t1 = t[1] - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    a = list_T[r0]
    b = list_T[r1]
    c = a | b
    list_T[r0] = c
    root_T[r1] = r0
    root_T[t1] = r0
    #print(list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = list_D[rd]
    t = list_T[rt]
    res[i] = len(d & t)
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(K)]
T = [list(map(int, input().split())) for _ in range(L)]

#print(N,K,L,D,T)

list_D = [set([i]) for i in range(N)]
list_T = [set([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

#print(list_D)

for d in D:
    d0 = d[0] - 1
    d1 = d[1] - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    a = list_D[r0]
    b = list_D[r1]
    c = a | b
    list_D[r0] = c
    root_D[r1] = r0
    root_D[d1] = r0
    #print(list_D, root_D)

for t in T:
    t0 = t[0] - 1
    t1 = t[1] - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    a = list_T[r0]
    b = list_T[r1]
    c = a | b
    list_T[r0] = c
    root_T[r1] = r0
    root_T[d1] = r0
    #print(list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = list_D[rd]
    t = list_T[rt]
    res[i] = len(d & t)
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(K)]
T = [list(map(int, input().split())) for _ in range(L)]

#print(N,K,L,D,T)

list_D = [set([i]) for i in range(N)]
list_T = [set([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

#print(list_D)

for d in D:
    d0 = d[0] - 1
    d1 = d[1] - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    a = list_D[r0]
    b = list_D[r1]
    c = a | b
    list_D[r0] = c
    root_D[r1] = r0
    #print(list_D, root_D)

for t in T:
    t0 = t[0] - 1
    t1 = t[1] - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    a = list_T[r0]
    b = list_T[r1]
    c = a | b
    list_T[r0] = c
    root_T[r1] = r0
    #print(list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = list_D[rd]
    t = list_T[rt]
    res[i] = len(d & t)
#print(*(res[i] for i in range(N)))
print(" ".join([str(i) for i in res]))

Submission status: Wrong Answer

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

Group1=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ
Group2=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find1(x):#find(a)=find(b)のとき同じグループ
    while Group1[x] != x:
        x=Group1[x]
    return x

def Union1(x,y):#xとyが同じグループになるよう更新
    if find1(x) != find1(y):
        Group1[find1(y)]=Group1[find1(x)]=min(find1(y),find1(x))

def find2(x):#find(a)=find(b)のとき同じグループ
    while Group2[x] != x:
        x=Group2[x]
    return x

def Union2(x,y):#xとyが同じグループになるよう更新
    if find2(x) != find2(y):
        Group2[find2(y)]=Group2[find2(x)]=min(find2(y),find2(x))

for i,j in R:
    Union1(i,j)

for i,j in T:
    Union2(i,j)

Grin1=[set() for i in range(N+1)]
Grin2=[set() for i in range(N+1)]

for i in range(1,N+1):
    Grin1[Group1[i]].add(i)
    Grin2[Group2[i]].add(i)

for i in range(1,N+1):
    print(len(Grin1[find1(i)] & Grin2[find2(i)]))

Submission status: Wrong Answer

Solution code:
N,K,L = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(K)]
T = [list(map(int, input().split())) for _ in range(L)]

#print(N,K,L,D,T)

list_D = [set([i]) for i in range(N)]
list_T = [set([i]) for i in range(N)]
root_D = [i for i in range(N)]
root_T = [i for i in range(N)]

#print(list_D)

for d in D:
    d0 = d[0] - 1
    d1 = d[1] - 1
    r0 = root_D[d0]
    r1 = root_D[d1]
    a = list_D[r0]
    b = list_D[r1]
    c = a | b
    list_D[r0] = c
    root_D[r1] = r0
    #print(list_D, root_D)

for t in T:
    t0 = t[0] - 1
    t1 = t[1] - 1
    r0 = root_T[t0]
    r1 = root_T[t1]
    a = list_T[r0]
    b = list_T[r1]
    c = a | b
    list_T[r0] = c
    root_T[r1] = r0
    #print(list_T, root_T)

#和集合
res = [0] * N
for i in range(N):
    rd = root_D[i]
    rt = root_T[i]
    d = list_D[rd]
    t = list_T[rt]
    res[i] = len(d & t)
print(*(res[i] for i in range(N)))

Submission status: Wrong Answer

Solution code:
N, K , L = map(int, input().split())
check1 = [0] * N
check2 = [0] * N
ans = [0] * N
for i in range(K):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    check1[a] = 1
    check1[b] = 1
    
for i in range(L):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    check2[a] = 1
    check2[b] = 1
    
for i in range(N):
    ans[i] = check1[i] + check2[i]
print(' '.join(map(str, ans)))

Submission status: Wrong Answer

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


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


def unite(a, x, y):
    X = find(a, x)
    Y = find(a, y)
    M = max(X, Y)
    a[x], a[y], a[X], a[Y] = M, M, M, M


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

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

Submission status: Wrong Answer

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


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


def unite(a, 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()]


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = max(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[find(a_road, i), find(a_railway, i)] = memo.get(
        (a_road[i], 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()]


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


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


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

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

Submission status: Wrong Answer

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


def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]


def unite(a, x, y):
    if find(a, x) != find(a, y):
        a[x] = min(find(a, x), find(a, 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[find(a_road, i), find(a_railway, i)] = memo.get(
        (find(a_road, i), find(a_railway, i)), 0) + 1

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

Submission status: Wrong Answer

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

par = [i for i in range(2 * N)]


def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    par[x] = min(find(x), find(y))
    par[y] = par[x]


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

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

Submission status: Wrong Answer

Solution code:
class UFT():
    def __init__(self):
        self.par = {}
        self.rank = {}

    def find(self, x):
        if self.par.get(x, 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 x == y:
            return

        self.rank[x] = self.rank.get(x, 0)
        self.rank[y] = self.rank.get(y, 0)

        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(self, x, y):
        return self.find(x) == self.find(y)
    
    def root(self, x):
        return self.par.get(x, x)


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

C = UFT()
for _ in range(K):
    p, q = [int(_) for _ in input().split()]
    C.unite(p, q)
for _ in range(L):
    r, s = [int(_) for _ in input().split()]
    C.unite(r + N, s + N)
memo = {}
for i in range(1, N + 1):
    memo[C.root(i) - 1, C.root(i + N) - N - 1] = memo.get((C.root(i) - 1, C.root(i + N) - N - 1), 0) + 1
print(' '.join(str(memo[C.root(i) - 1, C.root(i + N) - N - 1]) for i in range(1, N + 1)))

Submission status: Wrong Answer

Solution code:
N, K, L = [int(_) for _ in input().split()]
PQ = sorted([sorted([int(_) for _ in input().split()]) for _ in range(K)], key = lambda xs: xs[0])
RS = sorted([sorted([int(_) for _ in input().split()]) for _ in range(L)], key = lambda xs: xs[0])

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

for pq in PQ:
    road_train[pq[0]][0] = min(road_train[pq[0]][0], road_train[pq[1]][0])
    road_train[pq[1]][0] = road_train[pq[0]][0]
for rs in RS:
    road_train[rs[0]][1] = min(road_train[rs[0]][1], road_train[rs[1]][1])
    road_train[rs[1]][1] = road_train[rs[0]][1]

Submission status: Wrong Answer

Solution code:
N, K, L = [int(_) for _ in input().split()]
PQ = sorted([[int(_) for _ in input().split()] for _ in range(K)], key = lambda xs: xs[0] * 300000 + xs[1])
RS = sorted([[int(_) for _ in input().split()] for _ in range(L)], key = lambda xs: xs[0] * 300000 + xs[1])

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

for i in range(K):
    road_train[PQ[i][1]][0] = road_train[PQ[i][0]][0]
for i in range(L):
    road_train[RS[i][1]][1] = road_train[RS[i][0]][1]

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
result = []
for i in range(1, N + 1):
    dp[road_train[i][0]][road_train[i][1]] += 1
for i in range(1, N + 1):
    result += [str(dp[road_train[i][0]][road_train[i][1]])]

print(' '.join(result))

Submission status: Wrong Answer

Solution code:
N, K, L = [int(_) for _ in input().split()]
PQ = sorted([sorted([int(_) for _ in input().split()]) for _ in range(K)], key = lambda xs: xs[0])
RS = sorted([sorted([int(_) for _ in input().split()]) for _ in range(L)], key = lambda xs: xs[0])

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

for pq in PQ:
    road_train[pq[1]][0] = road_train[pq[0]][0]
for rs in RS:
    road_train[rs[1]][1] = road_train[rs[0]][1]

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
result = []
for i in range(1, N + 1):
    dp[road_train[i][0]][road_train[i][1]] += 1
for i in range(1, N + 1):
    result += [str(dp[road_train[i][0]][road_train[i][1]])]

print(' '.join(result))

Submission status: Wrong Answer

Solution code:
N, K, L = [int(_) for _ in input().split()]
PQ = sorted([sorted([int(_) for _ in input().split()]) for _ in range(K)], key = lambda xs: xs[0])
RS = sorted([sorted([int(_) for _ in input().split()]) for _ in range(L)], key = lambda xs: xs[0])

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

for pq in PQ:
    road_train[pq[1]][0] = road_train[pq[0]][0]
for rs in RS:
    road_train[rs[1]][1] = road_train[rs[0]][1]

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
result = []
for i in range(1, N + 1):
    if dp[road_train[i][0]][road_train[i][1]] == 0:
        count = 0
        for j in range(1, N + 1):
            if road_train[j] == road_train[i]:
                count += 1
        dp[road_train[i][0]][road_train[i][1]] = count
    result += [str(dp[road_train[i][0]][road_train[i][1]])]

print(' '.join(result))

Submission status: Wrong Answer

Solution code:
N, K, L = [int(_) for _ in input().split()]
PQ = sorted([sorted([int(_) for _ in input().split()]) for _ in range(K)], key = lambda xs: xs[0])
RS = sorted([sorted([int(_) for _ in input().split()]) for _ in range(L)], key = lambda xs: xs[0])

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

for pq in PQ:
    road[pq[1]] = road[pq[0]]
for rs in RS:
    train[rs[1]] = train[rs[0]]

print(' '.join([str(sum([1 if road[i] == road[j] and train[i] == train[j] else 0 for j in range(1, N + 1)])) for i in range(1, N + 1)]))

Submission status: Wrong Answer

Solution code:
import itertools
N, K, L = [int(_) for _ in input().split()]
PQ = [[int(_) for _ in input().split()] for _ in range(K)]
RS = [[int(_) for _ in input().split()] for _ in range(L)]

road = [[1 if i == j else 0 for j in range(N + 1)] for i in range(N + 1)]
road[0][0] = 0
train = [[1 if i == j else 0 for j in range(N + 1)] for i in range(N + 1)]
train[0][0] = 0

for i, j in itertools.product(range(K), range(1, N + 1)):
    if road[PQ[i][0]][j] or road[PQ[i][1]][j]:
        road[PQ[i][0]][j] = 1
        road[PQ[i][1]][j] = 1
        road[j][PQ[i][0]] = 1
        road[j][PQ[i][1]] = 1
        print('road', road)

for i, j in itertools.product(range(L), range(1, N + 1)):
    if train[RS[i][0]][j] or train[RS[i][1]][j]:
        train[RS[i][0]][j] = 1
        train[RS[i][1]][j] = 1
        train[j][RS[i][0]] = 1
        train[j][RS[i][1]] = 1
        print('train', train)

print(' '.join([str(sum([road[i][j] and train[i][j] for j in range(1, N + 1)])) for i in range(1, N + 1)]))

Submission status: Wrong Answer

Solution code:
#unionfind
class UF:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
    def find(self, x, y):
        return self._root(x) == self._root(y)
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    def show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())

n,k,l=map(int,input().split())
pq=[list(map(int,input().split())) for _ in range(k)]
rs=[list(map(int,input().split())) for _ in range(l)]
auf=UF(n)
buf=UF(n)
for p,q in pq:
    auf.union(p-1,q-1)
for r,s in rs:
    buf.union(r-1,s-1)
ta=auf.data()
tb=buf.data()
ar=[0 for i in range(n)]
br=[0 for i in range(n)]
for i in range(len(ta)):
    for t in ta[i]:
        ar[t]=i
for i in range(len(tb)):
    for t in tb[i]:
        br[t]=i
x=[str(ar[i])+'-'+str(br[i]) for i in range(n)]
#Counter
from collections import Counter
c=Counter(x)
z=[str(c[x[i]]) for i in range(n)]
print(" ".join(z))

Submission status: Wrong Answer

Solution code:
#unionfind
class UF:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
    def find(self, x, y):
        return self._root(x) == self._root(y)
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    def show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())

n,k,l=map(int,input().split())
pq=[list(map(int,input().split())) for _ in range(k)]
rs=[list(map(int,input().split())) for _ in range(l)]
auf=UF(n)
buf=UF(n)
for p,q in pq:
    auf.union(p-1,q-1)
for r,s in rs:
    buf.union(r-1,s-1)
ta=auf.data()
tb=buf.data()
ar=[0 for i in range(n)]
br=[0 for i in range(n)]
for i in range(len(ta)):
    for t in ta[i]:
        ar[t]=i
for i in range(len(tb)):
    for t in tb[i]:
        br[t]=i
x=[str(ar[i])+'-'+str(br[i]) for i in range(n)]
res={}
for i in range(n):
    res[x[i]]=0
for i in range(n):
    res[x[i]]+=1
z=[str(res[str(t)]) for t in x]
print(" ".join(z))

Submission status: Wrong Answer

Solution code:
#unionfind
class UF:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
    def find(self, x, y):
        return self._root(x) == self._root(y)
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
    def show(self):
        print(self.table)
    def data(self):
        res={}
        n=len(self.table)
        for i in range(n):
            res.update({i:[i] if self.table[i]<0 else [self.table[i]]})
        for i in range(n):
            res[res[i][0]]+=[i]
        for i in range(n):
            if len(res[i])==1:
                del res[i]
            else:
                del res[i][0]
        return list(res.values())

n,k,l=map(int,input().split())
pq=[list(map(int,input().split())) for _ in range(k)]
rs=[list(map(int,input().split())) for _ in range(l)]
auf=UF(n)
buf=UF(n)
for p,q in pq:
    auf.union(p-1,q-1)
for r,s in rs:
    buf.union(r-1,s-1)
ta=auf.data()
tb=buf.data()
ar=[0 for i in range(n)]
br=[0 for i in range(n)]
for i in range(len(ta)):
    for t in ta[i]:
        ar[t]=i
for i in range(len(tb)):
    for t in tb[i]:
        br[t]=i
x=[str(ar[i])+' '+str(br[i]) for i in range(n)]
res={}
for i in range(n):
    res[x[i]]=0
for i in range(n):
    res[x[i]]+=1
z=[str(res[str(t)]) for t in x]
print(" ".join(z))