Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
c = [set([]) for _ in range(N + 1)]
g = [[0] * (N + 1) for _ in range(N + 1)]
paths = []
for _ in range(N-1):
    a, b = map(int, input().split())
    paths.append((a, b))

cmax = 1

for a, b in paths:
    cnt = 1
    while True:
        if cnt not in c[a] and cnt not in c[b]:
            c[a].add(cnt)
            c[b].add(cnt)
            g[a][b] = cnt
            cmax = max(cmax, cnt)
            break
        cnt += 1

print(cmax)
for a, b in paths:
    print(g[a][b])


Fixed submission:
from collections import deque

N = int(input())
g = [[] for _ in range(N)]
vp = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    vp.append((a, b))

k = 0
d = dict()
cs = [0] * N
used = [False] * N

que = deque([])
used[0] = 1
que.appendleft(0)
while len(que) > 0:
    v = que.pop()
    k = max(k, len(g[v]))
    cur = 1
    for u in g[v]:
        if used[u]:
            continue
        if cur == cs[v]:
            cur += 1
        cs[u] = d[(u, v)] = d[(v, u)] = cur
        cur += 1
        used[u] = True
        que.appendleft(u)
print(k)
for p in vp:
    print(d[p])

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
c = [[] for _ in range(N + 1)]
g = [[0] * (N + 1) for _ in range(N + 1)]
paths = []
for _ in range(N-1):
    a, b = map(int, input().split())
    paths.append((a, b))

for a, b in paths:
    cnt = 1
    while True:
        if cnt not in c[a] and cnt not in c[b]:
            c[a].append(cnt)
            c[b].append(cnt)
            g[a][b] = cnt
            break
        cnt += 1

print(max([max(x) for x in g]))
for a, b in paths:
    print(g[a][b])


Fixed submission:
from collections import deque

N = int(input())
g = [[] for _ in range(N)]
vp = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    vp.append((a, b))

k = 0
d = dict()
cs = [0] * N
used = [False] * N

que = deque([])
used[0] = 1
que.appendleft(0)
while len(que) > 0:
    v = que.pop()
    k = max(k, len(g[v]))
    cur = 1
    for u in g[v]:
        if used[u]:
            continue
        if cur == cs[v]:
            cur += 1
        cs[u] = d[(u, v)] = d[(v, u)] = cur
        cur += 1
        used[u] = True
        que.appendleft(u)
print(k)
for p in vp:
    print(d[p])
Buggy python submission (verdict: Runtime Error):
H, W, K = map(int, input().split())
c = []
cnt = [0] * W
num = 0
A = [[0] * W for _ in range(H)]

for i in range(H):
    row = list(input())
    c.append(row)
    cnt[i] = row.count("#")


def solve(cl, cr):
    global num
    P = []
    for i in range(cl, cr + 1):
        for j in range(W):
            if c[i][j] == "#":
                P.append(j)
    P = sorted(P)
    for i in range(len(P)):
        v1 = 0
        v2 = W - 1
        if (i >= 1):
            v1 = P[i - 1] + 1
        if (i < len(P) - 1):
            v2 = P[i]
        num += 1
        for j in range(cl, cr + 1):
            for k in range(v1, v2 + 1):
                A[j][k] = num


vec = []
for i in range(H):
    if cnt[i] >= 1:
        vec.append(i)
for i in range(len(vec)):
    v1 = 0
    v2 = H - 1
    if (i >= 1):
        v1 = vec[i - 1] + 1
    if (i < len(vec) - 1):
        v2 = vec[i]
    solve(v1, v2)
for i in range(H):
    print(*A[i])


Fixed submission:
H, W, K = map(int, input().split())
c = []
cnt = [0] * H
num = 0
A = [[0] * W for _ in range(H)]

for i in range(H):
    row = list(input())
    c.append(row)
    cnt[i] = row.count("#")


def solve(cl, cr):
    global num
    P = []
    for i in range(cl, cr + 1):
        for j in range(W):
            if c[i][j] == "#":
                P.append(j)
    P = sorted(P)
    for i in range(len(P)):
        v1 = 0
        v2 = W - 1
        if (i >= 1):
            v1 = P[i - 1] + 1
        if (i < len(P) - 1):
            v2 = P[i]
        num += 1
        for j in range(cl, cr + 1):
            for k in range(v1, v2 + 1):
                A[j][k] = num


vec = []
for i in range(H):
    if cnt[i] >= 1:
        vec.append(i)
