Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03006 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        x, y = MI()
        X[i], Y[i] = x, y

    dct = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j: continue
            xi, yi = X[i], Y[i]
            xj, yj = X[j], Y[j]

            dct[(xi-xj, yi-yj)] += 1
    # print(dct)
    mx = 0
    for d in dct.values():
        mx = max(mx, d)
    print(N - mx)


if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N = II()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        x, y = MI()
        X[i], Y[i] = x, y

    dct = defaultdict(int)
    for i in range(N):
        for j in range(N):
            if i == j: continue
            xi, yi = X[i], Y[i]
            xj, yj = X[j], Y[j]

            dct[(xi-xj, yi-yj)] += 1
    # print(dct)
    print(N - max(dct.values()))


if __name__ == '__main__':
    solve()
Problem p03043 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    n, k = MI()

    ans = 0
    for point in range(1, n+1):
        prob = 1
        while point < k:
            prob = prob / 2
            point = point * 2
        # print(point, prob)
        ans = ans + prob / n

    print(ans)

if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

from math import log2, ceil

def solve():
    n, k = MI()

    ans = 0
    m = ceil(log2(k))

    sm = 0
    v = 0
    for point in range(1, n+1):
        if 1 <= point < k:
            # さいころを振る
            # print(point)
            sm = sm + 1
            prob = 1
            for j in range(m+1):
                point = point * 2
                prob = prob / 2
                # print('  j+1', j+1, point)
                if point >= k:
                    # print(j)
                    ans = ans + prob
                    break
        else:
            # 無条件で勝利
            v = v + 1
    t = v / n
    print(ans * (1 - t) / sm + t)


if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

from math import log2, ceil

def solve():
    n, k = MI()

    ans = 0
    m = ceil(log2(k))

    sm = 0
    v = 0
    for point in range(1, n+1):
        if 1 <= point < k:
            # さいころを振る
            # print(point)
            sm = sm + 1
            for j in range(m+1):
                point = point * 2
                # print('  j+1', j+1, point)
                if point >= k:
                    # print(j)
                    if j != 0:
                        ans = ans + 1 / (pow(2, j+1))
                    break
        else:
            # 無条件で勝利
            v = v + 1
    t = v / n
    print(ans * (1 - t) / sm + t)


if __name__ == '__main__':
    solve()
Problem p03633 (python)

Fixed submission:
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

import fractions as math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

def solve():
    n = II()
    T = [II() for _ in range(n)]

    t1 = T[0]
    l = t1
    for t2 in T[1:]:
        l = lcm(t1, t2)
        t1 = l
    print(l)


if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

import fractions as math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

def solve():
    n = II()
    T = [II() for _ in range(n)]

    t1 = T[0]
    for t2 in T[1:]:
        l = lcm(t1, t2)
        t1 = l
    print(l)


if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

def solve():
    n = II()
    T = [II() for _ in range(n)]

    t1 = T[0]
    for t2 in T[1:]:
        l = lcm(t1, t2)
        t1 = l
    print(l)


if __name__ == '__main__':
    solve()
Problem p02618 (python)

Fixed submission:
d=int(input())
*c,=map(int, input().split())
s=[]
for _ in range(d):
    *si,=map(int, input().split())
    s.append(si)

for _ in range(d):
    print(1)

Buggy submission (verdict: Runtime Error):
d=int(input())
*c,=map(int, input().split())
s=[]
for _ in range(d):
    *si,=map(int, input().split())
    s.append(si)
#t=[int(input())-1 for _ in range(d)]
last=[-1]*26

ss=0
for i in range(d):
    ind=-1
    smx=-10**10
    for j in range(26):
        ssj=ss+s[j][t[j]]
        for j in range(26):
            if k!=j:
                ssj-= c[k]*(i-last[k])
        if smx<ssj:
            smx=max(ss,smx)
            ind=j
    last[ind]=i
    ss=smx        
    print(j)
Problem p02631 (python)

