Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
starts = []
goals = []
for _ in range(M):
    s, g = map(int, input().split())
    if s == 1:
        starts.append(g)
    elif g == N:
        goals.append(s)

for i in starts:
    if i in goals:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

Fixed submission:
N, M = map(int, input().split())
starts = []
goals = []
for _ in range(M):
    s, g = map(int, input().split())
    if s == 1:
        starts.append(g)
    elif g == N:
        goals.append(s)

ans = set(starts) & set(goals)

if len(ans) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
starts = []
goals = []
for _ in range(M):
    s, g = map(int, input().split())
    if s == 1:
        starts.append(g)
    elif g == N:
        goals.append(s)

for i in starts:
    if i in goals:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

Fixed submission:
N, M = map(int, input().split())
starts = []
goals = []
for _ in range(M):
    s, g = map(int, input().split())
    if s == 1:
        starts.append(g)
    elif g == N:
        goals.append(s)

ans = set(starts) & set(goals)

if len(ans) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

ans = 10**10
for i in range(1, N):
    a = sum(A[0:i])
    b = sum(A[i:N+1])
    ans = min(ans, abs(a - b))

print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
arai = sum(A)
sunuke = 0

ans = 10**10
for i in range(0, N-1):
    sunuke += A[i]
    arai -= A[i]
    ans = min(ans, abs(sunuke - arai))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
"""
Nは10**5以下。O(N)なら通る
"""

N = int(input())
A = []
B = []
for i in range(N):
    s = list(map(int, input().split()))
    A.append(s[0])
    B.append(s[1])

count = 0
for i in reversed(range(N)):
    if A[i] % B[i] == 0:
        continue
    else:
        s = B[i] - (A[i] % B[i])
        A[:i+1] = map(lambda x: x + s, A[:i+1])
        count += s

print(count)

Fixed submission:
"""
Nは10**5以下。O(N)なら通る
"""

N = int(input())
A = []
B = []
for i in range(N):
    s = list(map(int, input().split()))
    A.append(s[0])
    B.append(s[1])

count = 0
for i in reversed(range(N)):
    if (count + A[i]) % B[i] == 0:
        continue
    else:
        s = B[i] - (count + A[i]) % B[i]
        count += s

print(count)
Buggy python submission (verdict: Runtime Error):
from statistics import mean
import math

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

mean_num = mean(A)
Ceil = math.ceil(mean_num)
Floor = math.floor(mean_num)

Ceil_sum = 0
Floor_sum = 0
for i in A:
    Ceil_sum += (Ceil - i) ** 2
for i in A:
    Floor_sum += (Floor - i) ** 2

print(min(Floor_sum, Ceil_sum))

Fixed submission:
from statistics import mean
import math

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

mean_num = mean(A)
Ceil = math.ceil(mean_num)
Floor = math.floor(mean_num)

Ceil_sum = 0
Floor_sum = 0
for i in A:
    Ceil_sum += (Ceil - i) ** 2
for i in A:
    Floor_sum += (Floor - i) ** 2

print(min(Floor_sum, Ceil_sum))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    b = [0 for i in range(n + 1)]
    for i in range(n):
        l = max(0, i - a[i])
        r = min(n, i + a[i] + 1)
        b[l] += 1
        b[r] -= 1
    for i in range(len(b)-1):
        b[i+1] += b[i]
    b = b[:n]
    if a == b:
        break
    else:
        a = b
for i in range(n):
    print(b[i])


Fixed submission:
from numba import njit
@njit(cache=True)
def func(n, k, a):
    for i in range(k):
        b = []
        for i in range(n+1):
            b.append(0)
        for i in range(n):
            l = max(0, i - a[i])
            r = min(n, i + a[i] + 1)
            b[l] += 1
            b[r] -= 1
        for i in range(len(b)-1):
            b[i+1] += b[i]
        b = b[:n]
        if a == b:
            break
        else:
            a = b
    return b
if __name__ == '__main__':
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = func(n, k, a)
    for i in range(n):
        print(b[i])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
ans = 1
flag = 0
for i in range(n):
    ans = ans * a[i]
    if a[i] == 0:
        ans = 0
        break


if ans > 10**18:
    print('-1')
else:
    print(ans)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
