Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

d=sorted(d,key=lambda x:x[0])
dp=[-1]*(3000*2+5)
dp[0]=0
for i in range(len(d)):
  for j in range(T-1,-1,-1):
    if dp[j]!=-1:
      if dp[j]+d[i][1]>dp[j+d[i][0]]:
        dp[j+d[i][0]]=dp[j]+d[i][1]
      
print(max(dp))

Fixed submission:
N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

import numpy as np
d=sorted(d,key=lambda x:x[0])
dp=np.zeros(T,dtype=int)
ans=0
for i in range(len(d)):
  t=d[i][0]
  v=d[i][1]
  ans=max(ans,dp.max()+v)
  np.maximum(dp[:-t]+v,dp[t:],out=dp[t:])

print(ans)

Buggy python submission (verdict: Runtime Error):
N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

d=sorted(d,key=lambda x:x[a])
dp=[-1]*(3000*2+5)
dp[0]=0
for i in range(len(d)):
  for j in range(T-1,-1,-1):
    if dp[j]!=-1:
      if dp[j]+d[i][1]>dp[j+d[i][0]]:
        dp[j+d[i][0]]=dp[j]+d[i][1]
      
print(max(dp))

Fixed submission:
N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

import numpy as np
d=sorted(d,key=lambda x:x[0])
dp=np.zeros(T,dtype=int)
ans=0
for i in range(len(d)):
  t=d[i][0]
  v=d[i][1]
  ans=max(ans,dp.max()+v)
  np.maximum(dp[:-t]+v,dp[t:],out=dp[t:])

print(ans)

Buggy python submission (verdict: Runtime Error):
N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

dp=[-1]*(30*2)
dp[0]=0
for i in range(len(d)):
  for j in range(T,-1,-1):
    if dp[j]!=-1:
      if dp[j]+d[i][1]>dp[j+d[i][0]]:
        dp[j+d[i][0]]=dp[j]+d[i][1]
      
print(max(dp))

Fixed submission:
N,T=map(int,input().split())
d=[None]*N
for i in range(N):
  a,b=map(int,input().split())
  d[i]=[a,b]

import numpy as np
d=sorted(d,key=lambda x:x[0])
dp=np.zeros(T,dtype=int)
ans=0
for i in range(len(d)):
  t=d[i][0]
  v=d[i][1]
  ans=max(ans,dp.max()+v)
  np.maximum(dp[:-t]+v,dp[t:],out=dp[t:])

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

ans=False
for i in range(9):
  for j in range(9):
    if i*j==N:
      ans=True
      break
print(("No","Yes")[ans])

Fixed submission:
N=int(input())

ans=False
for i in range(1,10):
  for j in range(1,10):
    if i*j==N:
      ans=True
      break
print(("No","Yes")[ans])
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N=int(input())
data=prime_factorize(N)