Fixed submission:
n=int(input())
*a,=map(int, input().split())
x=0
for ai in a:
    x^=ai

a=[ai^x for ai in a]
print(*a)

Buggy submission (verdict: Runtime Error):
import numpy as np
n=int(input())
*a,=map(int, input().split())
x=0
for ai in a:
    x^=ai

ans=[ai^x for ai in ans]
print(*ans)
Problem p02670 (python)

Fixed submission:
from collections import deque
n=int(input())
*p,=map(int, input().split())

for i in range(n*n):p[i]-=1
seats=[min(i//n,i%n,n-(i//n)-1,n-(i%n)-1) for i in range(n*n)] 

exist=[1]*(n*n)
dxy=(n,-n,1,-1)

ans=0
q=deque()
for pi in p:
    ans+=seats[pi]
    exist[pi]=0
    q.append(pi)
    while q:
        i=q.popleft()
        for dx in dxy:
            idx=i+dx
            if 0<=idx<n*n :
                if seats[i]+exist[i]<seats[idx]:
                    seats[idx]=seats[i]+exist[i]
                    q.append(idx)
print(ans)

Buggy submission (verdict: Runtime Error):
n=int(input())
*p,=map(int, input().split())
#n=3
#p=[1, 3, 7, 9, 5, 4, 8, 6, 2]

for i in range(n*n):p[i]-=1
seats=[
    [min(i,j,n-i-1,n-j-1)for i in range(n)] 
    for j in range(n)
    ]

check=[[False]*n for _ in range(n)]
exist=[[1]*n for _ in range(n)]
dxy=[(0,1),(1,0),(-1,0),(0,-1)]
def dfs(pi):
    global check,exist
    i=pi%n
    j=pi//n
    res=seats[i][j]
    check[i][j]=True
    for dx,dy in dxy:
        idx,jdy=i+dx,j+dy
        if 0<=idx<n and 0<=jdy<n and (not check[idx][jdy]):
            res=min(res,dfs(idx+jdy*n)+exist[idx][jdy])
        if res==0:
            return res
    seats[i][j]=res
    return res
ans=0
for pi in p:
    check=[[False]*n for _ in range(n)]
    ans+=dfs(pi)
    exist[pi%n][pi//n]=0
print(ans)
Problem p02690 (python)

Fixed submission:
#保証されている
#分解するとa<10**3となる...はずだが

x=int(input())

for b in range(10**3):
    a = int((x+b**5)**(1/5))
    for i in range(a-1000,a+1000):#小さい数でも漏れが出ている
        if i**5+b**5==x:
            print(i,-b)
            exit()
for b in range(10**3):
    a2=(x-b**5)
    if a2<0:
        continue
    a = int(a2**(1/5))
    
    for i in range(a-1000,a+1000):
        if i**5-b**5==x:
            print(i,b)
            exit()

Buggy submission (verdict: Runtime Error):
#保証されている
#分解するとa<10**3となる

x=int(input())

for b in range(10**3):
    a = int((x+b**5)**(1/5))
    for i in range(a-1,a+2):
        if a**5+b**5==x:
            print(a,-b)
            exit()
for b in range(10**3):
    a = int((x-b**5)**(1/5))
    if a<0:
        continue
    for i in range(a-1,a+2):
        if a**5+b**5==x:
            print(a,b)
            exit()
Problem p02702 (python)

Fixed submission:

s=input()
s=s[::-1]
md=[0]
ex10=1
tmp=0
mod=2019
for i in range(len(s)):
    tmp+=ex10*int(s[i])
    tmp%=mod
    md.append(tmp)
    ex10*=10
    ex10%=mod
from collections import Counter

sc= Counter(md)
ans=0
for k in sc:
    sck=sc[k]
    ans+= sck*(sck-1)//2
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
s=input()
s=s[::-1]
md=[0]
ex10=1
tmp=0
mod=2019
for i in range(len(s)):
    tmp+=ex10*int(s[i])
    tmp%=mod
    md.append(tmp)
    ex10*=10
    ex10%=mod
from collections import Counter

sc= Counter(md)
ans=0
for k in sc:
    sck=sc[k]
    ans+= sck*(sck-1)//2
print(ans)
Problem p02720 (python)

Fixed submission:
#dpより愚直に作るか
k = int(input())
lun = [i for i in range(10)]
while len(lun)<k+1:#正の整数
    lun2 = []
    for i in lun:
        lun2.append(i*10+(i%10))
        if i%10:
            lun2.append(i*10+(i%10)-1)
        if (i%10)<9:
            lun2.append(i*10+(i%10)+1)
    lun = list(set(lun+lun2))
lun.sort()
print(lun[k])

Buggy submission (verdict: Runtime Error):
#dpより愚直に作るか
k = int(input())
lun = [i for i in range(10)]
while len(lun)<k:
    lun2 = []
    for i in lun:
        lun2.append(i*10+(i%10))
        if i%10:
            lun2.append(i*10+(i%10)-1)
        if (i%10)<9:
            lun2.append(i*10+(i%10)+1)
    lun = list(set(lun+lun2))
lun.sort()
print(lun[k])

Buggy submission (verdict: Runtime Error):
#dpより愚直に作るか
k = int(input())
lun = [i for i in range(10)]
last = 10
while len(lun)<k:
    lun2 = []
    for i in lun:
        lun2.append(i*10+(i%10))
        if i%10:
            lun2.append(i*10+(i%10)-1)
        if (i%10)<9:
            lun2.append(i*10+(i%10)+1)
    last = len(lun2)
    lun = list(set(lun+lun2))
lun.sort()
print(lun[k])
Problem p02722 (python)

Fixed submission:
#nの約数とn-1の約数全部愚直
n = int(input())
fct1 = []
fct2 = []
for i in range(1,int(n**(1/2))+10):
    if n%i==0:
        fct1.append(i)
        fct2.append(n//i)
    if (n-1)%i==0:
        fct1.append(i)
        fct2.append((n-1)//i)

fct = set(fct1+fct2)
if 1 in fct:
    fct.remove(1)
ans = 0
for k in fct:
    n2 = n
    while n2 and n2%k==0:
        n2//=k
    n2%=k
    if n2==1:
        ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
#nの約数とn-1の約数全部愚直
n = int(input())
fct1 = []
fct2 = []
for i in range(1,int(n**(1/2))+10):
    if n%i==0:
        fct1.append(i)
        fct2.append(n//i)
    if (n-1)%i==0:
        fct1.append(i)
        fct2.append((n-1)//i)

fct = set(fct1+fct2)
if 1 in fct:
    fct.remove(1)
ans = 0
for k in fct:
    n2 = n
    while n2 and n2%k==0:
        n2//=k
        test += 1
    n2%=k
    if n2==1:
        ans += 1
print(ans)
Problem p02734 (python)

Fixed submission:
import numpy as np
n,s = map(int, input().split( ))

a = np.array(list(map(int, input().split( ))))

dp = np.array([[0]*3001 for i in range(n)])
dp[0][0] = 1
dp[0][a[0]] = 1

ans = 0
mod = 998244353
for i in range(1,n):
    dp[i] += dp[i-1]
    dp[i][a[i]:] += dp[i-1][:-a[i]]
    dp[i][0] +=1
    dp[i][a[i]] += 1
    dp[i]%=mod
    ans += dp[i][s]
print(ans%mod)

Buggy submission (verdict: Runtime Error):
import numpy as np
n,s = map(int, input().split( ))

a = np.array(list(map(int, input().split( ))))

dp = np.array([[0]*(s+1) for i in range(n)])
dp[0][0] = 1
dp[0][a[0]] = 1

ans = 0

for i in range(1,n):
    dp[i] += dp[i-1]
    dp[i][a[i]:] += dp[i-1][:-a[i]]
    dp[i][0] +=1
    dp[i][a[i]] += 1
    ans += dp[i][s]
print(ans)
Problem p02788 (python)

Fixed submission:
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]
from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):

    while Q:###ifから変更
        tmp2 = Q.popleft();
        if ms[tmp2][0]+2*d<ms[i][0]:###tmpじゃないわms[tmp2][0]だわ
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
            break###
    ms[i][1]-=tmp###
    ms[i][1] = max(ms[i][1],0)###

    if ms[i][1]>0:
        #ms[i][1]-=tmp　二回引いてるわ
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
print(ans)

Buggy submission (verdict: Runtime Error):
n,d,a= map(int, input().split( ))
ms = []
for i in range(n):
    xi,hi = map(int, input().split( ))
    tmp = 0
    if hi%a:
        tmp+=1
    ms.append([xi,hi//a+tmp])

ms.sort()
ans = ms[0][1]
tmp = ms[0][1]
from collections import deque

Q = deque()
Q.append(0)

for i in range(1,n):

    while Q:###ifから変更
        tmp2 = Q.popleft();
        if ms[tmp2][0]+2*d<ms[i][0]:###tmpじゃないわms[tmp2][0]だわ
            tmp -= ms[tmp2][1]
        else:
            Q.appendleft(tmp2)
            break###
    ms[i][1]-=tmp###
    ms[i][1] = max(ms[i][1],0)###

    if ms[i][1]>0:　
        ##ms[i][1]-=tmp　二回引いてるわ
        ans += ms[i][1]
        Q.append(i)
        tmp += ms[i][1]
print(ans)
Problem p02791 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split( )))
ans = 0
tmp = a[0]
for i in range(n):
    if tmp>=a[i]:
        tmp = a[i]
        ans += 1
    tmp = min(a[i],tmp)
print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
p = list(map(int, input().split( )))
ans = 0
tmp = 0
for i in range(n):
    if tmp>=a[i]:
        tmp = a[i]
        ans += 1
    tmp = max(a[i],tmp)
print(ans)
Problem p02811 (python)

Fixed submission:

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

if 500*k>=x:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
#小さいCから変更
n = int(input())
c = list(map(int, input().split( )))

c.sort()

#i　bit目が違うようなs,tは 2**(2*n-2)*2通り
sm = 0
for i in range(n):
    sm += (n-i)*c[i]

sm *= pow(2,2*n-2,10**9+7)

print(sm)

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

if 500*k>=x:
    print("Yes")
else:
    print("No")
Problem p02838 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split( )))
ans = 0
mod = 10**9+7
Bit = [0 for j in range(60)]# for i in range(n+1)
for j in range(60):#ループ交換
    for i in range(1,n):##1から
        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j]<<j
            ans %=mod
        else:
            ans += (i-Bit[j])<<j
            ans %= mod
    
print(ans)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split( )))
ans = 0
mod = 10**9+7
Bit = [0 for j in range(60)]# for i in range(n+1)
for j in range(60):#ループ交換
	for i in range(1,n):##1から

        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j]<<j
            ans %=mod
        else:
            ans += (i-Bit[j])<<j
            ans %= mod
    
