Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from functools import reduce

result = 0

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

n = int(input())
A = list(map(int, input().split()))
X = [0 for i in range n]
Y = [0 for i in range n]
for i in range(1, N):
    X[i] = gcd(X[i-1], A[i-1])
for i in range(n-1)[::-1]:
    Y[i] = gcd(Y[i+1], A[i+1])
print(max(gcd(X[i], Y[i]) for i in range(n)))


Fixed submission:
from functools import reduce

result = 0

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

n = int(input())
A = list(map(int, input().split()))
X = [0 for i in range(n)]
Y = [0 for i in range(n)]
for i in range(1, n):
    X[i] = gcd(X[i-1], A[i-1])
for i in range(n-1)[::-1]:
    Y[i] = gcd(Y[i+1], A[i+1])
print(max(gcd(X[i], Y[i]) for i in range(n)))

Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

result = 0

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    result = max(result, reduce(gcd, A[:i]+A[i+1:]))

print(result)

Fixed submission:
from functools import reduce

result = 0

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

n = int(input())
A = list(map(int, input().split()))
X = [0 for i in range(n)]
Y = [0 for i in range(n)]
for i in range(1, n):
    X[i] = gcd(X[i-1], A[i-1])
for i in range(n-1)[::-1]:
    Y[i] = gcd(Y[i+1], A[i+1])
print(max(gcd(X[i], Y[i]) for i in range(n)))

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce
import fraction

result = 0

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    result = max(result, reduce(fraction.gcd, A[:i]+A[i+1:]))

print(result)

Fixed submission:
from functools import reduce

result = 0

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

n = int(input())
A = list(map(int, input().split()))
X = [0 for i in range(n)]
Y = [0 for i in range(n)]
for i in range(1, n):
    X[i] = gcd(X[i-1], A[i-1])
for i in range(n-1)[::-1]:
    Y[i] = gcd(Y[i+1], A[i+1])
print(max(gcd(X[i], Y[i]) for i in range(n)))

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

result = 0

n = int(input())
A = list(map(int, input().split()))
for i in range(n):
    result = max(result, reduce(math.gcd, A[:i]+A[i+1:]))

print(result)

Fixed submission:
from functools import reduce

result = 0

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

n = int(input())
A = list(map(int, input().split()))
X = [0 for i in range(n)]
Y = [0 for i in range(n)]
for i in range(1, n):
    X[i] = gcd(X[i-1], A[i-1])
for i in range(n-1)[::-1]:
    Y[i] = gcd(Y[i+1], A[i+1])
print(max(gcd(X[i], Y[i]) for i in range(n)))
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
k=input()

correct = s[k-1]
ans =""
for i in s:
    if i != correct:
        ans += "*"
    else:
        ans+= i

print(ans)


Fixed submission:
n=int(input())
s=input()
k=int(input())

correct = s[k-1]
ans =""
for i in s:
    if i != correct:
        ans += "*"
    else:
        ans+= i

print(ans)
Buggy python submission (verdict: Runtime Error):
A = input()
_ = input()
_ = input()
_ = input()
E = input()
k = input()

if (E-A) > k:
  print(":(")
else:
  print("Yay!")

Fixed submission:
A = int(input())
_ = input()
_ = input()
_ = input()
E = int(input())
k = int(input())

if (E-A) > k:
    print(":(")
else:
    print("Yay!")
Buggy python submission (verdict: Runtime Error):
li = [int(input()) for _ in range(5)]

time = 0
non10li = []
for i in li:
    if i%10==0:
        time+=i
    else:
        non10li.append(i)