ans=10**12
for i in range((len(data))//2+1):
  for subset in itertools.permutations(data, i):
    a=1
    for e in subset:
      a*=e
    b=N//a
    ans=min(ans,a+b)
print(ans-2)


Fixed submission:
N=int(input())
import math
SQ=int(math.sqrt(N))
minval=10**12
a=1
b=1
for i in range(1,SQ+1):
  if N%i==0:
    newa=i
    newb=N//i
    if abs(newa-newb) < minval:
      minval=abs(newa-newb)
      a=newa
      b=newb

print(a+b-2)

Buggy python submission (verdict: Runtime Error):
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N=int(input())
datas=prime_factorize(N)
a=1
b=1
for i in range(len(data)):
  if a<b:
    a+=data[i]
  else:
    b+=data[i]

print(max(1,a-1)+max(1,b-1))



Fixed submission:
N=int(input())
import math
SQ=int(math.sqrt(N))
minval=10**12
a=1
b=1
for i in range(1,SQ+1):
  if N%i==0:
    newa=i
    newb=N//i
    if abs(newa-newb) < minval:
      minval=abs(newa-newb)
      a=newa
      b=newb

print(a+b-2)
Buggy python submission (verdict: Runtime Error):
import math
a,b,x=map(int,input().split())

bottle=(a**2)*b

if x <= bottle/2:
  # 半分以上傾ける場合
  soko=(x*2/b)/a
  
  #bに対してtangent(r)がsokoとなるrを求める
  r=90-(math.degrees(math.atan(soko/b)))
  
else:
  # 半分傾けられない場合
  takasa=((a**2)*b-x)*2/(a**2)
  
  #takasaに対してtangent(r)がaとなるrを求める
  r=90-(math.degrees(math.atan(a/takasa)))

print(r)

Fixed submission:
import math
a,b,x=map(int,input().split())

bottle=(a**2)*b

if x <= bottle/2:
  # 半分以上傾ける場合
  soko=(x*2/b)/a
  
  #bに対してtangent(r)がsokoとなるrを求める
  r=90-(math.degrees(math.atan(soko/b)))
  
else:
  # 半分傾けられない場合
  takasa=((a**2)*b-x)*2/(a**2)
  
  #takasaに対してtangent(r)がaとなるrを求める
  if takasa==0:
    r=0
  else:
      r=90-(math.degrees(math.atan(a/takasa)))

print(r)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

import numpy as np

N,K = map(int,readline().split())
A = np.array(sorted(list(map(int,readline().split()))))
F = np.array(sorted(list(map(int,readline().split())),reverse = True))

ok = A[-1] * F[0]
ng = -1

def isOk(x):
  # 時間がxになるためには、A_iをx/F_i以下まで減らす必要がある
  diff = A - x // F
  return sum(np.where(diff > 0, diff, 0)) <= K
  
while (ok - ng)>1:
  mid = (ok + ng) // 2
  if isOk(mid):
    ok = mid
  else:
    ng = mid
print(ok)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))

a=sorted(a)[::-1]
f=sorted(f)

ok=10**18
ng=-1

import math
def isOK(val,arr,farr,k):
  s=0
  for i in range(len(arr)):
    s+=max(math.ceil(a[i]-val/f[i]),0)
  return s<=k
  
while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOK(mid,a,f,k):
    ok=mid
  else:
    ng=mid
    
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
A = sorted(list(map(int,readline().split())))
F = sorted(list(map(int,readline().split())),reverse = True)

ok = A[-1] * F[0]
ng = -1

def isOk(x):
  # 時間がxになるためには、A_iをx/F_i以下まで減らす必要がある
  diff = 0
  for i in range(len(A)):
    diff += max(A[i] - x // F[i], 0)
  return diff <= K
  
while (ok - ng)>1:
  mid = (ok + ng) // 2
  if isOk(mid):
    ok = mid
  else:
    ng = mid
print(ok)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))

a=sorted(a)[::-1]
f=sorted(f)

ok=10**18
ng=-1

import math
def isOK(val,arr,farr,k):
  s=0
  for i in range(len(arr)):
    s+=max(math.ceil(a[i]-val/f[i]),0)
  return s<=k
  
while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOK(mid,a,f,k):
    ok=mid
  else:
    ng=mid
    
print(ok)

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

a=sorted(a)[::-1]
f=sorted(f)

ok=10**18
ng=-1

import math
def isOK(val,arr,farr,k):
  s=0
  for i in range(len(arr)):
    s+=max(math.ceil(a[i]-val/f[i]),0)
  return s<=k
  
while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOK(mid,a,f,k):
    ok=mid
  else:
    ng=mid
    
print(ok)

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))

a=sorted(a)[::-1]
f=sorted(f)

ok=10**18
ng=-1

import math
def isOK(val,arr,farr,k):
  s=0
  for i in range(len(arr)):
    s+=max(math.ceil(a[i]-val/f[i]),0)
  return s<=k
  