print(ans)

Buggy submission (verdict: Runtime Error):
import sys,array
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split( )))
a = array.array("i",a)
ans = 0
mod = 10**9+7
Bit = [[0]*2 for j in range(60)]# for i in range(n+1)

for i in range(1,n):##1から
    for j in range(60):
        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j][0] += 1
        else:#ｊビット目1
            Bit[j][1] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j][0]<<j
            ans %=mod
        else:
            ans += Bit[j][1]<<j
            ans %= mod
    #print(Bit[:6])
"""
for i in range(1,n):##1から
    for j in range(60):

    #ans += a[i]
    #ans %=mod
    #自身の分
        #print(ans)
"""
print(ans)

Buggy submission (verdict: Runtime Error):
import sys,array
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split( )))
a = array.array("i",a)
ans = 0
mod = 10**9+7
Bit = [[0]*2 for j in range(60)]# for i in range(n+1)

for i in range(1,n):##1から
    for j in range(60):
        if not ((a[i-1]>>j)&1):#a[i-1]のjビット目0
            Bit[j][0] += 1
        else:#ｊビット目1
            Bit[j][1] += 1
        if ((a[i]>>j)&1):#aiのjビット目1
            ans += Bit[j][0]<<j
            ans %=mod
        else:
            ans += Bit[j][1]<<j
            ans %= mod
    #print(Bit[:6])