minili = [i%10 for i in non10li]
ind = non10li.pop(minili.index(min(minili)))
for i in non10li:
    time+=(i//10)*10+10

time+=ind
print(time)


Fixed submission:
li = [int(input()) for _ in range(5)]

time = 0
non10li = []
for i in li:
    if i%10==0:
        time+=i
    else:
        non10li.append(i)
if len(non10li)!=0:
    minili = [i%10 for i in non10li]
    ind = non10li.pop(minili.index(min(minili)))
    for i in non10li:
        time+=(i//10)*10+10

    time+=ind
print(time)
Buggy python submission (verdict: Runtime Error):
N = int(input())

num=0

for s in input():
    if s=="R":
        num+=1
    else:
        num-=1

if num>0:
    print("Yes")
else:
    print("No")


Fixed submission:
A, B, C = map(int, input().split())

if A == B and B == C:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
A = list(map(int, input().split()))

print(gcd_list(A))


Fixed submission:
import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = list(map(int, input().split()))

print(gcd_list(A))

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

def gcd(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
A = list(map(int, input().split()))

print(gcd(A))


Fixed submission:
import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = list(map(int, input().split()))

print(gcd_list(A))

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

def gcd(numbers):
    return reduce(math.gcd, numbers)

N = int(input())
A = list(map(int, input().split()))

print(gcd(A))


Fixed submission:
import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = list(map(int, input().split()))

print(gcd_list(A))
Buggy python submission (verdict: Runtime Error):
N = int(input())
h = list(map(int, input().split()))

dp = [0] * (N+2)

for i in range(N):
    dp[i+1] = min(dp[i+1], dp[i]+abs(h[i]-h[i+1]))
    dp[i+2] = min(dp[i+2], dp[i]+abs(h[i]-h[i+2]))

print(dp[N-1])


Fixed submission:
inf = 10**9 + 7
n = int(input())
nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0


for i in range(1, n):
    dp[i] = min(dp[i], dp[i-1]+abs(nodes[i]-nodes[i-1]))
    if i > 1:
        dp[i] = min(dp[i], dp[i-2]+abs(nodes[i]-nodes[i-2]))

print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))
inf = 10**9 + 7

dp = [inf] * n
dp[0] = 0

for i in range(n):
    for j in range(1, min(k+1, n-i)):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[n-1])


Fixed submission:
inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

for i in range(n):
    for j in range(i+1, min(i+k+1, n)):
        dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
# for i in range(n):
#     for j in range(1, min(k+1, n-i)):
#         dp[i+j] = min(dp[i+j], dp[i]+abs(nodes[i]-nodes[i+j]))
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

# for i in range(n):
#     for j in range(i+1, min(i+k+1, n)):
#         dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
for i in range(n):
    for j in range(1, min(k+1, n-i)):
        dp[i+j] = min(dp[i+j], dp[i]+abs(nodes[i]-nodes[i+j]))
print(dp[n-1])


Fixed submission:
inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

for i in range(n):
    for j in range(i+1, min(i+k+1, n)):
        dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
# for i in range(n):
#     for j in range(1, min(k+1, n-i)):
#         dp[i+j] = min(dp[i+j], dp[i]+abs(nodes[i]-nodes[i+j]))
print(dp[n-1])

Buggy python submission (verdict: Runtime Error):
inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

# for i in range(n):
#     for j in range(i+1, min(i+k+1, n)):
#         dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
for i in range(n):
    for j in range(k):
        dp[i+j] = min(dp[i+j], dp[i]+abs(nodes[i]-nodes[i+j]))
print(dp[n-1])


Fixed submission:
inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

for i in range(n):
    for j in range(i+1, min(i+k+1, n)):
        dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
# for i in range(n):
#     for j in range(1, min(k+1, n-i)):
#         dp[i+j] = min(dp[i+j], dp[i]+abs(nodes[i]-nodes[i+j]))
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

for i in range(n):
    for j in range(i+1, min(i+k+1, n)):
        dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
print(dp[n-1])


Fixed submission:
inf = 10**9 + 7
n, k = map(int, input().split())

nodes = list(map(int, input().split()))
dp = [inf] * n

dp[0] = 0

for i in range(n):
    for j in range(i+1, min(i+k+1, n)):
        dp[j] = min(dp[j], dp[i] + abs(nodes[i] - nodes[j]))
# for i in range(n):
#     for j in range(1, min(k+1, n-i)):
#         dp[i+j] = min(dp[i+j], dp[i]+abs(nodes[i]-nodes[i+j]))
print(dp[n-1])
Buggy python submission (verdict: Runtime Error):
import numpy as np