for i in range(len(vec)):
    v1 = 0
    v2 = H - 1
    if (i >= 1):
        v1 = vec[i - 1] + 1
    if (i < len(vec) - 1):
        v2 = vec[i]
    solve(v1, v2)
for i in range(H):
    print(*A[i])
Buggy python submission (verdict: Runtime Error):
n = int(input())
B = list(map(int, input().split()))
ans = 0
ans += B[0]
for i in range(n - 2):
    if B[i] > B[i + 1]:
        ans += B[i + i]
    else:
        ans += B[i]
ans += B[-1]
print(ans)


Fixed submission:
n = int(input())
B = list(map(int, input().split()))
ans = 0
ans += B[0]
for i in range(n - 2):
    if B[i] > B[i + 1]:
        ans += B[i + 1]
    else:
        ans += B[i]
ans += B[-1]
print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
B = list(map(int, input().split()))
A = [0] * (n)
A[0] = B[0]
for i in range(n - 2):
    if B[i] > B[i + 1]:
        A[i + 1] = B[i + i]
    else:
        A[i + 1] = B[i]
A[-1] = B[-1]
print(sum(A))


Fixed submission:
n = int(input())
B = list(map(int, input().split()))
ans = 0
ans += B[0]
for i in range(n - 2):
    if B[i] > B[i + 1]:
        ans += B[i + 1]
    else:
        ans += B[i]
ans += B[-1]
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
T = input()
ans = 0
for i in range(3):
  is S[i] == T[i]:
    ans += 1
print(ans)

Fixed submission:
S = input()
T = input()
ans = 0
for i in range(3):
  if S[i] == T[i]:
    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())
ans = 0
for r in range(N + 1):
    for g in range(N + 1):
        v = N - r * R - g * G
        if v >= 0 and v % B == 0:
            ans += 1
print(ans)

Fixed submission:
def solve():
    R, G, B, N = map(int, input().split())
    ans = 0
    for r in range(N + 1):
        for g in range(N + 1):
            v = N - r * R - g * G
            if v >= 0 and v % B == 0:
                ans += 1
    print(ans)

solve()

Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())
ans = 0
for r in range(3001):
    for g in range(3001):
        if N - r * R - g * G >= 0 and (N - r * R - g * G) % B == 0:
            ans += 1
print(ans)

Fixed submission:
def solve():
    R, G, B, N = map(int, input().split())
    ans = 0
    for r in range(N + 1):
        for g in range(N + 1):
            v = N - r * R - g * G
            if v >= 0 and v % B == 0:
                ans += 1
    print(ans)

solve()
Buggy python submission (verdict: Runtime Error):
b = input()
if b == "A":
  print("T")
elif b == "G":
  print("C")
elif b == "C":
  print("G")
else b == "T":
  print("A")
  

Fixed submission:
b = input()
if b == "A":
  print("T")
elif b == "G":
  print("C")
elif b == "C":
  print("G")
else:
  print("A")
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
for _ in range(q):
    l, r = map(int, input().split())
    ss = s[(l - 1):r]
    a = 0
    for i in range(len(ss) - 1):
        if ss[i:(i+2)] == "AC":
            a += 1
    print(a)

Fixed submission:
n, q = map(int, input().split())
s = input()
ss = [0] * n
for i in range(n - 1):
    if s[i:(i+2)] == "AC":
        ss[i] = 1
sss = [0] * n
for i in range(n - 1):
    sss[i + 1] = sss[i] + ss[i]
for _ in range(q):
    l, r  = map(int, input().split())
    print(sss[r - 1] - sss[l - 1])
Buggy python submission (verdict: Runtime Error):
a, b, c = sorted(map(int(), input().split(" ")))
print(c * 10 + a + b)

Fixed submission:
a, b, c = sorted(map(int, input().split(" ")))
print(c * 10 + a + b)
Buggy python submission (verdict: Runtime Error):
a = map(int, input().split())
print(max(a) - min(a))

Fixed submission:
(*a,)= map(int, input().split(" "))
print(max(a) - min(a))
Buggy python submission (verdict: Runtime Error):
a, b, k = map(int, input().split())
l = list(range(a, b + 1))
a = sorted(set(l[:k] + l[(b - a + 1 - k):]))
print(*a, sep="\n")

