Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,k = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))

def solve(start):
    loopcnt = 0
    loopsum = 0
    reached = [0]*n
    scoremax = [-10**20]
    scoresum = 0
    ans = 0
    now = start
    while True:
        reached[now] = 1
        nxt = P[now]-1
        loopcnt += 1
        loopsum += C[now]
        scoresum += C[now]
        scoremax.append(max(scoremax[-1], scoresum))
        if reached[nxt]:break
        now = nxt
    if loopsum < 0 or loopcnt > k:
        ans = max(scoremax[1:k])
    else:
        ans = max(loopsum * (k//loopcnt) + scoremax[k%loopcnt],-10**20)#,max(scoremax[1:]))
    return ans #- C[start]
ans = -10**20
for i in range(n):
    ans = max(ans, solve(i))
    # print(solve(i))

print(ans)


Fixed submission:
n, k = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))


def solve(start):
    loop = []
    llen = 0
    lsum = 0
    reach = [0]*n

    now = start
    while True:
        nxt = P[now]-1
        loop.append(now)
        llen += 1
        lsum += C[now]
        reach[now] = 1
        if reach[nxt]:
            break
        now = nxt
    
    if lsum <= 0 or llen >= k:
        res = -10 ** 20
        s = 0
        now = start
        for i in range(min(llen, k)):
            s += C[now]
            res = max(res, s)
            now = P[now]-1
        return res
    else:
        s = lsum * (k // llen)
        now = start
        for i in range(k % llen):
            s += C[now]
            now = P[now]-1
        j = loop.index(now)
        res = -10**20
        for i in range(llen):
            j -= 1
            res = max(res, s)
            s -= C[loop[j]]
        return res


def solver():
    ans = -10 ** 20
    for i in range(n):
        ans = max(ans, solve(i))
    return ans


print(solver())
Buggy python submission (verdict: Time Limit Exceeded):
def nth_element(array, will):
    will -= 1
    n = len(array)
    left = 0
    right = n-1
    while right > left:
        i = left-1
        j = right
        v = array[right]
        while True:
            i += 1
            j -= 1
            while array[i]<v:i+=1
            while array[j]>v:j-=1
            if i>=j:break
            array[i],array[j] = array[j],array[i]
        array[i],array[right] = array[right],array[i]
        if i == will:break
        if i > will:
            right = i-1
        else:
            left = i+1
    return array

# from random import randrange
# for i in range(100):

n = int(input())
A = list(map(int,input().split()))
# n = randrange(2,10)
# A = [0]*n
# for j in range(n):
#     A[j] = randrange(1,1000)
k = 1 + (n-1)//2

nth_element(A,n-k+1)
# B = sorted(A)
ans = 0
M = 0
# m = B[-1]
for i in range(-1,n-1):
    ans += A[n - (i+1)//2 - 1]
    M = max(M, A[n- (i+1)//2 - 1])
    # ans -= B[n-(i+1)//2 - 1]
ans -= M
# ans += m
# if ans != 0:
#     print(n,A)
print(ans)


Fixed submission:
n = int(input())
A = list(map(int,input().split()))

A.sort(reverse = True)

ans = 0
can = 1
last = 0
for i in range(n-1):
    ans += A[last]
    can -= 1
    if can == 0:
        can = 2
        last += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()

def f(k):
    return chr(97+k)

c = 0
i = 1
while True:
    d = c+pow(26,i)
    if c < n <= d:
        break
    c = d
    i+=1

m = n-c-1
ans = ''
for _ in range(i)
    ans = f(m%26) + ans
    m = m//26
ans = f(m%26) + ans

# ans = 'a'*(i-len(ans)) + ans

print(ans)


Fixed submission:
n = int(input())
i = 1
while pow(26,i) < n:
    n -= pow(26,i)
    i += 1
ans = ''
n -= 1
for _ in range(i):
    ans += chr(ord('a') + n%26)
    n //= 26
print(ans[::-1])
Buggy python submission (verdict: Runtime Error):
a,b,c,d = map(int,input().split())
mod = 998244353
dp = [[0]*(d-b+1) for i in range(c-a+1)]
if a == c and b == d:
    print(1)
elif a == c:
    print(a)
elif b == d:
    print(b):
else:
    for i in range(c-a):
        p = 0
        for j in range(d-b+1):
            if i == j == 0:
                dp[i][j] = 1
            dp[i+1][j] = (p + dp[i][j]*(b+j))%mod

            p += dp[i][j]
            p %= mod
            p *= a+i
            p %= mod

    ans = 0
    for d in dp[-1]:
        ans *= c
        ans %= mod
        ans += d
        ans %= mod
    print(ans)

Fixed submission:
a,b,c,d = map(int,input().split())
mod = 998244353
dp = [[0]*(d-b+1) for i in range(c-a+1)]
if a == c and b == d:
    print(1)
elif a == c:
    print(pow(a,d-b,mod))
elif b == d:
    print(pow(b,c-a,mod))
else:
    for i in range(c-a):
        p = 0
        for j in range(d-b+1):
            if i == j == 0:
                dp[i][j] = 1
            dp[i+1][j] = (p + dp[i][j]*(b+j))%mod

            p += dp[i][j]
            p %= mod
            p *= a+i
            p %= mod

    ans = 0
    for d in dp[-1]:
        ans *= c
        ans %= mod
        ans += d
        ans %= mod
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = list(map(int,input().split()))

ans = 0
can = 1
for a in A:
    if can < a:
        print(-1)
        exit(0)
    else:
        can -= a
        can *= 2
can //= 2
can += A[-1]
real = A[-1]
for i in range(n-1,-1,-1):
    ans += real
    real = min(real,can//2)
    real += A[i]
    can //= 2
    can += A[i]
print(ans + 1)


Fixed submission:
n = int(input())
A = list(map(int,input().split()))
Can = [0]*n
ans = 0
can = 1
for i,a in enumerate(A):
    if can < a:
        print(-1)
        exit(0)
    elif i < n:
        can -= a
        can *= 2
        Can[i] = can
real = A[-1]
for i in range(n-1,-1,-1):
    ans += real
    real = min(real,Can[i]//2)
    real += A[i]
print(ans + 1)
Buggy python submission (verdict: Runtime Error):
import itertools
n,m,q = map(int,input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
ans = 0
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    cnt = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            cnt += d[i]
    ans = max(ans,tmp)
print(ans)


Fixed submission:
import itertools
n,m,q = map(int,input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
ans = 0
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    tmp = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            tmp += d[i]
    ans = max(ans,tmp)
print(ans)

Buggy python submission (verdict: Runtime Error):
n,m,q = map(int,input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(n):
    a[i],b[i],c[i],d[i] = map(int,input().split())
    a[i] -= 1
    b[i] -= 1
A = [0]*n
ans = 0
def dfs(h):
    global ans
    if h == n-1:
        cnt = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                cnt += d[i]
        ans = max(ans,cnt)
    else:
        for i in range(A[h],m+1):
            A[h+1] = i
            dfs(h+1)
    return

for i in range(1,m+1):
    A[0] = i
    dfs(0)
print(ans)


Fixed submission:
import itertools
n,m,q = map(int,input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q
for i in range(q):
    a[i],b[i],c[i],d[i] = map(int,input().split())
ans = 0
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    tmp = 0
    for i in range(q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            tmp += d[i]
    ans = max(ans,tmp)
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
can = set(range(1,n+1))
ans = [[0,0] for _ in range(m)]
done = 0
for i in range(1,n+1):
    if done == m:break
    if i not in can:continue
    else:
        ans[done] = [i,i+done+1]
        can.remove(i+done+1)
        done += 1
for i in range(m):
    print(' '.join(str(i) for i in ans[i]))


Fixed submission:
n,m = map(int,input().split())
done = 0
for i in range(1,m+1)[::-1]:
    if (m-i)&1:
        print(m+1+(m+1-i)//2,m+1+(m+1-i)//2+i)
    else:
        print((m-i)//2 + 1,(m-i)//2 + 1 + i)
Buggy python submission (verdict: Time Limit Exceeded):
import collections
s = input()
n = len(s)
mod = [0]*(n+1)
for i in range(n):
    mod[i+1] = (mod[i] + int(s[-1-i])*pow(10,i))%2019
d = collections.Counter(mod)
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)


Fixed submission:
import collections
s = list(input())
n = len(s)
mod = [0]*(n+1)
pow10 = 1
for i in range(n):
    mod[i+1] = (mod[i] + int(s[-1-i])*pow10)%2019
    pow10 = pow10*10%2019
d = collections.Counter(mod)
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(a,k+1):
    ab = gcd(a,b)
    for c in range(c,k+1):
      g = gcd(ab,c)
      if a == b == c:
        ans += g
      elif a!=b!=c!=a:
        ans += g*6
      else:
        ans += g*3
print(ans)


Fixed submission:
from math import gcd
k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(a,k+1):
    ab = gcd(a,b)
    for c in range(b,k+1):
      g = gcd(ab,c)
      if a == b == c:
        ans += g
      elif a != b !=c != a:
        ans += g*6
      else:
        ans += g*3
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
s = input()
R = set()
G = set()
B = set()
for i in range(s):
    if s[i] == 'R':
        R.add(i)
    elif s[i] == 'B':
        B.add(i)
    else:
        G.add(i)
ans = 0
for r in R:
    for g in G:
        ans += len(B)
        if 2*r - g in B:
            ans -= 1
        if 2*g - r in B:
            ans -= 1
        if not (r+g)&1 and (r+g)//2 in B:
            ans -= 1
print(ans)


Fixed submission:
n = int(input())
s = input()
R = set()
G = set()
B = set()
for i in range(n):
    if s[i] == 'R':
        R.add(i)
    elif s[i] == 'B':
        B.add(i)
    else:
        G.add(i)
ans = 0
for r in R:
    for g in G:
        ans += len(B)
        if 2*r - g in B:
            ans -= 1
        if 2*g - r in B:
            ans -= 1
        if not (r+g)&1 and (r+g)//2 in B:
            ans -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k,c = map(int,input().split())
s = list(input())

ans = []
cnt = 0
kcn = 0
for i,x in enumerate(s[::-1]):
    i = n - i - 1
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        ans.append(i)
cnt = 0
j = len(ans) - 1
kcn = 0
for i,x in enumerate(s):
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        # while 0<=j and ans[j] <= i:
        #     if ans[j] == i:
        #         print(i+1)
        #     j -= 1
        if i in ans:
            print(i+1)


Fixed submission:
n,k,c = map(int,input().split())
s = list(input())

ans = []
cnt = 0
kcn = 0
for i,x in enumerate(s[::-1]):
    i = n - i - 1
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        ans.append(i)

cnt = 0
j = len(ans) - 1
kcn = 0
for i,x in enumerate(s):
    if cnt:
        cnt -= 1
    elif x == 'o' and kcn < k:
        cnt += c
        kcn += 1
        if ans[j] == i:
            print(i+1)
        j -= 1
Buggy python submission (verdict: Time Limit Exceeded):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def main():
    n = int(input())
    ans = 0
    div = make_divisors(n)
    for i in div[::1]:
        var = n
        while not var%i:
            var = var // i
        if var%i == 1:
            ans += 1
    ans += len(make_divisors(n-1)) - 1
    print(ans)

main()


Fixed submission:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def main():
    n = int(input())
    ans = 0
    div = make_divisors(n)
    for i in div[1:]:
        var = n
        while not var%i:
            var = var // i
        if var%i == 1:
            ans += 1
    ans += len(make_divisors(n-1)) - 1
    print(ans)

main()
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n = int(readline())

mod = 10**9 + 7

def expo(x,n):
    var = 1
    while n>0:
        if n%2 == 1:
            var = (var*x) % mod
        x = (x*x)%mod
        n = n>>1
    return var

def conbi(*x):
    num = 1
    den = 1
    for i in range(1,sum(x)+1):
        num = (num*i)%mod
    for i in x:
        for j in range(1,i+1):
            den = (den * j)%mod
    return (num*expo(den,mod-2))%mod

path = [set() for _ in range(n)]
pathq= [0]*n

for _ in range(n-1):
    a,b = map(int,read().split())
    a -= 1
    b -= 1
    path[a].add(b)
    pathq[a] += 1
    path[b].add(a)
    pathq[b] += 1

memo = {}
def go(i,j):
    if (i,j) in memo.keys():
        return memo[(i,j)]
    else:
        memo[(i,j)] = [1,1]
        cnt = []
        meth = 1
        for k in path[j]:
            if i != k:
                [x,y] = go(j,k)
                meth *= y
                meth %= mod
                cnt.append(x)
        memo[(i,j)] = [sum(cnt)%mod + 1, meth*conbi(*cnt)%mod]
        return memo[(i,j)]

for i in range(n):
    ans = 1
    cnt = []
    meth = 1
    for j in path[i]:
        [x,y] = go(i,j)
        meth *= y
        meth %= mod
        cnt.append(x)
    print(meth*conbi(*cnt)%mod)


Fixed submission:
s = input()
if s[2] == s[3] and s[5] == s[4]:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Runtime Error):
s = input()
if s == 'AAA' or s == 'BBB':
  print(No)
else:
  print(Yes)

Fixed submission:
s = input()
if s == 'AAA' or s == 'BBB':
  print('No')
else:
  print('Yes')
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
array = [10]*N
T_F = True

for i in range(M):
  s,c = map(int,input().split())
  if s>N or (array[s-1] != 10 and array[s-1] !=c) or (s == 1 and c == 0):
    T_F = False
    break
  else:
    array[s-1] = c
ans = 0

if T_F:
  for i in range(N):
  if array[i] == 10:
      array[i] == 0
  ans += array[i]*(10**(N-i-1))
  if array[0]:
    print(ans)
  else:
    print(ans+10**(N-1))
else:
  print(-1)

Fixed submission:
N,M = map(int,input().split())
array = [10]*N
T_F = True

for i in range(M):
  s,c = map(int,input().split())
  if s>N or (array[s-1] != 10 and array[s-1] !=c) or (s == 1 and c == 0 and N != 1):
    T_F = False
    break
  else:
    array[s-1] = c

ans = 0
if T_F:
  for i in range(N):
    if array[i] == 10:
        array[i] = 0
    ans += array[i]*(10**(N-i-1))
  if array[0] or N == 1:
    print(ans)
  else:
    print(ans+10**(N-1))
else:
  print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
class BinaryIndexedTree:
    def __init__(self,n,default = 0):
        self.s = [default]*(n+1)
        self.n = n
    
    def add(self,val,idx):
        while idx < self.n+1:
            self.s[idx] = self.s[idx] + val
            idx += idx&(-idx)
        return
    
    def get(self,idx):
        res = 0
        while idx > 0:
            res = res + self.s[idx]
            idx -= idx&(-idx)
        return res

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
S = [ord(s) - ord('a') for s in input()[:-1]]

BIT = [BinaryIndexedTree(n) for i in range(26)]

for i,s in enumerate(S):
    BIT[s].add(1,i+1)

Q = int(input())
ans = []
for _ in range(Q):  
    flag,x,y = input().split()

    if flag == "1":
        i = int(x)
        c = ord(y) - ord('a')
        BIT[S[i-1]].add(-1,i)
        BIT[c].add(1,i)
        S[i-1] = c
    else:
        l = int(x)
        r = int(y)
        res = 0
        for i in range(26):
            # print([BIT[i].get(r),BIT[i].get(l)])
            res += (BIT[i].get(r) > BIT[i].get(l-1))
        ans.append(str(res))
print("\n".join(ans))


Fixed submission:
class BinaryIndexedTree:
    def __init__(self,n,default = 0):
        self.s = [default]*(n+1)
        self.n = n
    
    def add(self,val,idx):
        while idx < self.n+1:
            self.s[idx] = self.s[idx] + val
            idx += idx&(-idx)
        return
    
    def get(self,idx):
        res = 0
        while idx > 0:
            res = res + self.s[idx]
            idx -= idx&(-idx)
        return res

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
S = [ord(s) - ord('a') for s in input()[:-1]]

BIT = [BinaryIndexedTree(n) for i in range(26)]

for i,s in enumerate(S):
    BIT[s].add(1,i+1)

Q = int(input())
ans = []
for _ in range(Q):  
    flag,x,y = input().split()

    if flag == "1":
        i = int(x)
        c = ord(y) - ord('a')
        BIT[S[i-1]].add(-1,i)
        BIT[c].add(1,i)
        S[i-1] = c
    else:
        l = int(x)
        r = int(y)
        res = 0
        for i in range(26):
            # print([BIT[i].get(r),BIT[i].get(l)])
            res += (BIT[i].get(r) > BIT[i].get(l-1))
        ans.append(str(res))
print("\n".join(ans))
Buggy python submission (verdict: Runtime Error):
n = int(input())

x = list(map(int,input().split()))

ans = float('inf')

for i in range(1,101):
  ans_temp = 0
  for j in x:
    ans_temp += (x-i)**2
  ans = min(ans,ans_temp)
print(ans)

Fixed submission:
n = int(input())

x = list(map(int,input().split()))

ans = float('inf')

for i in range(1,101):
  ans_temp = 0
  for j in x:
    ans_temp += (j-i)**2
  ans = min(ans,ans_temp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,A,B = map(int,input().split())

ans = 0 
mod = 7+10**9

def expo(x,n):
  var = 1
  while n>0:
    if n%2 == 1:
      var = (var*x) % mod
    x = (x*x)%mod
    n = n>>1
  return var

def combi(n,k):
  N = 1
  mK = 1
  mN_K = 1
  for i in range(1,n+1):
    N = (N*i)%mod
  for i in range(1,k+1):
    mK = (mK * expo(i,mod-2))%(mod)
  for i in range(1,n-k+1):
    mN_K = (mN_K*expo(i,mod-2))%mod
  return (((N*mK)%mod)*mN_K)%mod

print(expo(2,N)-1-combi(N,A)-combi(N,B))

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

ans = 0 
mod = 7+10**9

def expo(x,n):
  var = 1
  while n>0:
    if n%2 == 1:
      var = (var*x) % mod
    x = (x*x)%mod
    n = n>>1
  return var

def combi(n,k):
  N = 1
  K = 1
  for i in range(n-k+1,n+1):
    N = (N*i)%mod
  for i in range(1,k+1):
    K = (K * i)%mod
  return (N*expo(K,mod-2))%mod

print((expo(2,N)-1-combi(N,A)-combi(N,B))%mod)
Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
dp = [float('inf')]*(h+1)
dp[0] = 0

for i in range(n):
    for j in range(h+1):
        if dp[j] != float('inf'):
            nj = j + a[i]
            if nj >= h:
                nj = h
            dp[nj] = min(dp[nj],dp[j] + b[i])
print(dp[h])


Fixed submission:
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
dp = [1e100]*(h+1)
dp[0] = 0

for i in range(n):
    for j in range(h+1):
        if dp[j] != 1e100:
            nj = j + a[i]
            if nj >= h:
                nj = h
            dp[nj] = min(dp[nj],dp[j] + b[i])
print(dp[h])

Buggy python submission (verdict: Time Limit Exceeded):
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
dp = [-1]*(h+1)
dp[0] = 0

for i in range(n):
    for j in range(h+1)[::-1]:
        if dp[j] != -1:
            for k in range((h-j)//a[i] + 1):
                dj = a[i] * (k+1)
                if j + dj >= h :
                    nj = h
                else:
                    nj = j+dj
                if dp[nj] == -1:
                    dp[nj] = dp[j] + b[i]*(k+1)
                    continue
                dp[nj] = min(dp[nj],dp[j] + b[i]*(k+1))
print(dp[h])


Fixed submission:
h,n = map(int,input().split())
a = [0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())
dp = [1e100]*(h+1)
dp[0] = 0

for i in range(n):
    for j in range(h+1):
        if dp[j] != 1e100:
            nj = j + a[i]
            if nj >= h:
                nj = h
            dp[nj] = min(dp[nj],dp[j] + b[i])
print(dp[h])
Buggy python submission (verdict: Runtime Error):
a,b = map(int,input().split())
print(str(min(a,b)*max(a,b))

Fixed submission:
a,b = map(int,input().split())
print(str(min(a,b))*max(a,b))
Buggy python submission (verdict: Runtime Error):
s = int(input())
n = len(s)
ans = 0
for i in range(n//2):
  if s[i] != s[n-i-1]:
    ans += 1
print(ans)


Fixed submission:
s = input()
n = len(s)
ans = 0
for i in range(n//2):
  if s[i] != s[n-i-1]:
    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n = int(input())
path = [[] for _ in range(n)]
ab = []
color = [0]*(n-1)
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  ab.append([a,b])
  path[a].append(b)
  path[b].append(a)
  
que = deque()
que.append((0,0))
reached = [False]*n
reached[0] = True
while que:
  p,pc = que.popleft()
  c = 0
  for i in path[p]:
    if reached[i] == False:
      while True:
        c += 1
        if c == pc:continue
        color[ab.index(sorted([p,i]))] = c
        break
      reached[i] = True
      que.append((i,c))
print(max(color))
for i in color:
  print(i)


Fixed submission:
from collections import deque
n = int(input())
path = [[] for _ in range(n)]
ab = []
color = {}
for i in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  ab.append((a,b))
  path[a].append(b)
  path[b].append(a)
  
que = deque()
que.append((0,0))
reached = [False]*n
reached[0] = True
while que:
  p,pc = que.popleft()
  c = 0
  for i in path[p]:
    if reached[i] == False:
      while True:
        c += 1
        if c == pc:continue
        color[tuple(sorted((p,i)))] = c
        break
      reached[i] = True
      que.append((i,c))
print(max(color.values()))
for i in ab:
  print(color[i])
Buggy python submission (verdict: Runtime Error):
n,t = map(int,input().split())
ab = [[0,0] for _ in range(n)]
for i in range(n):
    ab[i] = list(map(int,input().split()))
dp = [[0]*t for i in range(n+1)]
ab.sort()
ans = 0
for i in range(n):
    a,b = ab[i]
    for j in range(t)[::-1]:
        v = dp[i][j]
        ans = max(ans,v+b)
        dp[i+1][j] = max(dp[i+1][j], dp[j][i])
        if j + a >= t:continue
        dp[i+1][j+a] = max(dp[i][j+a], v+b)
print(ans)


Fixed submission:
n,t = map(int,input().split())
ab = [[0,0] for _ in range(n)]
for i in range(n):
    ab[i] = list(map(int,input().split()))
dp = [[0]*t for i in range(n+1)]
ab.sort()
ans = 0
for i in range(n):
    a,b = ab[i]
    for j in range(t)[::-1]:
        v = dp[i][j]
        ans = max(ans,v+b)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j + a >= t:continue
        dp[i+1][j+a] = max(dp[i][j+a], v+b)
print(ans)
Buggy python submission (verdict: Runtime Error):
from itertools import *
n = int(input())
d = list(map(int,input().split()))
ans = 0
for i,j in comninations(d,2):
  ans += i*j
print(ans)


Fixed submission:
from itertools import *
n = int(input())
d = list(map(int,input().split()))
ans = 0
for i,j in combinations(d,2):
  ans += i*j
print(ans)