ans = 1
flag = 0
for i in range(n):
    ans = ans * a[i]
    if a[i] == 0:
        ans = 0
        break
    elif ans > 10**18 or a[i] > 10**18:
        if a[i:].count(0) > 0:
            ans = 0
            break
        else:
            ans = -1
            break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
    ans = ans * a[i]
if ans > 10**18:
    print('-1')
else:
    print(ans)


Fixed submission:
n = int(input())
a = list(map(int,input().split()))
ans = 1
flag = 0
for i in range(n):
    ans = ans * a[i]
    if a[i] == 0:
        ans = 0
        break
    elif ans > 10**18 or a[i] > 10**18:
        if a[i:].count(0) > 0:
            ans = 0
            break
        else:
            ans = -1
            break
print(ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())
h = list(map(int,input().split()))
max = max(h)
count = [0 for i in range(max)]
for i in range(m):
    a, b = map(int,input().split())
    if a >= b:
        A = a
        a = b
        b = A
    count[a-1] = 1
ans = 0
for i in h:
    if count[i-1] == 0:
        ans += 1
print(ans)


Fixed submission:
n, m = map(int,input().split())
h = list(map(int,input().split()))
dic = {}
for i in range(len(h)):
    dic[i] = 0
for i in range(m):
    a, b = map(int,input().split())
    if h[a-1] > h[b-1]:
        dic[b-1] = 1
    elif h[a-1] < h[b-1]:
        dic[a-1] = 1
    elif h[a-1] == h[b-1]:
        dic[b-1] = 1
        dic[a-1] = 1
ans = 0
for i in range(len(h)):
    if dic[i] == 0:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import collections
n=int(input())
s = []
sort=[]
for i in range(n):
    s.append(input())
ans=collections.Counter(s).most_common()
oldnum=ans[0][1]
for i in range(n):
    if oldnum == ans[i][1]:
        sort.append(ans[i][0])
        oldnum=ans[i][1]
    else:
        break
sort.sort()
for i in range(len(sort)):
    print(sort[i])


Fixed submission:
import collections
n=int(input())
s = []
sort=[]
for i in range(n):
    s.append(input())
ans=collections.Counter(s).most_common()
oldnum=ans[0][1]
for i in range(len(ans)):
    if oldnum == ans[i][1]:
        sort.append(ans[i][0])
        oldnum=ans[i][1]
    else:
        break
sort.sort()
for i in range(len(sort)):
    print(sort[i])
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
p=list(map(int,input().split()))
new_p=[]
s=[]
ans=-1
for i in range(n):
    new_p.append((((p[i]*(1+p[i]))/2)/p[i]))
s.append(new_p[0])
for i in range(n-1):
    s.append(s[i]+new_p[i+1])
for i in range((len(s)-k)):
    val=s[k+i]-s[i]
    ans=max(ans,max)
print(ans)


Fixed submission:
n,k=map(int,input().split())
p=list(map(int,input().split()))
new_p=[]
s=[]
ans=-(10**9)
for i in range(n):
    new_p.append((1+p[i])/2)
s.append(new_p[0])
for i in range(n-1):
    s.append(s[i]+new_p[i+1])
s.insert(0,0)
for i in range((len(s)-k)):
    val=s[k+i]-s[i]
    ans=max(ans,val)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[]
p=0
for i in range((n-k+1)):
    for j in range(k):
        p+=(((a[i+j]*(1+a[i+j]))/2)/a[i+j])
    ans.append(p)
    p=0
print(max(ans))


Fixed submission:
n,k=map(int,input().split())
p=list(map(int,input().split()))
new_p=[]
s=[]
ans=-(10**9)
for i in range(n):
    new_p.append((1+p[i])/2)
s.append(new_p[0])
for i in range(n-1):
    s.append(s[i]+new_p[i+1])
s.insert(0,0)
for i in range((len(s)-k)):
    val=s[k+i]-s[i]
    ans=max(ans,val)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=input().split()
flag=0
oldflag=2*10**5+1
ans=0
for i in range(1,(n+1)):
    idx=p.index(str(i))
    flag=idx
    ans+=1
    if oldflag<idx:
        ans-=1
        flag=oldflag
        continue
    oldflag=flag