while abs(ok-ng)>1:
  mid=abs(ok+ng)//2
  if isOK(mid,a,f,k):
    ok=mid
  else:
    ng=mid
    
print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N = int(readline())
L = list(map(int,readline().split()))
L = sorted(L)

# 2本固定すると、もう一本として選べるのは、2本の和より長いものだけ
# これを二分探索で数える

#print(L)
import bisect
ans = 0
for i in range(N - 1):
  for j in range(i + 1,N):
    limit = L[i] + L[j]
    ng = len(L)
    ok = j
    while abs(ok - ng) > 1:
      mid = abs(ok + ng) // 2
      if L[mid] < limit:
        ok = mid
      else:
        ng = mid
#    print("i",i,"j",j,"L[i]",L[i],"L[j]",L[j],"limit",limit,ok - j)
    ans += ok - j
        
print(ans)

Fixed submission:
import bisect
N=int(input())
L=sorted(list(map(int,input().split())))

ans=0
for i in range(N):
  for j in range(i+1,N):
    ans+=bisect.bisect_left(L,L[i]+L[j])-j-1

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

a=sorted(a)
if n==1:
  for i in range(m):
    a[0]=a[0]//2
else:
  for i in range(m):
    if a[n-2]>a[n-1]:
      a=sorted(a)
    a[n-1]=a[n-1]//2

ans=sum(a)
  
print(ans)

Fixed submission:
import heapq	

n,m=map(int,input().split())
a=list(map(int,input().split()))
hq=[]
for i in range(len(a)):
  heapq.heappush(hq,-a[i])