"""
for i in range(1,n):##1から
    for j in range(60):

    #ans += a[i]
    #ans %=mod
    #自身の分
        #print(ans)
"""
print(ans)
Problem p02844 (python)

Fixed submission:
#dp[i]:i+1桁目-n桁目で1桁の数字は/2桁の数字は/何通りあるか
n = int(input())
s = input()
ans = 0
for i in range(10):
    for j in range(10):
        t1 = n-1
        u1 = n-1
        for t in range(n):
            if i == int(s[t]):
                t1 = t
                break
        for u in range(t1+1,n):
            if j == int(s[u]):
                u1 = u
                break
        if int(s[t1]) == i and int(s[u1]) == j and t1<u1:
            #print(i,j,k,t1,u1,v1)
            ans += len(set(s[u1+1:]))
print(ans)

Buggy submission (verdict: Runtime Error):
#dp[i]:i+1桁目-n桁目で1桁の数字は/2桁の数字は/何通りあるか
n = int(input())
s = input()
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            for t in range(n):
                if i == int(s[t]):
                    break
            for u in range(t+1,n):
                if j == int(s[u]):
                    break
            for v in range(u+1,n):
                if k == int(s[v]):
                    break
            if int(s[t]) == i and int(s[u]) == j and int(s[v]) == k:
                ans += 1