print(ans)


Fixed submission:
n=int(input())
p=list(map(int,input().split()))
flag=2*10**5+1
ans=0
for i in range(n):
    if flag>int(p[i]):
        ans+=1
    flag=min(flag,p[i])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=input().split()
flag=2*10**5+1
ans=0
for i in range(1,(n+1)):
    idx=p.index(str(i))
    if flag>idx:
        ans+=1
        flag=idx
print(ans)


Fixed submission:
n=int(input())
p=list(map(int,input().split()))
flag=2*10**5+1
ans=0
for i in range(n):
    if flag>int(p[i]):
        ans+=1
    flag=min(flag,p[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
p=[]
s=[]
start=0
idx=0
AC=0
WA=0
count=0
for i in range(m):
    p_,s_=input().split()
    p.append(int(p_))
    s.append(s_)
for i in range(m):
    count=p.count(p[idx])
    if s[start:start+count].count('AC')>=1:
        AC+=1
        WA+=s[start:s[start:start+count].index('AC')+start].count('WA')
    else:
        WA+=s[start:start+count].count('WA')
    start=start+count
    idx=start
    if start==m:
        break
print("{} {}".format(AC,WA))


Fixed submission:
n,m=map(int,input().split())
ac=[0]*n
wa=[0]*n
for i in range(m):
    p,s=input().split()
    p=int(p)
    if ac[p-1] == 1:
        continue
    if s=='AC':
        ac[p-1] = 1
    else:
        wa[p-1] += 1
AC=0
WA=0
for i in range(n):
    AC += ac[i]
    if ac[i] == 1:
        WA += wa[i]
print("{} {}".format(AC,WA))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
p=[]
s=[]
idx=0
AC=0
WA=0
for i in range(m):
    p_,s_=input().split()
    p.append(int(p_))
    s.append(s_)
for i in range(m):
    cp=p.count(p[idx])
    for i in range(idx,(cp+idx)):
        ##print(i)
        if s[i]=='WA':
            WA+=1
        elif s[i]=='AC':
            AC+=1
            break
    idx=cp+idx
    if idx==m:
        break
print("{} {}".format(AC,WA))


Fixed submission:
n,m=map(int,input().split())
ac=[0]*n
wa=[0]*n
for i in range(m):
    p,s=input().split()
    p=int(p)
    if ac[p-1] == 1:
        continue
    if s=='AC':
        ac[p-1] = 1
    else:
        wa[p-1] += 1
AC=0
WA=0
for i in range(n):
    AC += ac[i]
    if ac[i] == 1:
        WA += wa[i]
print("{} {}".format(AC,WA))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,k,q=map(int,input().split())
a=[]
ones=np.ones((1,n,))
point=k*ones
de_point=ones
for i in range(q):
    num=int(input())
    de_point[0,num-1]=0
    point=point-de_point
    de_point[0,num-1]=1
for i in range(n):
    if point[0,i]>0:
        print("Yes")
    elif point[0,i]<=0:
        print("No")


Fixed submission:
import numpy as np
n,k,q=map(int,input().split())
a=[]
ones=np.ones((1,n,))
point=k*ones
de_point=-q*ones
for i in range(q):
    num=int(input())
    de_point[0,num-1]=de_point[0,num-1]+1
point=point+de_point
for i in range(n):
    if point[0,i]>0:
        print("Yes")
    elif point[0,i]<=0:
        print("No")
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,k = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp = np.zeros(n)
for i in range(1,n):
    flag = max(0,i-k)
    dp[i] = np.min(dp[flag:i]+abs(h[flag:i]-h[i]))
print(int(dp[n-1]))


Fixed submission:
import numpy as np
n,k = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp = np.zeros(n)
for i in range(1,n):
    flag = max(0,i-k)
    dp[i] = np.min(dp[flag:i]+abs(h[flag:i]-h[i]))
print(int(dp[-1]))

Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [10**9 for i in range(n)]
dp[0] = 0
for i in range(1,n):
    for j in range(1,(k+1)):
        if i-j >= 0 :
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[n-1])


Fixed submission:
import numpy as np
n,k = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp = np.zeros(n)
for i in range(1,n):
    flag = max(0,i-k)
    dp[i] = np.min(dp[flag:i]+abs(h[flag:i]-h[i]))
print(int(dp[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
WV = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    WV.append(list(map(int,input().split())))
for i in range(N):
    dp[i+1][0:WV[i][0]] = dp[i][0:WV[i][0]]
    for w in range(WV[i][0],W+1):
        dp[i+1][w] = max(dp[i][w],dp[i][w - WV[i][0]]+WV[i][1])
print(max(max(dp)))


Fixed submission:
import numpy as np
N,W = map(int,input().split())
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:W+1] = np.maximum(dp[0:W+1-w]+v,dp[w:W+1])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
WV = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    WV.append(list(map(int,input().split())))
for i in range(N):
    for w in range(W+1):
        if  w - WV[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w],dp[i][w - WV[i][0]]+WV[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(dp[-1][-1])


Fixed submission:
import numpy as np
N,W = map(int,input().split())
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:W+1] = np.maximum(dp[0:W+1-w]+v,dp[w:W+1])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int,input().split())
WV = []
dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    WV.append(list(map(int,input().split())))
for i in range(N):
    for w in range(W+1):
        if  w - WV[i][0] >= 0:
            dp[i+1][w] = max(dp[i][w],dp[i][w - WV[i][0]]+WV[i][1])
        else:
            dp[i+1][w] = dp[i][w]
print(max(max(dp)))


Fixed submission:
import numpy as np
N,W = map(int,input().split())
dp = np.zeros(W+1,dtype=int)
for i in range(N):
    w,v = map(int,input().split())
    dp[w:W+1] = np.maximum(dp[0:W+1-w]+v,dp[w:W+1])
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
(lambda f: int(input()) == print(min([f(f, i, 0) for i in list(map(int, input().split()))])))(lambda f, i, c: f(i // 2, c + 1) if i % 2 == 0 else c)

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

def func(i, c):
    return func(i // 2, c + 1) if i % 2 == 0 else c

print(min([func(i, 0) for i in A]))
Buggy python submission (verdict: Runtime Error):
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

def main(N, M, a_list):
    div = 10**9 + 7
    @lru_cache(maxsize=None)
    def fib(n):
        if n in a_list:
            return 0
        else:
            if n == -1:
                return 0
            elif n == 0 or n == 1:
                return 1
            else:
                return fib(n-2) % div + fib(n-1) % div
    
    
    print(fib(N) % div )


if __name__ == "__main__":
    N, M = [int(x) for x in input().split()]
    a_list = []
    for _ in range(M):
        a_list.append(int(input()))

    main(N, M, a_list)


Fixed submission:

def main(P, Q, R):
    print(min([P+Q, Q+R, P+R]))

if __name__ == "__main__":
    P, Q, R = [int(x) for x in input().split()]

    main(P, Q, R)
Buggy python submission (verdict: Time Limit Exceeded):
import copy
N,K = map(int,input().split())
A = list(map(int,input().split()))

for i in range(K):
  l = [0]*N
  for i in range(N):
    m,p = i-A[i],i+A[i]
    if p+1 <= N-1:
      l[p+1] -= 1
    if m >= 0:
      l[m] += 1
    if m < 0:
      l[0] += 1
  for i in range(N-1):
    l[i+1] += l[i]
  A = copy.deepcopy(l)
  if A[0] == N:
    break 
print(*A)

Fixed submission:
import copy
N,K = map(int,input().split())
A = list(map(int,input().split()))

for i in range(K):
  l = [0]*N
  for i in range(N):
    m,p = i-A[i],i+A[i]
    if p+1 <= N-1:
      l[p+1] -= 1
    if m >= 0:
      l[m] += 1
    if m < 0:
      l[0] += 1
  for i in range(N-1):
    l[i+1] += l[i]
  A = copy.deepcopy(l)
  if A[0] == N:
    break 
print(*A)
Buggy python submission (verdict: Time Limit Exceeded):
import math
K = int(input())
ans = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += math.gcd(a,math.gcd(b,c))
print(ans)

Fixed submission:
import math
K = int(input())
ans = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += math.gcd(a,math.gcd(b,c))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = "0"+input()
lr = [0]
lg = [0]
lb = [0]
for j in range(1,N+1):
  if S[j] == "R":
    i = j-1
    lr.append(lr[i]+1)
    lg.append(lg[i])
    lb.append(lb[i])
  if S[j] == "G":
    i = j-1
    lr.append(lr[i])
    lg.append(lg[i]+1)
    lb.append(lb[i])
  if S[j] == "B":
    i = j-1
    lr.append(lr[i])
    lg.append(lg[i])
    lb.append(lb[i]+1)

cnt = 0
mcnt = 0
for i in range(1,N+1):
  s = S[i]
  for j in range(1,N-i+1): 
    #Rパターン
    if s == "R":      
      if S[i+j] == "R":
        continue
      else:
        if i+j <= N and i-j >=0:
          if (S[i+j] == "B" and S[i-j] == "G") or (S[i+j] == "G" and S[i-j] == "B"):
            mcnt += -1 
        if S[i+j] == "G":
          cnt += lb[i-1]
        if S[i+j] == "B":
          cnt += lg[i-1]
    #Gパターン
    if s == "G":      
      if S[i+j] == "G":
        continue
      else:
        if i+j <= N and i-j >=0: 
          if (S[i+j] == "B" and S[i-j] == "R") or (S[i+j] == "R" and S[i-j] == "B"):
            mcnt += -1 
        if S[i+j] == "R":
          cnt += lb[i-1]
        if S[i+j] == "B": 
          cnt += lr[i-1]   
    #Bパターン
    if s == "B":      
      if S[i+j] == "B":
        continue
      else:
        if i+j <= N and i-j >=0: 
          if (S[i+j] == "G" and S[i-j] == "R") or (S[i+j] == "R" and S[i-j] == "G"):
            mcnt += -1 
        if S[i+j] == "R":
          cnt += lg[i-1]
        if S[i+j] == "G": 
          cnt += lr[i-1]  
print(cnt+mcnt)

Fixed submission:
N = int(input())
S = "0"+input()
lr = [0]
lg = [0]
lb = [0]
for j in range(1,N+1):
  if S[j] == "R":
    i = j-1
    lr.append(lr[i]+1)
    lg.append(lg[i])
    lb.append(lb[i])
  if S[j] == "G":
    i = j-1
    lr.append(lr[i])
    lg.append(lg[i]+1)
    lb.append(lb[i])
  if S[j] == "B":
    i = j-1
    lr.append(lr[i])
    lg.append(lg[i])
    lb.append(lb[i]+1)

cnt = 0
mcnt = 0
for i in range(1,N+1):
  s = S[i]
  for j in range(1,N-i+1): 
    #Rパターン
    if s == "R":      
      if S[i+j] == "R":
        continue
      else:
        if i+j <= N and i-j >=0:
          if (S[i+j] == "B" and S[i-j] == "G") or (S[i+j] == "G" and S[i-j] == "B"):
            mcnt += -1 
        if S[i+j] == "G":
          cnt += lb[i-1]
        if S[i+j] == "B":
          cnt += lg[i-1]
    #Gパターン
    if s == "G":      
      if S[i+j] == "G":
        continue
      else:
        if i+j <= N and i-j >=0: 
          if (S[i+j] == "B" and S[i-j] == "R") or (S[i+j] == "R" and S[i-j] == "B"):
            mcnt += -1 
        if S[i+j] == "R":
          cnt += lb[i-1]
        if S[i+j] == "B": 
          cnt += lr[i-1]   
    #Bパターン
    if s == "B":      
      if S[i+j] == "B":
        continue
      else:
        if i+j <= N and i-j >=0: 
          if (S[i+j] == "G" and S[i-j] == "R") or (S[i+j] == "R" and S[i-j] == "G"):
            mcnt += -1 
        if S[i+j] == "R":
          cnt += lg[i-1]
        if S[i+j] == "G": 
          cnt += lr[i-1]  
print(cnt+mcnt)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N,X,Y = map(int,input().split())
G = [[] for i in range(N+1)] 
for i in range(1,N+1):
  if i-1 >= 1:
    G[i].append(i-1)
  if i+1 <= N:
    G[i].append(i+1)

G[X].append(Y)
G[Y].append(X)

dl = [0]*(N+1)
def bfs(p):
  seen = [False]*(N+1)
  seen[p] = True
  dist = [0]*(N+1)
  d = deque([p])
  while len(d) > 0:
    v = d.popleft()
    for i in G[v]:
      if seen[i] == False:
        seen[i] = True
        dist[i] = dist[v]+1
        dl[dist[i]] += 1
        d.append(i)      


for i in range(1,N+1):
  bfs(i)

for i in range(1,N):
  print(dl[i]//2)

Fixed submission:
import collections
from collections import deque

N,X,Y = map(int,input().split())

#辺のリスト
n = N
l_hen = [[i,i+1] for i in range(1,n)]+[[X,Y]]

#頂点のラベルリスト
l_chouten =list( set(sum(l_hen, [])) )

#G={頂点:[頂点に繋がっている点たち],... } を取得する
G = dict( [ (key,[]) for key in l_chouten]  )
for i in range(n):
   G[l_hen[i][0]].append(l_hen[i][1])

#無効グラフの場合両方から見ているので以下のコードも実行する
for i in range(n):
   G[l_hen[i][1]].append(l_hen[i][0])

'''
以上グラフの準備
'''
#seenとtodoの初期設定
l_seen = {i:False for i in l_chouten}
l_todo = []
dist = {i:-1 for i in l_chouten}
#距離の羅列用  
l_d =deque([])  

for point in range(1,N+1):
  #seenとtodoの初期設定
  for key in l_seen:
    l_seen[key] = 0
  l_todo = []  
  for key in dist:
    dist[key] = 0

  #seenに出発地点pを決めてやる、出発点の隣接リストもtodoに入れる
  p = point
  l_seen[p] = True #pはチェック済み
  for i in G[p]:
    l_seen[i] = True #pに隣接する頂点もチェック済み
  l_todo = l_todo + G[p] #pに隣接する頂点をtodoリストに追加
  l_todo = deque(l_todo)
  dist[p] = 0
  for i in G[p]:
    dist[i] = 1 #pに隣接する頂点とpとの距離を1とする
    l_d.append(dist[i])
  

  #探索
  while len(l_todo) != 0:
    #幅優先探索
    v = l_todo.popleft() #todoの左端つまりindex0から処理しているので
    for i in G[v]:
      #回り込まれて先越された時
      if l_seen[i] == True:
        continue
      else:
        l_seen[i] = True
        l_todo.append(i)
        dist[i]=dist[v]+1
        l_d.append(dist[i])
###
c = collections.Counter(l_d)
for i in range(1,N):
  print(c[i]//2)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if (c+int(i[1]))%2 ==1:
      s = i[2] + s
    else:
      s = s + i[2]  
  
if c == 1:
  s = ''.join(list(reversed(s)))
print(s)

Fixed submission:
from collections import deque

s = deque( list(input()) )
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if (c+int(i[1]))%2 ==1:
      s.appendleft(i[2])
    else:
      s.append(i[2])

s=list(s)

if c == 1:
  s.reverse()

s = ''.join(s)
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if (c+int(i[1]))%2 ==1:
      s = i[2] + s
    else:
      s = s + i[2]  
  
if c == 1:
  s = ''.join(list(reversed(s)))
print(s)

Fixed submission:
from collections import deque

s = deque( list(input()) )
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if (c+int(i[1]))%2 ==1:
      s.appendleft(i[2])
    else:
      s.append(i[2])

s=list(s)

if c == 1:
  s.reverse()

s = ''.join(s)
print(s)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if i[1] == "1":
      if c==0:
        s = i[2] + s
      else:
        s = s + i[2] 
    else:
      if c==1:
        s = i[2] + s
      else:
        s = s + i[2] 
if c == 1:
  s = ''.join(list(reversed(s)))
print(s)

Fixed submission:
from collections import deque

s = deque( list(input()) )
q = int(input())

l_q = []
for i in range(q):
  l_q.append( list(input().split())  ) 

#クエリ処理
c = 0
for i in l_q:

  if i[0] == "1":
    c = (c+1)%2

  else:
    if (c+int(i[1]))%2 ==1:
      s.appendleft(i[2])
    else:
      s.append(i[2])

s=list(s)

if c == 1:
  s.reverse()

s = ''.join(s)
print(s)