if n==1:
  for i in range(m):
    hq[0]=(((-1)*hq[0])//2)*(-1)
else:
  for i in range(m):
    v=heapq.heappop(hq)
    heapq.heappush(hq,((v*-1)//2)*(-1))

ans=0
for i in range(len(hq)):
  ans=ans+(-1)*heapq.heappop(hq)

print(ans)

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

a=sorted(a)
if n==1:
  for i in range(m):
    a[0]=a[0]/2
else:
  for i in range(m):
    if a[n-2]>a[n-1]:
      a=sorted(a)
    a[n-1]=a[n-1]/2

ans=0
for j in range(n):
  ans=ans+int(a[j])
  
print(ans)

Fixed submission:
import heapq	

n,m=map(int,input().split())
a=list(map(int,input().split()))
hq=[]
for i in range(len(a)):
  heapq.heappush(hq,-a[i])

if n==1:
  for i in range(m):
    hq[0]=(((-1)*hq[0])//2)*(-1)
else:
  for i in range(m):
    v=heapq.heappop(hq)
    heapq.heappush(hq,((v*-1)//2)*(-1))

ans=0
for i in range(len(hq)):
  ans=ans+(-1)*heapq.heappop(hq)

print(ans)

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

for i in range(m):
  a=sorted(a)
  a[n-1]=a[n-1]/2
  
ans=0
for j in range(n):
  ans=ans+int(a[j])
  
print(ans)

Fixed submission:
import heapq	

n,m=map(int,input().split())
a=list(map(int,input().split()))
hq=[]
for i in range(len(a)):
  heapq.heappush(hq,-a[i])

if n==1:
  for i in range(m):
    hq[0]=(((-1)*hq[0])//2)*(-1)
else:
  for i in range(m):
    v=heapq.heappop(hq)
    heapq.heappush(hq,((v*-1)//2)*(-1))

ans=0
for i in range(len(hq)):
  ans=ans+(-1)*heapq.heappop(hq)

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

S = readline().rstrip()
T = readline().rstrip()

if len(set(T) - set(S)) > 0:
  print(-1)
  exit(0)
  
import bisect
# Tの各文字を探す
S2 = S * 2
from collections import defaultdict
# ある文字が何文字目にあるか辞書
dic = defaultdict(list)

for i in range(len(S2)):
  dic[S2[i]] += [i]

ind = -1
ans = 0
for t in T:
  # 探す文字はt
  targets = dic[t]
#  print("targets",targets,"t",t,"ind + 1",ind + 1)
  newind = targets[bisect.bisect_left(targets, ind + 1)]
#  print("t",t,"S2",S2,"newind",newind)
  ans += (newind - ind)
  if newind > len(S):
    newind -= len(S)
  ind = newind

print(ans)

  
  

Fixed submission:
s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
  exit(0)

ss=s*2
ind=-1
turn=0
for c in t:
  nex=ss[ind+1:].find(c)
  ind=(ind+1)+nex
  if ind>=len(s):
    ind-=len(s)
    turn+=1

print(turn*len(s)+ind+1)

Buggy python submission (verdict: Runtime Error):
s=input()
t=input()

if len(set(t)-set(s))>0:
  print(-1)
else:
  s2=s*2
  s2pos={}
  for i in range(len(s2)):
    if s2[i] in s2pos:
      s2pos[s2[i]].append(i)
    else:
      s2pos[s2[i]]=[i]

  cur=-1
  import bisect
  rev=0
  for c in t:
    cur+=1
    pos=s2pos[c]
    p=bisect.bisect_left(pos,cur)
    cur=pos[p]
    if cur>len(s):
      cur-=len(s)
      rev+=1
    if rev>=100:
      print(-1)
      break
  else:
    print(rev*len(s)+cur+1)

Fixed submission:
s=input()
t=input()
if len(set(t)-set(s))>0:
  print(-1)
  exit(0)

ss=s*2
ind=-1
turn=0
for c in t:
  nex=ss[ind+1:].find(c)
  ind=(ind+1)+nex
  if ind>=len(s):
    ind-=len(s)
    turn+=1

print(turn*len(s)+ind+1)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
cur=""
i=0
ans=0
while i<len(s):
  for j in range(i+1,len(s)):
    if s[i:j]!=cur:
      if s[i:j]==s[j:]:
        continue
      cur=s[i:j]
      i=j
      ans+=1
print(ans)


Fixed submission:
S=input()
dp=[[0 for i in range(2)] for j in range(len(S))]
# dp[x]:x番目の文字に、dp[x][0]:1文字で来たときの最大分割数、dp[x][1]:2文字で来た時
dp[0][0]=1
dp[0][1]=-1
for i in range(1,len(S)):
  if S[i]==S[i-1]:
    dp[i][0]=dp[i-1][1]+1
  elif S[i]!=S[i-1]:
    dp[i][0]=max(dp[i-1][0],dp[i-1][1])+1
  if i-2>=0:
    dp[i][1]=max(dp[i-2][0],dp[i-2][1])+1
print(max(dp[-1][0],dp[-1][1]))

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
seen=set()
i=0
ans=0
while i<len(s):
  for j in range(i+1,len(s)):
    if s[i:j] not in seen:
      if s[j:] in seen:
        continue
      seen.add(s[i:j])
      i=j
      ans+=1
print(ans)
      

Fixed submission:
S=input()
dp=[[0 for i in range(2)] for j in range(len(S))]
# dp[x]:x番目の文字に、dp[x][0]:1文字で来たときの最大分割数、dp[x][1]:2文字で来た時
dp[0][0]=1
dp[0][1]=-1
for i in range(1,len(S)):
  if S[i]==S[i-1]:
    dp[i][0]=dp[i-1][1]+1
  elif S[i]!=S[i-1]:
    dp[i][0]=max(dp[i-1][0],dp[i-1][1])+1
  if i-2>=0:
    dp[i][1]=max(dp[i-2][0],dp[i-2][1])+1
print(max(dp[-1][0],dp[-1][1]))
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=[None]*n
for i in range(n):
  s[i]=sorted(input())
import collections
c=collections.Counter(s)
ans=0
for v in c.valeus():
  ans+=(v*(v-1))//2
print(ans)
  

Fixed submission:
n=int(input())
s=[None]*n
for i in range(n):
  s[i]="".join(sorted(input()))

s=sorted(s)

total=0
count=1
for j in range(1,n):
  if s[j]==s[j-1]:
    count = count+1
  else:
    if count>1:
      total = total+(count*(count-1))//2
    count=1

if count>1:
  total = total+(count*(count-1))//2

print(total)
Buggy python submission (verdict: Time Limit Exceeded):
# x*y == S
# を満たすx,yがあれば答えは0,0,x,0,0,y

S=int(input())
for i in range(int(S**0.5),S+1):
  if S%i>0:
    continue
  if S//i<10**9+1:
    print(0,0,i,0,0,S//i)
    break

Fixed submission:
# (0,0),(a,b),(c,d)
# (10**9, 1)(x,y)
# 10**9 * y - x == S
# S = 10**9 * a + bとおくと
# y = a + 1
# x = 10**9- b

S=int(input())
if S==10**18:
  print(0,0,10**9,0,0,10**9)
  exit(0)
DIV=10**9
a = S//DIV
b = S%DIV
x = 10**9-b
y = a + 1
if x>10**9:
  print(x)
if y>10**9:
  print(y)
print(0,0,10**9,1,x,y)

Buggy python submission (verdict: Time Limit Exceeded):
# x1,x2=(0,0)とする
# x2*y3 - x3*y2 == S
# を満たす(x2,y2),(x3,y3)を求める

S=int(input())
# x3,y2のペアで探索してみよう
for x3 in range(1,10**9):
  for y2 in range(1,10**9):
    rest=x3*y2+S
    # restを構成する10**9以下の数値のペアが作れるか
    for x2 in range(1,int((10**9)**0.5)+1):
      if rest%x2==0:
        y3=rest//x2
        if y3>10**9:
          continue
        print(0,0,x2,y2,x3,y3)
        exit(0)

Fixed submission:
# (0,0),(a,b),(c,d)
# (10**9, 1)(x,y)
# 10**9 * y - x == S
# S = 10**9 * a + bとおくと
# y = a + 1
# x = 10**9- b

S=int(input())
if S==10**18:
  print(0,0,10**9,0,0,10**9)
  exit(0)
DIV=10**9
a = S//DIV
b = S%DIV
x = 10**9-b
y = a + 1
if x>10**9:
  print(x)
if y>10**9:
  print(y)
print(0,0,10**9,1,x,y)
Buggy python submission (verdict: Time Limit Exceeded):
l,r=map(int,input().split())
mini = 2018
for i in range(l,r,1):
  for j in range(i+1,r+1,1):
    mini = min((i*j)%2019, mini)
    if mini == 0:
      break

print(mini)

Fixed submission:
L,R=map(int,input().split())
if R-L>2019:
  print(0)
elif L%2019==0 or R%2019==0:
  print(0)
elif L//2019!=R//2019:
  print(0)
else:
  L=L%2019
  R=R%2019
  ans=2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      ans=min(ans,(i*j)%2019)
      if ans==0:
        break

  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l,r=map(int,input().split())
min = 2018
for i in range(l,r,1):
  for j in range(i+1,r+1,1):
    if (i*j)%2019 < min:
      min = (i*j)%2019
      if min == 0:
        break

print(min)

Fixed submission:
L,R=map(int,input().split())
if R-L>2019:
  print(0)
elif L%2019==0 or R%2019==0:
  print(0)
elif L//2019!=R//2019:
  print(0)
else:
  L=L%2019
  R=R%2019
  ans=2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      ans=min(ans,(i*j)%2019)
      if ans==0:
        break

  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l,r=map(int,input().split())
min = 2018
for i in range(l,r,1):
  for j in range(i+1,r+1,1):
    if (i*j)%2019 < min:
      min = (i*j)%2019

print(min)

Fixed submission:
L,R=map(int,input().split())
if R-L>2019:
  print(0)
elif L%2019==0 or R%2019==0:
  print(0)
elif L//2019!=R//2019:
  print(0)
else:
  L=L%2019
  R=R%2019
  ans=2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      ans=min(ans,(i*j)%2019)
      if ans==0:
        break

  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

stack=[]
INF=10**5*3
seen=[[INF for i in range(3)] for j in range(N)]
stack.append([S,0,1])
ans=INF
while stack:
  node=stack.pop()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      if ans>turn:
        ans=turn
      continue
    step=0
    turn+=1
  if seen[v][step]<=turn:
    continue
  seen[v][step]=turn
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  if ans==INF:
    print(-1)
  else:
    print(ans)


Fixed submission:
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

from collections import deque
stack=deque()
seen=[[False for i in range(3)] for j in range(N)]
stack.append([S,0,1])
while stack:
  node=stack.popleft()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      print(turn)
      break
    step=0
    turn+=1
  if seen[v][step]:
    continue
  seen[v][step]=True
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

stack=[]
INF=10**9
seen=[[INF for i in range(3)] for j in range(N)]
stack.append([S,0,1])
ans=INF
while stack:
  node=stack.pop()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      if ans>turn:
        ans=turn
      continue
    step=0
    turn+=1
  if seen[v][step]<=turn:
    continue
  seen[v][step]=turn
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  if ans==INF:
    print(-1)
  else:
    print(ans)


Fixed submission:
N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

from collections import deque
stack=deque()
seen=[[False for i in range(3)] for j in range(N)]
stack.append([S,0,1])
while stack:
  node=stack.popleft()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      print(turn)
      break
    step=0
    turn+=1
  if seen[v][step]:
    continue
  seen[v][step]=True
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
a,b,c,d=map(int,input().split())

def gcd(x,y):
  if x<y:
    x,y=y,x
  while x%y!=0:
    x,y=y,x%y
  return y

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

block=lcm(c,d)
block_c=block//c
block_d=block//d
ans_in_block=block-(block_c+block_d-1)

def count_ans(z,block,ans_in_block,p,q):
  z_amari=z%block
  z_ans=0
  for i in range(1,z_amari+1):
    if i%p!=0 and i%q!=0:
      z_ans+=1
  return (z//block)*ans_in_block+z_ans

print(count_ans(b,block,ans_in_block,c,d)-count_ans(a,block,ans_in_block,c,d)+(a%c!=0 and a%d!=0))  


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

def gcd(x,y):
  if x<y:
    x,y=y,x
  while x%y!=0:
    x,y=y,x%y
  return y

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

a_ans=(a-1)-(a-1)//c-(a-1)//d+(a-1)//lcm(c,d)
b_ans=b-b//c-b//d+b//lcm(c,d)
print(b_ans-a_ans)
Buggy python submission (verdict: Runtime Error):
# 最も小さい数から最も大きい数を引く、を繰り返すことで、できるだけ小さい数が作れる
# 最後に残った数からできるだけ小さい数を引くことで答えが求められる

N=int(input())
A=sorted(list(map(int,input().split())))

if N==2:
  print(A[1]-A[0])

from collections import deque
q = deque(A)

seq = []
x = q.popleft()
y = q.pop()
seq += [[x,y]]
x = x-y
while len(q) > 1:
  y = q.pop()
  seq += [[x,y]]
  x = x-y

y = q.pop()
seq += [[y,x]]
print(y - x)
for s in seq:
  print(*s)


Fixed submission:
# 符号が異なる数同士の引き算をすれば絶対値が大きくなる
# 基本は負から正を引いて大きな負の数を作る
# 最後だけ正から負を引いて大きな正の数を作る
# 正と正しか存在しない場合は最も小さい数からその他の数を引くことで負の数を作れる
# 負と負しか存在しない場合は最も大きい数からその他の数を引くことで正の数を作れる
# 正のリストと負のリスト両方を管理する
# 0は何も影響を与えないのでとりあえず正のリストに入れておく

N = int(input())
A = list(map(int,input().split()))

if len(A) == 2:
  x = max(A)
  y = min(A)
  print(x-y)
  print(x,y)
  exit(0)

plusA = []
minusA = []
for a in A:
  if a >= 0:
    plusA += [a]
  else:
    minusA += [a]
    
method = [] # 計算過程をメモ
if len(plusA) == 0:
  minusA = sorted(minusA) # 最も小さな数を取り出すため
#  print("minusA",minusA)
  x = minusA.pop()
  y = minusA.pop()
#  print("x",x,"y",y)
  method.append([x,y])
  plusA.append(x-y)
#  print("plusA",plusA,"minusA",minusA,"method",method)
elif len(minusA) == 0:
  plusA = sorted(plusA)[::-1] # 最も小さな数を取り出すため
  x = plusA.pop()
  y = plusA.pop()
  method.append([x,y])
  minusA.append(x-y)
  
while True:
  if len(minusA) + len(plusA) == 1:
    print(x-y)
    for m in method:
      print(*m)
    break
  if len(plusA) == 1:
    # 正の数が一つのときは、この数から残りの負の数を引いていく
    x = plusA.pop()
    y = minusA.pop()
    method.append([x,y])
    plusA.append(x-y)
  else:
    # 正の数が複数あるときは、負の数を作り続ける
    x = minusA.pop()
    y = plusA.pop()
    method.append([x,y])
    minusA.append(x-y)
Buggy python submission (verdict: Time Limit Exceeded):
n,m,*a=map(int,open(0).read().split())
dp=[0]*(n+2)
dp[0]=1
div=1000000007
for i in range(n):
  dp[i]%=div
  if i+1 in a:
    dp[i+1]=0
  else:
    dp[i+1]+=dp[i]
  if i+2 in a:
    dp[i+2]=0
  else:
    dp[i+2]+=dp[i]
print(dp[n]%div)

Fixed submission:
n,m=map(int,input().split())
broken=[False]*(n+1)
for i in range(m):
  broken[int(input())]=True
dp=[0]*(n+1)
dp[0]=1
dp[1]=0 if broken[1] else 1

for i in range(2,len(dp)):
  if broken[i]:
    dp[i]=0
  else:
    dp[i]=(dp[i-2]+dp[i-1])%1000000007
  
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
  n,m=map(int,input().split())
  broken=[0]*m
  for i in range(m):
    broken[i]=int(input())
  
  dp=[0]*(n+1)
  dp[0]=1
  dp[1]=1 if 1 not in broken else 0

  for i in range(2,len(dp)):
    if i in broken:
      dp[i]=0
    else:
      dp[i]=(dp[i-2]+dp[i-1])%1000000007
  
  print(dp[-1])

solve()

Fixed submission:
n,m=map(int,input().split())
broken=[False]*(n+1)
for i in range(m):
  broken[int(input())]=True
dp=[0]*(n+1)
dp[0]=1
dp[1]=0 if broken[1] else 1

for i in range(2,len(dp)):
  if broken[i]:
    dp[i]=0
  else:
    dp[i]=(dp[i-2]+dp[i-1])%1000000007
  
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
broken=[0]*m
for i in range(m):
  broken[i]=int(input())
  
dp=[0]*(n+1)
dp[0]=1
dp[1]=1 if 1 not in broken else 0

for i in range(2,len(dp)):
  if i in broken:
    dp[i]=0
  else:
    dp[i]=(dp[i-2]+dp[i-1])%1000000007
  
print(dp[-1])

Fixed submission:
n,m=map(int,input().split())
broken=[False]*(n+1)
for i in range(m):
  broken[int(input())]=True
dp=[0]*(n+1)
dp[0]=1
dp[1]=0 if broken[1] else 1

for i in range(2,len(dp)):
  if broken[i]:
    dp[i]=0
  else:
    dp[i]=(dp[i-2]+dp[i-1])%1000000007
  
print(dp[-1])