Fixed submission:
a, b, k = map(int, input().split())
l = range(a, b + 1)
a = sorted(set(l[:k]) | set(l[-k:]))
print(*a, sep="\n")
Buggy python submission (verdict: Runtime Error):
import math
a, b = map(int, iniput().split(" "))
print(math.ceil((a + b) / 2))

Fixed submission:
import math
a, b = map(int, input().split(" "))
print(math.ceil((a + b) / 2))
Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, input().split())

print(sum(a, b, c) - max(a, b, c))

Fixed submission:
a, b, c = map(int, input().split())

print(min(a + b, b + c, c + a))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [int(input()) for _ in range(n)]
print(sorted(set(a))[-2])

Fixed submission:
n = int(input())
a = sorted(map(int, input().split()))
print(a[-1] - a[0])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

dp = [0] * (N + 1)
for i in range(1, N + 1):
    cursor = i
    while cursor <= N:
        dp[cursor] += 1
        cursor += i

ans = 0
for i in range(1, N + 1):
    ans += i * dp[i]

print(ans)


Fixed submission:
N = int(input())

ans = 0
for i in range(1, N + 1):
    start = i
    n = N // i
    end = i * n
    ans += n * (start + end) // 2


print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))

ans = [0] * N
bit = 0
for i in range(1, N):
    ans[i] = a[i - 1] ^ a[i] ^ ans[i - 1]
    bit ^= ans[i]

if bit == a[0]:
    print(' '.join(map(str, ans)))
else:
    index = 0
    for i in range(1, 10 ** 9 + 1):
        bit = bit ^ (i - 1) ^ i
        if bit == a[0]:
            index = i
            break

    ans[0] = index
    for i in range(1, N):
        ans[i] = a[i - 1] ^ a[i] ^ ans[i - 1]
        bit ^= ans[i]

    print(' '.join(map(str, ans)))


Fixed submission:
N = int(input())
a = list(map(int, input().split()))
S = 0
for i in range(N):
    S ^= a[i]

ans = [0] * N

for i in range(N):
    ans[i] = S ^ a[i]

print(' '.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))

ans = [0] * N

for i in range(10 ** 9 + 1):
    ans[0] = i
    bit = 0
    for i in range(1, N):
        ans[i] = a[i - 1] ^ a[i] ^ ans[i - 1]
        bit ^= ans[i]
    if bit == a[0]:
        break

print(' '.join(map(str, ans)))


Fixed submission:
N = int(input())
a = list(map(int, input().split()))
S = 0
for i in range(N):
    S ^= a[i]

ans = [0] * N

for i in range(N):
    ans[i] = S ^ a[i]

print(' '.join(map(str, ans)))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans *= a

if ans > (10 ** 18):
    print(-1)
else:
    print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
ans = 1
dekai = False
for a in A:
    ans *= a
    if ans > (10 ** 18):
        dekai = True
        break

if 0 in A:
    print(0)
elif dekai:
    print(-1)
else:
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
ans = 1
for a in A:
    ans *= a

if ans > (10 ** 18):
    print(-1)
else:
    print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
ans = 1
dekai = False
for a in A:
    ans *= a
    if ans > (10 ** 18):
        dekai = True
        break

if 0 in A:
    print(0)
elif dekai:
    print(-1)
else:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
edges = [[] for i in range(N)]
ans = [[0 for i in range(N + 1)] for i in range(N + 1)]
lines = []

for i in range(N - 1):
    a, b = map(int, input().split())
    lines.append((a, b,))
    edges[a - 1].append(b - 1)

q = [(0, 0,)]
max_color = 0
while q:
    v, color = q.pop()
    c = 0
    for nv in edges[v]:
        c += 1
        if c == color:
            c += 1
        q.append((nv, c,))
        ans[v + 1][nv + 1] = c
        max_color = max(max_color, c)

print(max_color)
for i in range(N - 1):
    a, b = lines[i]
    print(ans[a][b])


Fixed submission:
N = int(input())
edges = [[] for i in range(N)]
ans = [-1] * (N - 1)
lines = []

for i in range(N - 1):
    a, b = map(int, input().split())
    lines.append((a, b))
    edges[a - 1].append((b - 1, i,))

q = [(0, 0,)]
max_color = 0
while q:
    v, c = q.pop()
    color = 1
    if c == color:
        color += 1
    for nv, i in edges[v]:
        ans[i] = color
        q.append((nv, color,))
        color += 1
        if c == color:
            color += 1

print(max(ans))
for i in range(N - 1):
    a, b = lines[i]
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = []
for i in range(N):
    S.append(input())

