Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def update(BIT,index,letter,value):
    while index < len(BIT):
        BIT[index][letter] += value
        index += index&-index

def sumQuery(BIT,index):
    letters = [0]*26
    while index > 0:
        for i in range(26):
            letters[i] += BIT[index][i]

        index -= index&-index

    return letters

def rangeQuery(BIT,l,r,ans):
    right = sumQuery(BIT,r)
    left = sumQuery(BIT,l-1)
    count = 0
    for i in range(26):
        right[i] -= left[i]
        if right[i] > 0:
            count += 1

    ans.append(count)

def main():
    n = int(input())
    s = list(input())
    q = int(input())
    BIT = [[0 for i in range(26)] for j in range(n+1)]
    ans = []

    for i in range(n):
        update(BIT,i+1,ord(s[i])-ord('a'),1)

    for i in range(q):
        query,index,c = map(str,input().split())
        query = int(query)
        if query == 1:
            index = int(index)
            update(BIT,index,ord(s[index-1])-ord('a'),-1)
            s[index-1] = c
            update(BIT,index,ord(s[index-1])-ord('a'),1)
        else:
            l,r = int(index),int(c)
            rangeQuery(BIT,l,r,ans)

    for i in ans:
        print(i)


main()


Fixed submission:
def update(BIT,index,letter,value):
    while index < len(BIT):
        BIT[index][letter] += value
        index += index&-index

def sumQuery(BIT,index):
    letters = [0]*26
    while index > 0:
        for i in range(26):
            letters[i] += BIT[index][i]

        index -= index&-index

    return letters

def rangeQuery(BIT,l,r,ans):
    right = sumQuery(BIT,r)
    left = sumQuery(BIT,l-1)
    count = 0
    for i in range(26):
        right[i] -= left[i]
        if right[i] > 0:
            count += 1

    ans.append(count)

def main():
    n = int(input())
    s = list(input())
    q = int(input())
    BIT = [[0 for i in range(26)] for j in range(n+1)]
    ans = []

    for i in range(n):
        update(BIT,i+1,ord(s[i])-ord('a'),1)

    for i in range(q):
        query,index,c = map(str,input().split())
        query = int(query)
        if query == 1:
            index = int(index)
            update(BIT,index,ord(s[index-1])-ord('a'),-1)
            s[index-1] = c
            update(BIT,index,ord(s[index-1])-ord('a'),1)
        else:
            l,r = int(index),int(c)
            rangeQuery(BIT,l,r,ans)

    for i in ans:
        print(i)


main()
Buggy python submission (verdict: Runtime Error):
import math

def main():
  h = int(inout())
  w = int(input())
  n = int(input())
  print(math.ceil(n/(max(h,w))))
  
  
main()

Fixed submission:
import math

def main():
    h = int(input())
    w = int(input())
    n = int(input())
    print(math.ceil(n/(max(h,w))))

main()
Buggy python submission (verdict: Runtime Error):
import math

def main():
    a,b = map(int,input().split())
    gcd = math.gcd(max(a,b),min(a,b))
    lcm = a*b//gcd

    print(lcm)

main()


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

def main():
    a,b = map(int,input().split())
    g = gcd(max(a,b),min(a,b))
    lcm = a*b//g

    print(lcm)

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    t = input()
    sletters = set()
    for i in s:
        sletters.add(i)

    for i in t:
        if i not in sletters:
            print(-1)
            return

    i = 0
    j = 0
    ans = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            j += 1
        i += 1
        ans += 1
        if i == len(s):
            i = 0

    print(ans)


main()


Fixed submission:
import bisect

def main():
    s = input()
    t = input()
    sletters = [0]*26
    for i in range(len(s)):
        x = ord(s[i])-ord('a')
        if sletters[x] == 0:
            sletters[x] = [i]
        else:
            sletters[x].append(i)

    ans = 0
    curr_index = -1
    for i in t:
        x = ord(i)-ord('a')
        if sletters[x] == 0:
            print(-1)
            return
        index = bisect.bisect(sletters[x],curr_index)
        #print(sletters[x],i,curr_index,index)
        if index == len(sletters[x]):
            ans += len(s)-curr_index
            curr_index = sletters[x][0]
            ans += curr_index
        else:
            ans += sletters[x][index]-curr_index
            curr_index = sletters[x][index]
        

    print(ans)


