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

Fixed submission:
m,d=map(int,input().split())
if d>=m:
  print(m)
else:
  print(m-1)

Buggy submission (verdict: Runtime Error):
m,d=map(int,input())
if d>=m:
  print(m)
else:
  print(m-1)
Problem p03417 (python)

Fixed submission:
A, B = map(int, input().split())
if A==1 and B==1:
  print(1)
elif A==1:
  print(B-2)
elif B==1:
  print(A-2)
else:
  print((A-2)*(B-2))

Buggy submission (verdict: Runtime Error):
A, B = map(int, input().split())
if A==1 and B==1:
  print(1)
elif A==1:
  print(B-2)
elif B==!:
  print(A-2)
else:
  print((A-2)*(B-2))
Problem p03498 (python)

Fixed submission:
#!/usr/bin python3
# -*- coding: utf-8 -*-

n = int(input())
a = list(map(int, input().split()))
m = 0
for i, ai in enumerate(a):
    if abs(ai) >= m:
        m = abs(ai)
        mi = i
ret= [[mi+1, i+1] for i in range(n)]
if a[mi] >= 0:
    for i in range(n-1):
        ret.append([i+1, i+2])
else:
    for i in range(n-2, -1, -1):
        ret.append([i+2, i+1])  #i+1->i
print(2*n-1)
for x in ret:
    print(" ".join(map(str, x)))

Buggy submission (verdict: Runtime Error):
#!/usr/bin python3
# -*- coding: utf-8 -*-

n = int(input())
a = list(map(int, input().split()))

def check(l):
    ret = True
    for i in range(n-1):
        if a[i]>a[i+1]:
            ret = False
            break
    return ret

def solv(ret):
    print(len(ret))
    for i in ret:
        print("{} {}".format(*i))

if check(a):
    print(0); exit()

m = 0
for i, ai in enumerate(a):
    if abs(ai) > m:
        m = ai
        mi = i

ret = []
if m > 0:
    for i in range(n):
        ret.append([mi+1, i+1])
        a[i] += a[mi]
        if check(a):
            solv(ret)
            exit()
    for i in range(n-1):
        ret.append([i+1, i+2])
        a[i+1] += a[i]
        if check(a):
            solv(ret)
            exit()
else:
    for i in range(n):
        ret.append([mi+1, i+1])
        a[i] += a[mi]
        if check(a):
            solv(ret)
            exit()
    for i in range(n-1, -1, -1):
        ret.append([i+1, i+2])
        a[i+1] += a[i]
        if check(a):
            solv(ret)
            exit()
Problem p03534 (python)

Fixed submission:
S = input()
ca = S.count("a")
cb = S.count("b")
cc = S.count("c")
n = min(ca,cb,cc)
ca2 = ca - n
cb2 = cb - n
cc2 = cc - n
flg = [ca2,cb2,cc2]
flg.sort()
if flg in [[0,0,0],[0,0,1],[0,1,1]]:
  print("YES")
else:
  print("NO")

Buggy submission (verdict: Runtime Error):
S = input()
if len(S)<=2:
  print("YES")
else:
  ca = S.count("a")
  cb = S.count("b")
  cc = S.count("c")
  n = len(S)//3
  ca2 = ca - n
  cb2 = cb - n
  cc2 = cc - n
  flg = [ca2,cb2,cc2]
  if flg.count(0)==3:
    print("YES")
    print(flg2,n,flg)
  elif flg.count(1)==1 and flg.count(0)==2:
    print("YES")
  elif flg.count(1)==2 and flg.count(0)==1:
    print("YES")
  elif flg.count(2)==1 and flg.count(1)==2:
    print("YES")
  else:
    print("NO")
Problem p03555 (python)

Fixed submission:
a=input()
b=input()
ret='YES'
for i in range(3):
  if a[i]!=b[2-i]:
    ret='NO'
    break
print(ret)