dicts = [{} for _ in range(N)]
for i in range(N):
    for j in range(10):
        c = S[i][j]
        dicts[i][c] = dicts[i].get(c, 0) + 1

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if dicts[i] == dicts[j]:
            ans += 1

print(ans)


Fixed submission:
N = int(input())
S = []
for i in range(N):
    S.append(input())
history = {}
ans = 0

for i in range(N):
    sorted_s = ''.join(sorted(S[i]))
    num = history.get(sorted_s, 0)
    ans += num
    history[sorted_s] = num + 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
MOD = 10 ** 9 + 7
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    for j in range(0, 10):
        if (S[i] != '?' and S[i] != str(j)):
            continue
        for k in range(0, 13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]

    for j in range(0, 13):
        dp[i + 1][j] %= MOD

print(dp[N][5])


Fixed submission:
S = input()
MOD = 10 ** 9 + 7
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    for j in range(0, 10):
        if (S[i] != '?' and S[i] != str(j)):
            continue
        for k in range(0, 13):
            dp[i + 1][(k * 10 + j) % 13] += dp[i][k]

    for j in range(0, 13):
        dp[i + 1][j] %= MOD

print(dp[N][5])
Buggy python submission (verdict: Runtime Error):
import bisect

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

ans = [A[0]]
for i in range(1, N):
    index = bisect.bisect_left(ans, A[i])
    if index > 0:
        ans[index - 1] = A[i]
    else:
        ans = [A[i]] + ans

print(len(ans))


Fixed submission:
r = int(input())
print(3 * r ** 2)
Buggy python submission (verdict: Runtime Error):
N = int(input())
d = list(map(int, input().split()))
d.sort()

abc = 0
arc = N

ans = 0
for k in range(1, 10 ** 5):
    while True:
        if d[abc] < k:
            abc += 1
            arc -= 1
        else:
            break
    if abc == arc:
        ans += 1
    elif abc > arc:
        break

print(ans)


Fixed submission:
N = int(input())
d = list(map(int, input().split()))
d.sort()

abc = 0
arc = N

ans = 0
for k in range(1, 10 ** 5 + 1):
    while True:
        if abc >= N:
            break
        elif d[abc] < k:
            abc += 1
            arc -= 1
        else:
            break
    if abc == arc:
        ans += 1
    elif abc > arc:
        break

print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())

max_num = (N - 1) * (N - 2) // 2

for i in range(2, N + 1):
    print(1, i)

add = max_num - K

edges = []
for i in range(2, N):
    for j in range(i + 1, N + 1):
        edges.append(i, j)

for i in range(add):
    print(edges[i])


Fixed submission:
N, K = map(int, input().split())

max_num = (N - 1) * (N - 2) // 2

if K > max_num:
    print(-1)
else:
    edges = []
    for i in range(2, N + 1):
        edges.append((1, i,))

    add = max_num - K

    candidates = []
    for i in range(2, N):
        for j in range(i + 1, N + 1):
            candidates.append((i, j,))

    for i in range(add):
        edges.append(candidates[i])

    print(len(edges))
    for edge in edges:
        print(' '.join(map(str, edge)))

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())

max_num = (N - 1) * (N - 2) // 2

for i in range(2, N + 1):
    print(1, i)

add = max_num - K

edges = []
for i in range(2, N):
    for j in range(i + 1, N + 1):
        edges.append(i, j)

for i in range(add):
    print(edges[i])


Fixed submission:
N, K = map(int, input().split())

max_num = (N - 1) * (N - 2) // 2

if K > max_num:
    print(-1)
else:
    edges = []
    for i in range(2, N + 1):
        edges.append((1, i,))

    add = max_num - K

    candidates = []
    for i in range(2, N):
        for j in range(i + 1, N + 1):
            candidates.append((i, j,))

    for i in range(add):
        edges.append(candidates[i])

    print(len(edges))
    for edge in edges:
        print(' '.join(map(str, edge)))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n, a, b, c, d = map(int, input().split())
s = input()
grid = []
for rock in s:
    grid.append(rock == '#')

if grid[c-1] or grid[d-1]:
    print('No')

max_none_count = 0
max_rock_count = 0
none_count = 0
rock_count = 0
if c < d:
    for i in range(a-1, d):
        if grid[i]:
            none_count = 0
            rock_count += 1
        else:
            rock_count = 0

        max_none_count = max(max_none_count, none_count)
        max_rock_count = max(max_rock_count, rock_count)

    if max_rock_count >= 2:
        print('No')
    else:
        print('Yes')