print(ans)
Problem p02850 (python)

Fixed submission:

n = int(input())
Ad = [[] for _ in range(n)]
Deg = [0]*n
E = {}
E2 =[]
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    Ad[ai].append(bi)
    Ad[bi].append(ai)
    Deg[ai] += 1
    Deg[bi] += 1
    E[(ai,bi)]=-1
    E[(bi,ai)]=-1
    E2.append((ai,bi))
mx = max(Deg)
print(mx)
E[(0,0)] = -1#後の都合
P =[-1]*n#parent
from collections import deque
Q = deque()
Q.append(0)
P[0] = 0

while Q:
    v = Q.popleft()
    for u in Ad[v]:
        if P[u]<0:
            P[u] = v
            Q.append(u)

Q = deque()
cnt = 1
for v in Ad[0]:
    E[(0,v)]=cnt
    E[(v,0)]=cnt
    cnt+=1
    Q.append(v)

while Q:
    v = Q.popleft()
    cnt = 1
    for u in Ad[v]:
        if E[(u,v)]<0:
            if cnt==E[(v,P[v])]:
                cnt +=1
            E[(u,v)] = cnt
            E[(v,u)] = cnt
            cnt+=1
            Q.append(u)
for i in range(n-1):
    print(E[E2[i]])

Buggy submission (verdict: Runtime Error):
#「辺」彩色
#最大次数で可
#構成はset()使って色管理
#Adいらない
n = int(input())
#Ad = [set() for i in range(n)]
Deg = [0]*n
E = []
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    #Ad[ai].add(bi)
    #Ad[bi].add(ai)
    Deg[ai]+=1
    Deg[bi]+=1
    E.append((ai,bi))

cl = max(Deg)
Deg2 = [set(range(cl)) for i in range(n)]
print(cl)
for ai,bi in E:
    #"c = 0
    #while c  not in Deg2[ai] or c not in Deg2[bi]:
    #    #c+=1ここで色探すのが遅かった
    
    for c in Deg2[ai]:
        if c in Deg2[bi]:
            print(c+1)
            break
    Deg2[ai].remove(c)
    Deg2[bi].remove(c)