Buggy submission (verdict: Runtime Error):
a=input()
b=input()
ret='YES'
for i in range(3):
  if a[i]!=b[2-i]
    ret='NO'
    break
print(ret)
Problem p03563 (python)

Fixed submission:
a=int(input())
m=int(input())
print(2*m-a)

Buggy submission (verdict: Runtime Error):
a,m=map(int,input().split())
print(2*m-a)
Problem p03592 (python)

Fixed submission:
N,M,K=map(int,input().split())
ret = 'No'
for m in range(M+1):
  a=K-m*N
  b=M-2*m
  if 0<=a and 0<b and a%b==0:
    n=a//b
    if 0<=n<=N:
      ret = 'Yes'
print(ret)

Buggy submission (verdict: Runtime Error):
N,M,K=map(int,input().split())
ret = 'No'
for m in range(M+1):
  a=K-m*N
  b=M-2*m
  if 0<=a and 0<=b and a%b==0:
    n=a//b
    if 0<=n<=N:
      ret = 'Yes'
print(ret)
Problem p03607 (python)

Fixed submission:
N=int(input())
A=[None]*N
for i in range(N):
  A[i]=input()
A.sort()
A.append('x')
cnt=0
c=A[0]
cc=1
for i in range(1,N+1):
  if A[i]==c:
    cc+=1
  else:
    cnt+=cc%2
    c=A[i]
    cc=1
print(cnt)

Buggy submission (verdict: Runtime Error):
N=int(input())
A=[None]*N
for i in range(N):
  A[i]=input()
A.sort()
cnt=0
i = 0
while i <N:
  if A[i]==A[i+1]:
    i+=2
  else:
    cnt+=1
    i+=1
print(cnt)
Problem p03612 (python)

Fixed submission:
N=int(input())
P=list(map(int,input().split()))
ans = 0
for i in range(1,N+1):
  if P[i-1]==i and i!=N:
    P[i-1],P[i]=P[i],P[i-1]
    ans += 1
  elif P[i-1]==i and i==N:
    ans += 1
print(ans)

Buggy submission (verdict: Runtime Error):
N=int(input())
P=list(map(int,input().split()))
ans = 0
for i in range(1,N+1):
  if P[i-1]==i:
    P[i-1],P[i]=P[i],P[i-1]
    ans += 1
print(ans)
Problem p03624 (python)

Fixed submission:
S = list(set(list(input())))
S.sort()
al = 'abcdefghijklmnopqrstuvwxyz'
if len(S)==26:
  ans = 'None'
else:
  for i in range(len(S)):
    if al[i] != S[i]:
      ans = al[i]
      break
    else:
      ans = al[len(S)]
print(ans)

Buggy submission (verdict: Runtime Error):
S = list(set(list(input())))
S.sort()
al = 'abcdefghijklmnopqrstuvwxyz'
if len(S)==26:
  ans = 'None'
else:
  for i in range(len(al)):
    if al[i] != S[i]:
      ans = al[i]
      break
print(ans)

Buggy submission (verdict: Runtime Error):
S = list(set(list(input())))
S.sort()
al = 'abcdefghijklmnopqrstuvwxyz'
for i in range(len(al)):
  if al[i] != S[i]:
    ans = al[i]
    break
if len(S)==26:
  ans = 'None'
print(ans)
Problem p03633 (python)