main()

Buggy python submission (verdict: Runtime Error):
def main():
    s = input()
    t = input()
    sletters = set()
    for i in s:
        sletters.add(i)

    for i in t:
        if i not in sletters:
            print(-1)
            return

    s = s*len(t)
    i = 0
    j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
            j += 1
        else:
            i += 1

    print(i)


main()


Fixed submission:
import bisect

def main():
    s = input()
    t = input()
    sletters = [0]*26
    for i in range(len(s)):
        x = ord(s[i])-ord('a')
        if sletters[x] == 0:
            sletters[x] = [i]
        else:
            sletters[x].append(i)

    ans = 0
    curr_index = -1
    for i in t:
        x = ord(i)-ord('a')
        if sletters[x] == 0:
            print(-1)
            return
        index = bisect.bisect(sletters[x],curr_index)
        #print(sletters[x],i,curr_index,index)
        if index == len(sletters[x]):
            ans += len(s)-curr_index
            curr_index = sletters[x][0]
            ans += curr_index
        else:
            ans += sletters[x][index]-curr_index
            curr_index = sletters[x][index]
        

    print(ans)


main()
Buggy python submission (verdict: Runtime Error):
import math

def main():
    a,b,c,d = map(int,input().split())
    total = b-a+1
    n1 = (b//c)-(a//c)
    n2 = (b//d)-(a//d)
    lcm = (c*d)//math.gcd(c,d)
    n3 = (b//lcm)-(a//lcm)
    if a%c == 0:
        n1 += 1
    if a%d == 0:
        n2 += 1
    if a%lcm == 0:
        n3 += 1

    #print(n1,n2,n3)
    print(total-n1-n2+n3)

main()


Fixed submission:
def gcd(n1,n2):
    if n2 > n1:
        return gcd(n2,n1)
    if n2 == 0:
        return n1
    return gcd(n2,n1%n2)

def main():
    a,b,c,d = map(int,input().split())
    total = b-a+1
    n1 = (b//c)-(a//c)
    n2 = (b//d)-(a//d)
    lcm = (c*d)//gcd(c,d)
    n3 = (b//lcm)-(a//lcm)
    if a%c == 0:
        n1 += 1
    if a%d == 0:
        n2 += 1
    if a%lcm == 0:
        n3 += 1

    #print(n1,n2,n3)
    print(total-n1-n2+n3)

main()
Buggy python submission (verdict: Runtime Error):
def main():
    n,k = map(int,input().split())
    hts = list(map(int,input().split()))
    
    dp = [float('inf')]*n
    dp[0] = 0
    dp[1] = abs(hts[1]-hts[0])

    for i in range(2,min(k,n)):
        ans = dp[i]
        for j in range(i,0,-1):
            ans = min(ans,dp[i-j]+abs(hts[i]-hts[i-j]))

        dp[i] = ans

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

        dp[i] = ans

    #print(dp)

    print(dp[-1])

main()


Fixed submission:
def main():
    n = int(input())
    hts = list(map(int,input().split()))
    if n == 2:
        print(abs(hts[0]-hts[1]))
        return
    
    dp = [0]*n
    dp[0] = 0
    dp[1] = abs(hts[1]-hts[0])
    dp[2] = abs(hts[2]-hts[0])

    for i in range(3,n):
        dp[i] = min(dp[i-1]+abs(hts[i]-hts[i-1]),
                    dp[i-2]+abs(hts[i]-hts[i-2]))

    print(dp[-1])

main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n,k = map(int,input().split())
    hts = list(map(int,input().split()))
    
    dp = [float('inf')]*n
    dp[0] = 0
    dp[1] = abs(hts[1]-hts[0])

    for i in range(2,min(k,n)):
        ans = dp[i]
        for j in range(i,0,-1):
            ans = min(ans,dp[i-j]+abs(hts[i]-hts[i-j]))

        dp[i] = ans

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

        dp[i] = ans

    #print(dp)

    print(dp[-1])

main()


Fixed submission:
def main():
    n,k = map(int,input().split())
    hts = list(map(int,input().split()))
    
    dp = [float('inf')]*n
    dp[0] = 0
    dp[1] = abs(hts[1]-hts[0])

    for i in range(2,min(k,n)):
        ans = dp[i]
        for j in range(i,0,-1):
            ans = min(ans,dp[i-j]+abs(hts[i]-hts[i-j]))

        dp[i] = ans

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

        dp[i] = ans

    #print(dp)

    print(dp[-1])

main()
Buggy python submission (verdict: Runtime Error):
print(1-int(input())

Fixed submission:
print(1-int(input()))
Buggy python submission (verdict: Runtime Error):
N=int(input())
MOD=10**9+7
MAX=N+1
powerls=[0 for i in range(MAX)]
powerls[0]=1
powerls[1]=base                     
def powermod(ind):
  if powerls[ind]!=0:
    return powerls[ind]
  elif ind%2==0:
    p=(powermod(base,ind//2)**2)%MOD
    powerls[ind]=p
    return p
  else:
    p=((powermod(base,ind//2)**2)*base)%MOD     
    powerls[ind]=p
    return p

print((powermod(10,N)-2*powermod(9,N)+powermod(8,N))%MOD)


Fixed submission:
N=int(input())
MOD=10**9+7
MAX=N+1
def powermod(base,ind):
  if ind==1:
    return base
  elif ind%2==0:
    return (powermod(base,ind//2)**2)%MOD
  else:
    return ((powermod(base,ind//2)**2)*base)%MOD

print((powermod(10,N)-2*powermod(9,N)+powermod(8,N))%MOD)
Buggy python submission (verdict: Runtime Error):
N=int(input())
MOD=10**9+7
DP1=[0 for _ in range(N+2)]
DP2=[0 for _ in range(N+2)]
DP1[3]=1
DP2[3]=1
for i in range(4,N+1):
  DP1[i]=(DP2[i-3]+1)%MOD
  DP2[i]=(DP1[i]+DP2[i-1])%MOD
print(DP1[N])

Fixed submission:
N=int(input())
MOD=10**9+7
DP1=[0 for _ in range(N+3)]
DP2=[0 for _ in range(N+3)]
DP1[3]=1
DP2[3]=1
for i in range(4,N+1):
  DP1[i]=(DP2[i-3]+1)%MOD
  DP2[i]=(DP1[i]+DP2[i-1])%MOD
print(DP1[N])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
if N%2==0:
  print(-1)
else:
  ans=1
  a=7
  num=7
  while(num%N!=0):
    a=(a*10)%N
    num=(num+a)%N
    ans+=1
  print(ans)
  


Fixed submission:
N=int(input())
if N%2==0:
  print(-1)
elif N%5==0:
  print(-1)
else:
  ans=1
  a=7
  num=7
  while(num%N!=0):
    a=(a*10)%N
    num=(num+a)%N
    ans+=1
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ls=[int(s) for s in input().split()]
money=1000
stock=0
for i in range(N-1):
  if ls[i]<ls[i+1]:
    while money>=ls[i]:
      money-=ls[i]
      stock+=1
  elif ls[i]>ls[i+1]:
    money+=ls[i]*stock
    stock=0
money+=ls[N-1]*stock

print(money)

Fixed submission:
N=int(input())
ls=[int(s) for s in input().split()]
money=1000
stock=0
for i in range(N-1):
  if ls[i]<ls[i+1]:
    s=money//ls[i]
    money-=s*ls[i]
    stock+=s
  elif ls[i]>ls[i+1]:
    money+=ls[i]*stock
    stock=0
money+=ls[N-1]*stock

print(money)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ls=[int(s) for s in input().split()]
money=1000
stock=0
for i in range(N-1):
  if ls[i]<ls[i+1]:
    while money>=ls[i]:
      money-=ls[i]
      stock+=1
  elif ls[i]>ls[i+1]:
    while stock>0:
      money+=ls[i]
      stock-=1
while stock>0:
  money+=ls[N-1]
  stock-=1
print(money)

Fixed submission:
N=int(input())
ls=[int(s) for s in input().split()]
money=1000
stock=0
for i in range(N-1):
  if ls[i]<ls[i+1]:
    s=money//ls[i]
    money-=s*ls[i]
    stock+=s
  elif ls[i]>ls[i+1]:
    money+=ls[i]*stock
    stock=0
money+=ls[N-1]*stock

print(money)
Buggy python submission (verdict: Time Limit Exceeded):
N=input()
ls=[int(s) for s in input().split()]
ans=1
flag=1
for e in ls:
  ans*=e
if ans>10**18:
  print(-1)
else:
  print(ans)


Fixed submission:
N=input()
ls=[int(s) for s in input().split()]
ans=1
flag=1
for e in ls:
  ans*=e
  if ans>10**18:
    flag=0
    break
zeroflag=1
for e in ls:
  if e==0:
    zeroflag=0
if flag==1:
  print(ans)
else:
  print(-1*zeroflag)
Buggy python submission (verdict: Runtime Error):
a,b=[int(s) for s in input().split()]
print(int(a*b))

Fixed submission:
a,b=input().split()
a=int(a)
intb=int(b[0])
flob=int(b[2:])
ans=(a*100*intb+a*flob)//100
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ls=[int(s) for s in input().split()]
lsA=[i+ls[i] for i in range(N)]
lsB=[i-ls[i] for i in range(N)]
ans=0
for i in range(N):
  for j in range(i,N):
    if lsA[i]==lsB[j]:
      ans+=1
print(ans)
    

Fixed submission:
N=int(input())
ls=[int(s) for s in input().split()]
dicA={}
dicB={}
for i in range(N):
  a=i+ls[i]
  if a in dicA:
    dicA[a]+=1
  else:
    dicA[a]=1
  b=i-ls[i]
  if b in dicB:
    dicB[b]+=1
  else:
    dicB[b]=1
ans=0
for a,na in dicA.items():
  if a in dicB:
    ans+=na*dicB[a]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ls=[int(s) for s in input().split()]
ls2=[[i,ls[i]]for i in range(N)]
ls2=sorted(ls2,key=lambda x:-x[1])
ans=0
for a,b in ls2:
  M=2*b
  for i in range(max([0, a-M]),min([N,a+M])):
    if abs(i-a)==b+ls[i]:
      ans+=1
print(ans)

Fixed submission:
N=int(input())
ls=[int(s) for s in input().split()]
dicA={}
dicB={}
for i in range(N):
  a=i+ls[i]
  if a in dicA:
    dicA[a]+=1
  else:
    dicA[a]=1
  b=i-ls[i]
  if b in dicB:
    dicB[b]+=1
  else:
    dicB[b]=1
ans=0
for a,na in dicA.items():
  if a in dicB:
    ans+=na*dicB[a]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
ls=[int(s) for s in input().split()]
ans=0
for i in range(N):
  for j in range(i,N):
    if j-i==ls[i]+ls[j]:
      ans+=1
print(ans)

Fixed submission:
N=int(input())
ls=[int(s) for s in input().split()]
dicA={}
dicB={}
for i in range(N):
  a=i+ls[i]
  if a in dicA:
    dicA[a]+=1
  else:
    dicA[a]=1
  b=i-ls[i]
  if b in dicB:
    dicB[b]+=1
  else:
    dicB[b]=1
ans=0
for a,na in dicA.items():
  if a in dicB:
    ans+=na*dicB[a]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
A,B,N=[int(s) for s in input().split()]
x=B-1
ans=set()
while x<N:
  ans.add((A*x)//B-A*(x//B))
  x+=B
ans.add((A*N)//B-A*(N//B))
print(max(ans))
  

Fixed submission:
import time
start=time.time()
A,B,N=[int(s) for s in input().split()]
x=((N+1)//B)*B-1
ans=set()
ans.add((A*N)//B-A*(N//B))
while x>0:
  ans.add((A*x)//B-A*(x//B))
  x-=B
  if (time.time()-start)>1.7:
    break
print(max(ans))
Buggy python submission (verdict: Runtime Error):
N=int(input())
ans=0
for i in range(N+1):
  if i%3!=0 and a%5!=0:
    ans+=i
print(ans)

Fixed submission:
N=int(input())
ans=0
for i in range(N+1):
  if i%3!=0 and i%5!=0:
    ans+=i
print(ans)
Buggy python submission (verdict: Runtime Error):
N,K=[int(s) for s in input().split()]
ls=[-1 for _ in range(N+1)]
for _ in range(K):
  a,b=[int(s) for s in input().split()]
  if ls[a]==-1:
    ls[a]=b
  else:
    ls[0]=0
    
print(ls)

if ls[0]==0:
  print(-1)
else:
  if N==1:
    ans=max([ls[1],0])    
  if N==2:
    for i in range(10,100):
      a=i//10
      b=i%10
      if (a==ls[1] or ls[1]==-1) and (b==ls[2] or ls[2]==-1):
        ans=i
        break
  if N==3:
    for i in range(100,1000):
      a=i//100
      b=(i//10)%10
      c=i%10
      if (a==ls[1] or ls[1]==-1) and (b==ls[2] or ls[2]==-1) and (c==ls[3] or ls[3]==-1):
        ans=i
        break
print(ans)

Fixed submission:
N,K=[int(s) for s in input().split()]
ls=[-1 for _ in range(N+1)]
for _ in range(K):
  a,b=[int(s) for s in input().split()]
  if ls[a]==-1:
    ls[a]=b
  elif ls[a]==b:
    continue
  else:
    ls[0]=0
ans=0


if ls[0]==0:
  print(-1)
else:
  if N==1:
    ans=max([ls[1],0])    
  if N==2:
    for i in range(10,100):
      if ls[1]==0:
        ans=-1
      else:
        a=i//10
        b=i%10
        if (a==ls[1] or ls[1]==-1) and (b==ls[2] or ls[2]==-1):
          ans=i
          break
  if N==3:
    for i in range(100,1000):
      if ls[1]==0:
        ans=-1
      else:
        a=i//100
        b=(i//10)%10
        c=i%10
        if (a==ls[1] or ls[1]==-1) and (b==ls[2] or ls[2]==-1) and (c==ls[3] or ls[3]==-1):
          ans=i
          break
  print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=0
d=1
while d<=N:
  a+=d
  d*=2
print(ans)

Fixed submission:
N=int(input())
a=0
d=1
while d<=N:
  a+=d
  d*=2
print(a)
Buggy python submission (verdict: Runtime Error):
N,M=[int(s) for s in input().split()]
if N==M:
  print(Yes)
else:
  print(No)

Fixed submission:
N,M=[int(s) for s in input().split()]
if N==M:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
MOD=10**9+7
L=60
ls=[int(s) for s in input().split()]
bils=[]
for i in range(N):
  val_ls=[0 for j in range(L)]
  for j in range(L):
    if (2**j)&ls[i]>0:
      val_ls[j]=1
  bils.append(val_ls)
bisumls=[[0 for _ in range(L)] for _ in range(N)]
bisumls[N-1]=bils[N-1]
for i in range(2,N):
  for j in range(L):
    bisumls[-i][j]=bisumls[-i+1][j]+bils[-i][j]
#[[0, 0, 0], [3, 0, 2], [2, 0, 2], [2, 0, 1], [1, 0, 1]]
ans=0
ans_ls=[0 for _ in range(L)]
for i in range(N-1):
  #print(bils[i],bisumls[i+1])
  for k in range(L):
    if bils[i][k]==1:
      a=N-i-1-bisumls[i+1][k]
    else:
      a=bisumls[i+1][k]
   #   print(a)
    ans_ls[k]+=a
ans=0
base=1
for k in range(L):
  ans+=base*ans_ls[k]%MOD
  base=base*2%MOD
print(ans%MOD)
  

Fixed submission:
N=int(input())
MOD=10**9+7
L=60
ls=[int(s) for s in input().split()]
bi_ls=[0 for _ in range(L)]
for i in range(N):
  for j in range(L):
    if (2**j)&ls[i]>0:
      bi_ls[j]+=1    
ans=0
base=1
for j in range(L):
  ans=(ans+bi_ls[j]*(N-bi_ls[j])*base)%MOD
  base*=2%MOD
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
MOD=10**9+7
L=60
ls=[int(s) for s in input().split()]
bils=[]
for i in range(N):
  val_ls=[0 for j in range(L)]
  for j in range(L):
    if (2**j)&ls[i]>0:
      val_ls[j]=1
  bils.append(val_ls)
bisumls=[[0 for _ in range(L)] for _ in range(N)]
bisumls[N-1]=bils[N-1]
for i in range(2,N):
  for j in range(L):
    bisumls[-i][j]=bisumls[-i+1][j]+bils[-i][j]
#[[0, 0, 0], [3, 0, 2], [2, 0, 2], [2, 0, 1], [1, 0, 1]]
ans=0
for i in range(N-1):
  base=1
  #print(bils[i],bisumls[i+1])
  for k in range(L):
    if bils[i][k]==1:
      a=N-i-1-bisumls[i+1][k]
    else:
      a=bisumls[i+1][k]
   #   print(a)
    ans+=a*base
    base*=2
  #  print(ans,a,k)
  ans=ans%MOD
print(ans)
  

Fixed submission:
N=int(input())
MOD=10**9+7
L=60
ls=[int(s) for s in input().split()]
bi_ls=[0 for _ in range(L)]
for i in range(N):
  for j in range(L):
    if (2**j)&ls[i]>0:
      bi_ls[j]+=1    
ans=0
base=1
for j in range(L):
  ans=(ans+bi_ls[j]*(N-bi_ls[j])*base)%MOD
  base*=2%MOD
print(ans)
Buggy python submission (verdict: Runtime Error):
MOD=1000000007
N=int(input())
ls=[int(s) for s in input().split()]
RGB=[0,0,0]
ans=1
for i in range(N):
  x=RGB.count(ls[i])
  ans=(ans*x)%MOD
  y=RGB.index(ls[i])
  RGB[y]+=1
print(ans)

Fixed submission:
MOD=1000000007
N=int(input())
ls=[int(s) for s in input().split()]
RGB=[0,0,0]
ans=1
for i in range(N):
  if ls[i] in RGB:
    x=RGB.count(ls[i])
    ans=(ans*x)%MOD
    y=RGB.index(ls[i])
    RGB[y]+=1
  else:
    ans=0
    break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  a-=1
  b-=1
  edge[a].add((b,i))
  edge[b].add((a,i))

def color(set):
  c=1
  while True:
    if c in set:
      c+=1
    else:
      return(c)

#幅優先探索
ans=[0 for _ in range(N-1)]
colors=set()
vrt_color=[set() for _ in range(N)] #辺に塗った
stack=[(0,-1)]
while stack:
  vrt, _from =stack.pop(-1) #現在の場所と親
  for _to, e_i in edge[vrt]: #行き先と辺の番号
    if _to==_from:
      continue     #逆流防止
    x=color(vrt_color[vrt])
    ans[e_i]=x
    vrt_color[_to].add(x)
    vrt_color[vrt].add(x)
    colors.add(x)
    stack.append((_to,vrt))
print(len(colors))
for a in ans:
  print(a)
    
    

Fixed submission:
N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  a-=1
  b-=1
  edge[a].add((b,i))
  edge[b].add((a,i))

def color(set):
  val=len(set)+1
  if not(val in set):
    return(val)
  c=1
  while True:
    if c in set:
      c+=1
    else:
      return(c)

#幅優先探索
ans=[0 for _ in range(N-1)]
colors=set()
vrt_color=[set() for _ in range(N)] #辺に塗った
stack=[(0,-1)]
while stack:
  vrt, _from =stack.pop(-1) #現在の場所と親
  for _to, e_i in edge[vrt]: #行き先と辺の番号
    if _to==_from:
      continue     #逆流防止
    x=color(vrt_color[vrt])
    ans[e_i]=x
    vrt_color[_to].add(x)
    vrt_color[vrt].add(x)
    colors.add(x)
    stack.append((_to,vrt))
print(len(colors))
for a in ans:
  print(a)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  a-=1
  b-=1
  edge[a].add((b,i))
  edge[b].add((a,i))

def color(set):
  c=1
  while True:
    if c in set:
      c+=1
    else:
      return(c)

#幅優先探索
ans=[0 for _ in range(N-1)]
colors=set()
vrt_color=[set() for _ in range(N)] #辺に塗った
stack=[(0,-1)]
while stack:
  vrt, _from =stack.pop(-1) #現在の場所と親
  for _to, e_i in edge[vrt]: #行き先と辺の番号
    if _to==_from:
      continue     #逆流防止
    x=color(vrt_color[vrt])
    ans[e_i]=x
    vrt_color[_to].add(x)
    vrt_color[vrt].add(x)
    colors.add(x)
    stack.append((_to,vrt))
print(len(colors))
for a in ans:
  print(a)
    
    

Fixed submission:
N = int(input())
edge = [set() for i in range(N)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  a-=1
  b-=1
  edge[a].add((b,i))
  edge[b].add((a,i))

def color(set):
  val=len(set)+1
  if not(val in set):
    return(val)
  c=1
  while True:
    if c in set:
      c+=1
    else:
      return(c)

#幅優先探索
ans=[0 for _ in range(N-1)]
colors=set()
vrt_color=[set() for _ in range(N)] #辺に塗った
stack=[(0,-1)]
while stack:
  vrt, _from =stack.pop(-1) #現在の場所と親
  for _to, e_i in edge[vrt]: #行き先と辺の番号
    if _to==_from:
      continue     #逆流防止
    x=color(vrt_color[vrt])
    ans[e_i]=x
    vrt_color[_to].add(x)
    vrt_color[vrt].add(x)
    colors.add(x)
    stack.append((_to,vrt))
print(len(colors))
for a in ans:
  print(a)
Buggy python submission (verdict: Runtime Error):
H,W,K=[int(s) for s in input().split()]
ls=[input() for i in range(H)]
ans=[[] for i in range(H)]
num=1
s=[] ##イチゴがあるかないか
for i in range(H):
  if '#' in ls[i]:
    s.append(1)
    p=0
    for j in range(W):
      if ls[i][j]=='#':
        if p==0:
          p=1
        else:
          num+=1
      ans[i].append(num)
    num+=1
  else:
    s.append(0)
for i in range(H):
  if s[i]==0:
    for k in range(1,H):
      if s[i+k]==1:
        ans[i]=ans[i+k]
        break
for i in range(1,H):
  if s[-i]==0:
    for k in range(1,H):
      if s[-i-k]==1:
        ans[-i]=ans[-i-k]
        break
  else:
    break
for i in range(H):
  print(*ans[i])
  

Fixed submission:
H,W,K=[int(s) for s in input().split()]
ls=[input() for i in range(H)]
ans=[[] for i in range(H)]
num=1
s=[] ##イチゴがあるかないか
for i in range(H):
  if '#' in ls[i]:
    s.append(1)
    p=0
    for j in range(W):
      if ls[i][j]=='#':
        if p==0:
          p=1
        else:
          num+=1
      ans[i].append(num)
    num+=1
  else:
    s.append(0)
for i in range(H):
  if s[i]==0:
    for k in range(1,H):
      if i+k>=H: break
      if s[i+k]==1:
        ans[i]=ans[i+k]
        break
for i in range(1,H):
  if s[-i]==0:
    for k in range(1,H):
      if i+k>H: break
      if s[-i-k]==1:
        ans[-i]=ans[-i-k]
        break
  else:
    break
for i in range(H):
  print(*ans[i])