elif c > d:
    max_rock_count = 0
    rock_count = 0
    # Dの位置は岩として考える
    grid[d-1] = True
    canSkip = False
    for i in range(a-1, c):
        if grid[i]:
            rock_count += 1
        else:
            if b - 1 <= i and c - 2 <= i and not grid[i-1] and not grid[i] and not grid[i+1]:
                canSkip = True
            rock_count = 0

        max_rock_count = max(max_rock_count, rock_count)

    if max_rock_count <= 1 and canSkip:
        print('Yes')
    else:
        print('No')


Fixed submission:
# -*- coding: utf-8 -*-
n, a, b, c, d = map(int, input().split())
s = input()
grid = []
for rock in s:
    grid.append(rock == '#')

if grid[c-1] or grid[d-1]:
    print('No')

max_rock_count = 0
rock_count = 0
if c < d:
    for i in range(a-1, d):
        if grid[i]:
            rock_count += 1
        else:
            rock_count = 0

        max_rock_count = max(max_rock_count, rock_count)

    if max_rock_count >= 2:
        print('No')
    else:
        print('Yes')
elif c > d:
    max_rock_count = 0
    rock_count = 0
    canSkip = False
    for i in range(a-1, c):
        if grid[i]:
            rock_count += 1
        else:
            if b - 1 <= i and i <= c - 2 and not grid[i-1] and not grid[i] and not grid[i+1]:
                if i-1 != d - 1:
                    canSkip = True
            rock_count = 0

        max_rock_count = max(max_rock_count, rock_count)

    if max_rock_count <= 1 and canSkip:
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
qS = input()


def replace(s, count):
    fi = s.find('ABC')
    if fi >= 0:
        newS = 'A' + s[fi+3:]
        return replace(newS, count + 1)
    else:
        return count


print(replace(qS, 0))


Fixed submission:
# -*- coding: utf-8 -*-
s = input()

a_num = 0
bc_num = 0
ans = 0
i = 0
while i < len(s):
    if s[i] == 'A':
        a_num += 1
        i += 1
    elif s[i:i+2] == 'BC':
        ans += a_num
        i += 2
    else:
        a_num = 0
        b_num = 0
        i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
qS = input()


def replace(s, count):
    fi = s.find('ABC')
    if fi >= 0:
        newS = s[:fi] + 'BCA' + s[fi+3:]
        return replace(newS, count + 1)
    else:
        return count


print(replace(qS, 0))


Fixed submission:
# -*- coding: utf-8 -*-
s = input()

a_num = 0
bc_num = 0
ans = 0
i = 0
while i < len(s):
    if s[i] == 'A':
        a_num += 1
        i += 1
    elif s[i:i+2] == 'BC':
        ans += a_num
        i += 2
    else:
        a_num = 0
        b_num = 0
        i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import re

qS = input()


def replace(s, count):
    matches = re.finditer('ABC', s)
    max_count = count
    for m in matches:
        m.span()
        max_count = max(max_count, replace(
            s[:m.span()[0]] + 'BCA' + s[m.span()[1]:], count + 1))
    return max_count


print(replace(qS, 0))


Fixed submission:
# -*- coding: utf-8 -*-
s = input()

a_num = 0
bc_num = 0
ans = 0
i = 0
while i < len(s):
    if s[i] == 'A':
        a_num += 1
        i += 1
    elif s[i:i+2] == 'BC':
        ans += a_num
        i += 2
    else:
        a_num = 0
        b_num = 0
        i += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import re

qS = input()

counts = {}


def replace(s, count):
    if counts.get(s, -1) >= 0:
        return counts[s]
    else:
        matches = re.finditer('ABC', s)
        max_count = count
        for m in matches:
            m.span()
            max_count = max(max_count, replace(
                s[:m.span()[0]] + 'BCA' + s[m.span()[1]:], count + 1))
        counts[s] = max_count
        return counts[s]


print(replace(qS, 0))


Fixed submission:
# -*- coding: utf-8 -*-
s = input()

a_num = 0
bc_num = 0
ans = 0
i = 0
while i < len(s):
    if s[i] == 'A':
        a_num += 1
        i += 1
    elif s[i:i+2] == 'BC':
        ans += a_num
        i += 2
    else:
        a_num = 0
        b_num = 0
        i += 1

print(ans)