Fixed submission:
#####################
#複数の最小公倍数lcm
#####################
from fractions import gcd
def Lcm(list):
  L = 1
  for a in list:
    L = (a // gcd(a, L))*L
  return L
n= int(input())
A = [int(input()) for i in range(n)]
print(Lcm(A))

Buggy submission (verdict: Runtime Error):
from math import gcd
from math import reduce
from fractions import gcd
from functools import reduce
def Gcd(list):
    gcd = 1
    G = reduce(gcd, list)
    return G

A = [2,6,8]
print(Gcd(A))

Buggy submission (verdict: Runtime Error):
#####################
#複数の最小公倍数lcm
#####################
from fractions import gcd
def Lcm(list):
  for a in list:
    L = (a // gcd(a, L))*L
  return L
n= int(input())
A = [int(input()) for i in range(n)]
# A = [2,6,8]
print(Lcm(A))
Problem p03671 (python)

Fixed submission:
a = map(int,input().split())
print(sum((sorted(a))[0:2]))

Buggy submission (verdict: Runtime Error):
a = map(int,input(),split())
print((sorted(a))[0:2])

Buggy submission (verdict: Runtime Error):
a = map(int,input(),split())
print((a.sort())[0:2])
Problem p03760 (python)

Fixed submission:
o = input()
e = input()
if len(o)-len(e)==1:
  x = o[-1]
else:
  x = ''
ans = ''
for i in range(len(e)):
  ans += o[i] + e[i]
ans += x
print(ans)

Buggy submission (verdict: Runtime Error):
o = int(input())
e = int(input())
if len(o)-len(e)==1:
  x = o[-1]
else:
  x = ''
ans = ''
for i in range(len(e)):
  ans += o[i] + e[i]
ans += x
print(ans)
Problem p03777 (python)

Fixed submission:
a,b = input().split()
if a == "H":
  print(b)
elif b == "H":
  print("D")
else:
  print("H")

Buggy submission (verdict: Runtime Error):
a,b = input().split()
if a = "H":
  print(b)
elif b = "H":
  print("D")
else:
  print("H")
Problem p03779 (python)

Fixed submission:
X=int(input())
s=0
for t in range(X+1):
  s+=t
  if s>=X:
    print(t)
    break

Buggy submission (verdict: Runtime Error):
X=int(input())
import numpy as np
dp = np.zeros(X+1, dtype = int) #xに到達できる判定
dp[0] = 1
for t in range(1,X+1):
    if dp[X-t]==1:
        print(t)
        break
    else:
        dp[t:] = dp[:X+1-t]

Buggy submission (verdict: Runtime Error):
X=int(input())
import numpy as np
dp = np.zeros(X+1, dtype = int) #xに到達できる判定
dp[0] = 1
for t in range(1,X+1):
    if dp[X-t]==1:
        print(t)
        break
    else:
        dp[t:] = dp[:X+1-t]
    print(dp)

Buggy submission (verdict: Runtime Error):
X=int(input())
import numpy as np
dp=[[False]*(X+1) for _ in range(X+1)]
dp[0][0]=True
for t in range(1,X+1):
  if dp[t-1][X-t]==True:
    ans = t
    break
  for x in range(0,X+1):
    if x>=t:
      dp[t][x]=dp[t-1][x-t]
    else:
      dp[t][x]=dp[t-1][x]
print(ans)
Problem p03814 (python)

Fixed submission:
s=input()
st=s.index('A')
t=s[::-1]
en=t.index('Z')
print(len(s)-st-en)

Buggy submission (verdict: Runtime Error):
s=input()
st=s.index('A')
t=s
t.reverse()
en=t.index('Z')
print(len(s)-st-en)
Problem p03827 (python)

Fixed submission:
n=int(input())
s=list(input())
nw = 0
ans = 0
for i in s:
  if i=='I':
    nw+=1
  else:
    nw-=1
  ans = max(ans,nw)
print(ans)

Buggy submission (verdict: Runtime Error):
n=int(input())
s=list(input())
nw = 0
ans = 0
for i in s:
  if i='I':
    nw+=1
  else:
    nw-=1
  ans = max(ans,nw)
print(ans)
Problem p03828 (python)

Fixed submission:
n=int(input())
def factorization(n):
  primen = []
  degree = []
  primend = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      primen.append(i)
      degree.append(cnt)
      primend.append([i,cnt])
  if temp!=1:
    primen.append(temp)
    degree.append(1)
    primend.append([temp,1])
  if primen==[]:
    primen.append(n)
    degree.append(1)
    primend.append([n,1])
  return primend#primen,degree
pn=[0]*(n+1)
for i in range(1,n+1):
  for j in factorization(i):
    pn[j[0]]+=j[1]
ans = 1
for k in range(2,n+1):
  ans*=(pn[k]+1)%(10**9+7)
print(ans%(10**9+7))

Buggy submission (verdict: Runtime Error):
n=int(input())
def factorization(n):
  primend = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      primend.append([i,cnt])
  if temp!=1:
    primend.append([temp,1])
  if primen==[]:
    primend.append([n,1])
  return primend#primen,degree
pn=[0]*(n+1)
for i in range(1,n+1):
  for j in factorization(i):
    pn[j[0]]+=j[1]
ans = 1
for k in range(2,n+1):
  ans*=(pn[k]+1)%(10**9+7)
print(ans%(10**9+7))

Buggy submission (verdict: Runtime Error):
n=int(input())
def factorization(n):
  primend = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      primend.append([i,cnt])
  if temp!=1:
    primend.append([temp,1])
  if primen==[]:
    primend.append([n,1])
  return primend#primen,degree
pn=[0]*(n+1)
for i in range(1,n+1):
  for j in factorization(i):
    pn[j[0]]+=j[1]
ans = 1
for k in range(2,n+1):
  ans*=(pn[k]+1)%(10**9+7)
print(ans%(10**9+7))

Buggy submission (verdict: Runtime Error):
n=int(input())
def factorization(n):
  primen = []
  degree = []
  primend = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0:
        cnt+=1
        temp //= i
      primen.append(i)
      degree.append(cnt)
      primend.append([i,cnt])
  if temp!=1:
    primen.append(temp)
    degree.append(1)
    primend.append([temp,1])
  if primen==[]:
    primen.append(n)
    degree.append(1)
    primend.append([n,1])
  return primend#primen,degree
pn=[0]*(n+1)
for i in range(1,n+1):
  for j in factorization(i):
    pn[j[0]]+=j[1]
ans = 1
for k in range(2,n+1):
  ans*=(pn[k]+1)%(10**9+7)
print(pn%(10**9+7))
Problem p03845 (python)

Fixed submission:
N=int(input())
T=list(map(int,input().split()))
M=int(input())
Ans=sum(T)
for i in range(M):
  p,x=map(int,input().split())
  xx=Ans+x-T[p-1]
  print(xx)

Buggy submission (verdict: Runtime Error):
N=int(input())
T=list(map(int,input().split())
M=int(input())
Ans=sum(T)
for i in range(M):
  p,x=map(int,input().split())
  xx=Ans+x-T[p-1]
  print(x)

Buggy submission (verdict: Runtime Error):
N=int(input())
T=list(map(int,input().split())
M=int(input())
Ans=sum(T)
for i in range(M):
  p,x=map(int,input().split()))
  xx=Ans+x-T[p-1]
  print(x)
Problem p03952 (python)

Fixed submission:
n, x = map(int, input().split())
if 2<=x<=2*(n-1):
  print('Yes')
else:
  print('No')
  exit()
  
if x == n:
  for i in range(1, 2*n):
    print(i)
elif x < n:
  for i in range(n, x, -1):
    print(i)
  for i in range(1, x+1):
    print(i)
  for i in range(n+1, 2*n):
    print(i)
else:
  for i in range(1, n):
    print(i)
  for i in range(x, 2*n):
    print(i)
  for i in range(x-1, n-1, -1):
    print(i)

Buggy submission (verdict: Runtime Error):
n, x = map(int, input().split())
if abs(n-x)<=1 :
  print('Yes')
else:
  print('No')
  exit()
if n == x:
  for i in range(2*(n-1)):
    print(i+1)
elif x == n-1:
  print(n)
  for i in range(2*(n-1)):
    if i != n:
      print(i)
else x == n-1:
  for i in range(2*(n-1)):
    if i != n:
      print(i)
  print(n)
Problem p03963 (python)

Fixed submission:
n,k=map(int,input().split())
def pt(n,k):
  if n==1:
    return k
  else:
    return pt(n-1,k)*(k-1)
print(k*((k-1)**(n-1)))

Buggy submission (verdict: Runtime Error):
n,k=map(int,input().split())
def pt(n,k):
  if n==1:
    return k
  else:
    return pt(n-1,k)*(k-1)
print(pt(n,k))
Problem p03971 (python)

Fixed submission:
n,a,b=map(int,input().split())
cab,cb=0,0
S=input()
for i in range(n):
  s=S[i]
  if s=='c':
    print('No')
  if s=='a':
    if cab<a+b:
      print('Yes')
      cab+=1
    else:
      print('No')
  if s=='b':
    if cab<a+b and cb<b:
      print('Yes')
      cab+=1
      cb+=1
    else:
      print('No')

Buggy submission (verdict: Runtime Error):
n,a,b=map(int,input().split())
cab,cb=0,0
for i in range(n):
  s=input()
  if s=='c':
    print('No')
  if s=='a':
    if cab<a+b:
      print('Yes')
      cab+=1
    else:
      print('No')
  if s=='b':
    if cab<a+b and cb<b:
      print('Yes')
      cab+=1
      cb+=1
    else:
      print('No')
Problem p04033 (python)

Fixed submission:
a,b=map(int,input().split())
a=min(1,a)
b=min(1,b)
if b==1 and a<=0:
  print('Zero')
elif b==0:
  print('Zero')
elif (b-a)%2==0 and b<0:
  print("Negative")
else:
  print("Positive")

Buggy submission (verdict: Runtime Error):
a,b=map(int,input().split())
a=min(1,a)
b=min(1,b)
z=aa.count(0)
if b==1 and a<=0:
  print('Zero')
elif b==0:
  print('Zero')
elif (b-a)%2==0 and b<0:
  print("Negative")
else:
  print("Positive")

Buggy submission (verdict: Runtime Error):
a,b=map(int,input().split())
aa=[a,b]
if a<b:
  aa+=list(range(a+1,b))
z=aa.count(0)
n=sum([1 for i in aa if i<0])%2
if z>0:
  print('Zero')
elif n==0:
  print("Positive")
else:
  print("Negative")

Buggy submission (verdict: Runtime Error):
a=list(map(int,input().split()))
aa=list(range(a[0],a[1]+1))
z=aa.count(0)
n=sum([1 for i in aa if i<0])%2
if z>0:
  print('Zero')
elif n==0:
  print("Positive")
else:
  print("Negative")
Problem p04043 (python)

Fixed submission:
X=list(map(int,input().split()))
X.sort()
if X==[5,5,7]:
  print('YES')
else:
  print('NO')

Buggy submission (verdict: Runtime Error):
X=map(int,input().split())
X.sort()
if X==[5,5,7]:
  print('YES')
else:
  print('NO')
Problem p02585 (python)

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

def func(x):
    return x - 1
def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        while True:
            x = P[x]
            S.append(C[x])
            tot += C[x]
            if x == si:
                break
        l = len(S)
        t = 0
        for i in range(l):
            t += S[i]
            if i + 1 > K:
                break
            now = t
            if tot > 0:
                e = (K-(i+1)) // l
                now += tot*e
            ans = max(ans, now)

    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000000)


def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        while True:
            x = P[x]
            S.append(C[x])
            tot += C[x]
            if x == si:
                break
        l = len(S)
        t = 0
        for i in range(l):
            t += S[i]
            if i + 1 > K:
                break
            now = t
            if tot > 0:
                e = (K-(i+1)) // l
                now += tot*e
            ans = max(ans, now)

    print(ans)


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N, K = map(int, input().split())
    P = list(map(func,map(int, input().split())))
    C = list(map(int, input().split()))
    ans = -float('inf')
    for si in range(N):
        x = si
        tot = 0
        S = []
        while True:
            x = P[x]
            S.append(C[x])
            tot += C[x]
            if x == si:
                break
        l = len(S)
        t = 0
        for i in range(l):
            t += S[i]
            if i + 1 > K:
                break
            now = t
            if tot > 0:
                e = (K-(i+1)) // l
                now += tot*e
            ans = max(ans, now)

    print(ans)


if __name__ == "__main__":
    main()
Problem p02609 (python)

Fixed submission:
import sys
from functools import lru_cache
 
sys.setrecursionlimit(4100000)
 
@lru_cache(maxsize=None)
def f(n):
    if n == 0:
        return 0

    return f(n % bin(n).count('1')) + 1

def main():
    N = int(input())
    X = list(input())
    pc = X.count('1')
    now = 0
    for i in range(N):
        if X[i] == '1':
            now += pow(2,N-i-1)

    ac = pc + 1
    dc = pc - 1
    ac_now = now % ac
    if dc:
        dc_now = now % dc
    for i in range(N):
        cnt = 0
        if X[i] == '1' and dc:
            tmp = (dc_now - pow(2, N-i-1, dc)) % dc
            cnt = 1 + f(tmp)
        elif X[i] == '0':
            tmp = (ac_now + pow(2, N-i-1, ac)) % ac
            cnt = 1 + f(tmp)

        print(cnt)



if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)

@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    
    mod = x % (bin(x).count('1'))
    return f(mod) + 1


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    pc = X.count('1')
    Y = list(X)
    ans = [0] * N
    pre = 1
    for i in range(N-1,-1,-1):
        if Y[i] == '1':
            tmp = (O - pre) % (pc - 1)
        else:
            tmp = (O + pre) % (pc + 1)
        ans[i] = f(tmp) + 1
        pre *= 2

    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
import sys
from functools import lru_cache

sys.setrecursionlimit(4100000)
d = defaultdict(int)

@lru_cache(maxsize=None)
def count_ones_by_shift(num):
    num = (num & 0x55555555) + ((num & 0xAAAAAAAA) >> 1) 
    num = (num & 0x33333333) + ((num & 0xCCCCCCCC) >> 2)
    num = (num & 0x0F0F0F0F) + ((num & 0xF0F0F0F0) >> 4)
    num = (num & 0x00FF00FF) + ((num & 0xFF00FF00) >> 8)
    num = (num & 0x0000FFFF) + ((num & 0xFFFF0000) >> 16)
    return num

@lru_cache(maxsize=None)
def f(x):
    if d[x]:
        return d[x]
    
    if x % count_ones_by_shift(x) == 0:
        d[x] = 1
        return 1

    d[x] = f(x % count_ones_by_shift(x)) + 1

    return d[x]


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    Y = list(X)
    for i in range(N):
        tmp = 0
        if Y[i] == '1':
            tmp = O - 2 ** (N - 1 - i)
        else:
            tmp = O + 2 ** (N - 1 - i)
        print(f(tmp))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

d = defaultdict(int)

def f(x):
    if x % (bin(x).count('1')) == 0:
        d[x] = 1
        return 1

    if d[x]:
        return d[x]
    
    d[x] = f(x % (bin(x).count('1'))) + 1

    return d[x]


def main():
    N = int(input())
    X = input()
    O = int(X, 2)
    Y = list(X)
    for i in range(N):
        tmp = 0
        if Y[i] == '1':
            tmp = O - 2 ** (N - 1 - i)
        else:
            tmp = O + 2 ** (N - 1 - i)
        print(f(tmp))




if __name__ == "__main__":
    main()
Problem p02698 (python)

Fixed submission:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

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

N = int(input())
A = list(map(int, input().split()))
dp = [float('inf')] * (N + 1)
ans = [0] * N

def dfs(s,edge):
    global ans, dp
    index = bisect.bisect_left(dp[s], A[s])
    old = dp[index]
    length = bisect.bisect_left(dp[s], float('inf'))
    ans[index] = length
    for i in edge[s]:
        if i == s:
            continue
        dfs(i,edge)
    dp[index] = old

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    dfs(0,edge)
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()