n, W = map(int, input().split())
w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())
ndp = np.zeros(W + 1, dtype=np.int64)

for w, v in zip(w, v):
    # [:w]は品物の重量がナップサックの空きよりも重いので更新しない。
    # ndp[w:] は通常DPでのdp[i][w]=dp[i-1][w]。そのままでの更新。
    # ndp[:-w] + v は[:-w]が[w-weight]に相当。
    np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])

print(ndp[-1])


Fixed submission:
N, W = map(int, input().split())
V = 10 ** 5
inf = 10 ** 18
dp = [inf] * (V + 1)
dp[0] = 0

for n in range(1, N+1):
    w, v = map(int, input().split())
    for i in range(v, V+1)[::-1]:
        if dp[i-v]+w <= W:
            dp[i] = min(dp[i], dp[i-v]+w)

for i in range(V+1)[::-1]:
    if dp[i] < inf:
        print(i)
        break
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+1)
from functools import lru_cache

def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        G[x].append(y)

    @lru_cache(maxsize=10**5+1)
    def dp(v):
        res = 0
        for w in G[v]:
            res = max(res, dp(w)+1)
        return res

    ans = 0
    for i in range(N):
        ans = max(ans, dp(i))
    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
import sys
sys.setrecursionlimit(10**5+1)

N, M = map(int, input().split())
graph = {i+1:[] for i in range(N)}

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)

"""
dp[v]: ノードv(1~N)を始点とした最大長
"""
dp = [0] * (1+N)

def max_length_from(v):
    if dp[v] != 0:
        return dp[v]
    max_length = 0
    for vv in graph[v]:
        tmp = max_length_from(vv) + 1
        if tmp > max_length:
            max_length = tmp
    dp[v] = max_length
    return max_length

for v in range(1, N+1):
    max_length_from(v)

print(max(dp))

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
graph = {i+1:[] for i in range(N)}

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)

"""
dp[v]: ノードv(1~N)を始点とした時の、最大長
"""
dp = [0] * (1+N)

def max_length_from(v):
    if dp[v] != 0:
        return dp[v]
    max_length = 0
    for vv in graph[v]:
        tmp = max_length_from(vv) + 1
        if tmp > max_length:
            max_length = tmp
    dp[v] = max_length
    return max_length

for v in range(1, N+1):
    max_length_from(v)

print(max(dp))


Fixed submission:
import sys
sys.setrecursionlimit(10**5+1)

N, M = map(int, input().split())
graph = {i+1:[] for i in range(N)}

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)

"""
dp[v]: ノードv(1~N)を始点とした最大長
"""
dp = [0] * (1+N)

def max_length_from(v):
    if dp[v] != 0:
        return dp[v]
    max_length = 0
    for vv in graph[v]:
        tmp = max_length_from(vv) + 1
        if tmp > max_length:
            max_length = tmp
    dp[v] = max_length
    return max_length

for v in range(1, N+1):
    max_length_from(v)

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
a = counter[1]
b = counter[2]
c = counter[3]
"""
dp[i][j][k]: 残り１貫の皿がi, ２貫j, ３貫kの状態から全部食べ切るまでの期待値
"""
dp = [[[-1] * (310) for _ in range(310)] for _ in range(310)]

def rec(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    res = 0
    if i > 0:
        res += rec(i-1,j,k) * i
    if j > 0:
        res += rec(i+1,j-1,k) * j
    if k > 0:
        res += rec(i,j+1,k-1) * k
    res += N
    res *= 1 / (i + j + k)
    dp[i][j][k] = res
    return res

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            rec(i, j, k)
print(dp[a][b][c])


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
a = A.count(1)
b = A.count(2)
c = A.count(3)
"""
dp[i][j][k]: 残り１貫の皿がi, ２貫j, ３貫kの状態から全部食べ切るまでの期待値
"""
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

# 先にiについて更新することで、dp[i""+1""][j-1][k]を可能にしている。
# 先にjについて更新することで、dp[i][j""+1""][k-1]を可能にしている。
for k in range(c + 1):
    for j in range(b + c + 1 - k): # ２貫の皿の数の最大値 - 3枚の皿の数
        for i in range(a + b + c + 1 - k - j):
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = N * 1.0
            if i > 0:
                tmp += i * dp[i-1][j][k]
            if j > 0:
                tmp += j * dp[i+1][j-1][k]
            if k > 0:
                tmp += k * dp[i][j+1][k-1]
            dp[i][j][k] = tmp / (i + j + k)
print(dp[i][j][k])
Buggy python submission (verdict: Runtime Error):
ans = 0
for i in range(1, N+1, 2):
    count = 0
    for j in range(1, i//2+1):
        if i % j == 0:
            count += 1
    if count == 7:
        ans += 1
print(ans)


Fixed submission:
N = int(input())
ans = 0
for i in range(1, N+1, 2):
    count = 0
    for j in range(1, i//2+1):
        if i % j == 0:
            count += 1
    if count == 7:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()
len_t = len(T)


def t_index_is_valid(t_index, start, end):
    if S[t_index+start:t_index+end]:
        for j, t_ in enumerate(T):
            if S[t_index+start+j] == "?" or S[t_index+start+j] == t_:
                pass
            else:
                return False
        return True
    else:
        return False


ok = False
replace_index = (0, 0)
for i, t in enumerate(T):
    if ok:
        break
    if t in S:
        t_indexes = [n for n, v in enumerate(S) if v == t]
        t_indexes.reverse()
        start = - i
        end = len_t - i + 1
        for t_index in t_indexes:
            if t_index_is_valid(t_index, start, end):
                replace_index = (t_index+start, t_index+end)
                ok = True
                break

if not ok:
    print("UNRESTORABLE")
else:
    S = list(S)
    for j, i in enumerate(range(replace_index[0], replace_index[1]-1)):
        S[i] = T[j]
    for i in range(len(S)):
        if S[i] == "?":
            S[i] = "a"
    print("".join(S))


Fixed submission:
S = list(input())
T = input()
len_t = len(T)


def is_valid(start, end):
    for t_i, s_i in enumerate(range(start, end)):
        if S[s_i] == "?" or S[s_i] == T[t_i]:
            continue
        else:
            return False
    return True


def assign(start, end):
    for t_i, s_i in enumerate(range(start, end)):
        S[s_i] = T[t_i]
    for i in range(len(S)):
        if S[i] == "?":
            S[i] = "a"


ok = False
for i in range(len_t-1, len(S))[::-1]:
    if S[i] == "?" or S[i] == T[-1]:
        start = i - len_t + 1
        end = i + 1
        if is_valid(start, end):
            ok = True
            assign(start, end)
            break

if ok:
    print("".join(S))
else:
    print("UNRESTORABLE")
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
N, K = map(int, input().split())
dots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

dot_comb = combinations(dots, K)

ans = 10 ** 37
for dots in dot_comb:
    x_min = 10 ** 9 + 1
    x_max = (-1) * (10 ** 9 + 1)
    y_min = 10 ** 9 + 1
    y_max = (-1) * (10 ** 9 + 1)
    for dot in dots:
        x, y = dot
        x_min = min(x_min, x)
        x_max = max(x_max, x)
        y_min = min(y_min, y)
        y_max = max(y_max, y)
    ans = min(ans, (x_max-x_min)*(y_max-y_min))
print(ans)


Fixed submission:
from itertools import combinations
N, K = map(int, input().split())
dots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

ans = 10 ** 37
for i in range(N):
    for j in range(i+K-1, N):
        width = dots[j][0] - dots[i][0]
        y = sorted([l for _, l in dots[i:j+1]])
        for a, b in zip(y, y[K-1:]):
            height = b - a
            ans = min(ans, width*height)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
N, K = map(int, input().split())
dots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

dot_comb = combinations(dots, K)

ans = 10 ** 37
for dots in dot_comb:
    x_min = 10 ** 9 + 1
    x_max = (-1) * (10 ** 9 + 1)
    y_min = 10 ** 9 + 1
    y_max = (-1) * (10 ** 9 + 1)
    for dot in dots:
        x, y = dot
        x_min = min(x_min, x)
        x_max = max(x_max, x)
        y_min = min(y_min, y)
        y_max = max(y_max, y)
    ans = min(ans, (x_max-x_min)*(y_max-y_min))
print(ans)


Fixed submission:
from itertools import combinations
N, K = map(int, input().split())
dots = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])

ans = 10 ** 37
for i in range(N):
    for j in range(i+K-1, N):
        width = dots[j][0] - dots[i][0]
        y = sorted([l for _, l in dots[i:j+1]])
        for a, b in zip(y, y[K-1:]):
            height = b - a
            ans = min(ans, width*height)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 0
flag = True
while flag:
    flag = False
    for i in range(N):
        if A[i] >= N:
            count = A[i] // N
            ans += count
            for j in range(N):
                A[j] += count
            A[i] -= count
            A[i] %= N
            flag = True
            break

print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
ans = 0
flag = True
while flag:
    flag = False
    for i in range(N):
        if A[i] >= N:
            count = A[i] // N
            ans += count
            for j in range(N):
                A[j] += count
            A[i] -= count
            A[i] %= N
            flag = True

print(ans)
Buggy python submission (verdict: Runtime Error):
    def main():
        import sys
        input = sys.stdin.readline
        a, b = map(int, input().split())
        if a % 3 == 0 or b % 3 == 0:
            print(0)
            sys.exit()
        if a > b:
            a, b = b, a

        x = (b // 3) * a
        bb = b - b//3
        aa = a
        if aa % 2 == 0 or bb % 2 == 0:
            y = (bb * aa) // 2
            li = sorted([x,y,y])
        else:
            if aa > bb:
                aa, bb = bb, aa
            y = aa * (bb//2)
            z = aa * ((bb+1)//2)
            li = sorted([x, y, z])
        ans = li[2] - li[0]

        x = (b // 3 + 1) * a
        bb = b - b//3 - 1
        aa = a
        if aa % 2 == 0 or bb % 2 == 0:
            y = (aa*bb)//2
            li = sorted([x,y,y])
        else:
            if aa > bb:
                aa, bb = bb, aa
            y = aa * (bb//2)
            y = aa * (bb//2)
            z = aa * ((bb+1)//2)
            li = sorted([x, y, z])
        ans = min(ans, li[2] - li[0])
        print(ans)


    if __name__ == '__main__':
        main()

Fixed submission:
def calc(W, H):
    ans = float("inf")
    for w in range(1, W//2+1):
        x = w * H
        w_ = W - w
        if w_ % 2 == 0 or H % 2 == 0:
            y = (w_*H)//2
            li = sorted([x, y, y])
        else:
            if w_ < H:
                a, b = w_, H
            else:
                a, b = H, w_
            y = a * (b//2)
            z = a * (b-b//2)
            li = sorted([x,y,z])
        ans = min(ans, li[2] - li[0])
    return ans



def main():
    import sys
    input = sys.stdin.readline
    w, h = map(int, input().split())
    ans = calc(w,h)
    ans = min(calc(h,w), ans)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
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, y):
        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()}


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

road = UnionFind(N+1)
railway = UnionFind(N+1)

for _ in range(K):
    p, q = map(int, input().split())
    road.union(p, q)

for _ in range(L):
    p, q = map(int, input().split())
    railway.union(p, q)

ans = []
for i in range(1, N+1):
    ans.append(len(set(road.members(i)) & set(railway.members(i))))
print(" ".join(map(str, ans)))


Fixed submission:
from collections import defaultdict

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

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

road = UnionFind(N)
railway = UnionFind(N)

for _ in range(K):
    p, q = map(int, input().split())
    road.union(p-1, q-1)

for _ in range(L):
    p, q = map(int, input().split())
    railway.union(p-1, q-1)

counter = defaultdict(int)
for i in range(N):
    counter[(road.find(i), railway.find(i))] += 1
ans = []
for i in range(N):
    ans.append(counter[(road.find(i), railway.find(i))])

print(*ans)