Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from sys import stdin, stderr
from collections import deque

def solve():
    N, M = map(int, input().split())

    Adj = [[] for i in range(N)]

    for i in range(M):
        a, b = map(int, stdin.readline().split())
        a, b = a - 1, b - 1
        Adj[a].append(b)
        Adj[b].append(a)

    Q = int(stdin.readline())

    assert 1 <= N <= 2000
    assert 1 <= M <= 2000
    assert 1 <= Q <= 2000
    
    v = [0] * Q
    d = [0] * Q
    c = [0] * Q

    for i in range(Q):
        v[i], d[i], c[i] = map(int, stdin.readline().split())
        v[i] -= 1

    cols = [0] * N

    for i in range(Q):
        bfs(N, Adj, v[i], d[i], c[i], cols)

    print(*cols, sep='\n')

def bfs(N, Adj, v, d, c, cols):
    visited = [False] * N
    visited[v] = True

    nxts = deque([[v, 0]])

    while nxts:
        u, dis = nxts.popleft()

        if dis > d:
            continue

        cols[u] = c

        for w in Adj[u]:
            if not visited[w]:
                visited[w] = True
                nxts.append([w, dis + 1])

    return

if __name__ == '__main__':
    solve()

Fixed submission:
from sys import stdin, stderr
from collections import deque

def solve():
    N, M = map(int, input().split())

    Adj = [[] for i in range(N)]

    for i in range(M):
        a, b = map(int, stdin.readline().split())
        a, b = a - 1, b - 1
        Adj[a].append(b)
        Adj[b].append(a)

    Q = int(stdin.readline())

    v = [0] * Q
    d = [0] * Q
    c = [0] * Q

    for i in range(Q):
        v[i], d[i], c[i] = map(int, stdin.readline().split())
        v[i] -= 1

    v.reverse()
    d.reverse()
    c.reverse()

    cols = [0] * N
    nuta = [-1] * N

    for i in range(Q):
        bfs(N, Adj, v[i], d[i], c[i], cols, nuta)

    print(*cols, sep='\n')

def bfs(N, Adj, v, d, c, cols, nuta):
    if nuta[v] >= d:
        return

    nxts = deque([[v, d]])
    nuta[v] = d

    while nxts:
        u, step = nxts.popleft()

        if step < 0:
            continue

        if cols[u] == 0:
            cols[u] = c

        for w in Adj[u]:
            if nuta[w] < step - 1:
                nuta[w] = step - 1
                nxts.append([w, step - 1])

    return

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from math import factorial

def solve():
    N, A, B = map(int, input().split())
    v = [int(i) for i in input().split()]

    h1, c1 = half_rekkyo(N, v, 0, N // 2)
    h2, c2 = half_rekkyo(N, v, N // 2, N - N //2)

    max_ave = 0
    cnt = 0

    for i in range(len(h1)):
        for j in range(len(h2)):
            if A <= i + j <= B:
                tot = h1[i] + h2[j]
                ave = tot / (i + j)

                if ave > max_ave:
                    cnt = c1[i] * c2[j]
                    max_ave = ave
                elif ave == max_ave:
                    cnt += c1[i] * c2[j]

    print(max_ave)
    print(cnt)

def half_rekkyo(N, v, s, m):
    max_vs = [0] * (m + 1)
    nums = [0] * (m + 1)

    for cmb in range(2**m):
        # print(bin(cmb))
        value = 0
        cnt = 0

        for i in range(m):
            if cmb & (1 << i):
                value += v[s + i]
                cnt += 1

        # print(value, cnt)

        if value == max_vs[cnt]:
            nums[cnt] += 1
        elif value > max_vs[cnt]:
            nums[cnt] = 1
            max_vs[cnt] = value

    return max_vs, nums

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Fixed submission:
import sys
from math import factorial

def solve():
    N, A, B = map(int, input().split())
    v = [int(i) for i in input().split()]
    v.sort(reverse=True)

    ave_max = sum(v[:A]) / A

    onaji = v.count(v[0])

    if onaji < A:
        k = v[:A].count(v[A - 1])
        n = v.count(v[A - 1])
        cnt = binom(n, k)
    else:
        cnt = 0

        for i in range(A, min(onaji, B) + 1):
            cnt += binom(onaji, i)

    print('{:.8f}'.format(ave_max))
    print(cnt)


def binom(n, k):
    return (factorial(n) // factorial(n - k)) // factorial(k)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import accumulate
from collections import deque

def solve():
    N, K = map(int, input().split())
    S = input()
    q = deque([1 if c == 'A' else 0 for c in S])
    cb = 1

    for i in range(K):
        if q[0] == cb:
            q[0] ^= 1
            # cb ^= 1
        else:
            q.popleft()
            q.append(cb ^ 1)
            cb ^= 1

    # print(q)

    ans = ['A' if (c ^ cb ^ 1) else 'B' for c in q]
    print(''.join(ans))


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Fixed submission:
import sys
from itertools import accumulate
from collections import deque

def solve():
    N, K = map(int, input().split())
    S = input()

    '''
    if N == 1:
        if K % 2 == 0:
            print(S)
        else:
            print('A' if S == 'B' else 'B')

        return
    '''

    q = deque([1 if c == 'A' else 0 for c in S])
    cb = 0

    for i in range(min(K, 2 * N + K % 2)):
        if q[0] == (cb ^ 1):
            q[0] ^= 1
        else:
            q.popleft()
            q.append(cb)
            cb ^= 1

    # print(q)

    ans = ['A' if (c ^ cb) else 'B' for c in q]
    print(''.join(ans))


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):
N = int(input())
s = input()

b = [0 if si == 'o' else 1 for si in s]
sw = [0] * N

for i in range(4):
    sw[0] = i & 1
    sw[1] = (i >> 1) & 1

    for k in range(2, N):
        sw[k] = b[k - 1] ^ sw[k - 1] ^ sw[k - 2]

    if b[N - 1] != (sw[N - 2] ^ sw[N - 1] ^ sw[0]):
        continue
    if b[0] != (sw[N - 1] ^ sw[0] ^ sw[1]):
        continue

    ans = ['W' if si else 'S' for si in sw]
    print(''.join(ans))
    quit()

print(-1)

Fixed submission:
import sys

def solve():
    N = int(input())
    ans = 800 * N - 200 * (N // 15)
    print(ans)
    
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Runtime Error):

def BS(th, a):
    top = len(th)
    btm = 0

    while top > btm:
        mid = (top + btm)//2
        if th[mid] <= a < th[mid + 1]:
            return mid
        elif a <= th[mid]:
            top = mid
        else:
            btm = mid

N = int(input())
A = [int(i) for i in input().split()]

th = [0]
num_th = []
rem = []
max_i = 0
nonzeros = dict()

for i, a in enumerate(A):
    if a > th[-1]:
        th.append(a)
        num_th.append(1)
        rem.append(0)
        nonzeros[i] = max_i
        max_i += 1
    else:
        j = BS(th, a)
        if j - 1 >= 0:
            num_th[j - 1] += 1
        rem[j] += a - th[j]

for i in range(len(num_th) - 1, 0, -1):
    num_th[i - 1] += num_th[i]
'''
print(th)
print(num_th)
print(rem)
'''
for i in range(N):
    if i in nonzeros:
        ans = (th[nonzeros[i] + 1] - th[nonzeros[i]])*num_th[nonzeros[i]] + rem[nonzeros[i]]
        print(ans)
    else:
        print(0)

Fixed submission:

def BS(th, a):
    top = len(th)
    btm = 0

    while top > btm:
        mid = (top + btm)//2
        if th[mid] < a <= th[mid + 1]:
            return mid
        elif a <= th[mid]:
            top = mid
        else:
            btm = mid

N = int(input())
A = [int(i) for i in input().split()]

th = [0]
num_th = []
rem = []
max_i = 0
nonzeros = dict()

for i, a in enumerate(A):
    if a > th[-1]:
        th.append(a)
        num_th.append(1)
        rem.append(0)
        nonzeros[i] = max_i
        max_i += 1
    else:
        j = BS(th, a)
        if j - 1 >= 0:
            num_th[j - 1] += 1
        rem[j] += a - th[j]

for i in range(len(num_th) - 1, 0, -1):
    num_th[i - 1] += num_th[i]
'''
print(th)
print(num_th)
print(rem)
'''
for i in range(N):
    if i in nonzeros:
        ans = (th[nonzeros[i] + 1] - th[nonzeros[i]])*num_th[nonzeros[i]] + rem[nonzeros[i]]
        print(ans)
    else:
        print(0)
Buggy python submission (verdict: Runtime Error):
import sys

def calc_depth(n):
    if children[n] == set():
        return 0

    depth_l = [calc_depth(child) for child in children[n]]
    depth_l.sort(reverse=True)

    return max(depth + (i+1) for (i, depth) in enumerate(depth_l))

N = int(input())

children = [set() for i in range(N + 1)]

for i in range(N - 1):
    a = int(input())
    children[a].add(i + 2)

ans = calc_depth(1)

# print(children)

print(ans)

Fixed submission:
import sys

limit = 10 ** 5 * 2
sys.setrecursionlimit(limit)

def calc_depth(n):
    if children[n] == set():
        return 0

    depth_l = [calc_depth(child) for child in children[n]]
    depth_l.sort(reverse=True)

    return max(depth + (i+1) for (i, depth) in enumerate(depth_l))

N = int(input())

children = [set() for i in range(N + 1)]

for i in range(N - 1):
    a = int(input())
    children[a].add(i + 2)

ans = calc_depth(1)

# print(children)

print(ans)
Buggy python submission (verdict: Runtime Error):
K, S = map(int, input().split())
wariate = 0

for x in range(0, K + 1):
    if S - x <= K:
        wariate += max(S - x + 1, 0)
    else:
        wariate += max(0, 2 * K - (S - x) + 1)

print(wariate)

Fixed submission:

s = input().split(",")

print(*s)
Buggy python submission (verdict: Time Limit Exceeded):

# D - Candidates of No Shortest Paths

MAXI = 999999999

# 入力
N, M = map(int, input().split())
cost = [[-1 for i in range(N)] for j in range(N)]

for i in range(M):
    a, b, c = map(int, input().split())
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c

# iからjへの最短距離を表すテーブルの初期化
dist = [[MAXI for i in range(N)] for j in range(N)]

# iからjへの辺があったら、最短距離をその辺のコストで初期化
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]

# ワーシャルフロイドで各i,j間の最短距離を求めておく
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# print(dist)

ans = 0

for i in range(N):
    for j in range(i, N):
        if cost[i][j] != -1: # 各辺がどの異なる２点の最短経路にも含まれないかを調べる
            flag = 1

            for k in range(N):
                for l in range(k + 1, N):
                    # 一つでも最短経路に含まれていたならブレイク
                    if dist[k][l] == dist[k][i] + cost[i][j] + dist[j][l]:
                        flag = 0
                        break
            
            # 全ての異なる２点間の最短経路に含まれていなかったら+1カウント
            ans += flag


print(ans)

Fixed submission:
# D - Candidates of No Shortest Paths

MAXI = 999999999

# 入力
N, M = map(int, input().split())
cost = [[-1 for i in range(N)] for j in range(N)]

for i in range(M):
    a, b, c = map(int, input().split())
    cost[a - 1][b - 1] = c
    cost[b - 1][a - 1] = c

# iからjへの最短距離を表すテーブルの初期化
dist = [[MAXI for i in range(N)] for j in range(N)]

# iからjへの辺があったら、最短距離をその辺のコストで初期化
for i in range(N):
    for j in range(N):
        if i == j:
            dist[i][j] = 0
        elif cost[i][j] != -1:
            dist[i][j] = cost[i][j]
            dist[j][i] = dist[i][j]

# ワーシャルフロイドで各i,j間の最短距離を求めておく
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

# print(dist)

ans = 0

for i in range(N):
    for j in range(i, N):
        if cost[i][j] != -1: # 各辺がどの異なる２点の最短経路にも含まれないかを調べる
            flag = 1

            for k in range(N):
                for l in range(k + 1, N):
                    # 一つでも最短経路に含まれていたならブレイク
                    if dist[k][l] == dist[k][i] + cost[i][j] + dist[j][l]:
                        flag = 0
                        break
            
            # 全ての異なる２点間の最短経路に含まれていなかったら+1カウント
            ans += flag


print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque, Counter

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    N, K, L = map(int, input().split())
    Adj_r = [[] for i in range(N)]
    Adj_t = [[] for i in range(N)]

    for i in range(K):
        p, q = map(int, input().split())
        p, q = p-1, q-1
        Adj_r[p].append(q)
        Adj_r[q].append(p)

    for i in range(L):
        r, s = map(int, input().split())
        r, s = r-1, s-1
        Adj_t[r].append(s)
        Adj_t[s].append(r)

    col = 0
    cols_r = [None] * N
    cols_t = [None] * N

    for u in range(N):
        if cols_r[u] is None:
            bfs_color(N, Adj_r, cols_r, u, col)
            col += 1
        if cols_t[u] is None:
            bfs_color(N, Adj_t, cols_t, u, col)
            col += 1

    # debug(cols_r, locals())
    # debug(cols_t, locals())

    cnt = Counter((cols_r[u], cols_t[u]) for u in range(N))

    ans = [cnt[cols_r[u], cols_t[u]] for u in range(N)]

    print(*ans)


def bfs_color(N, Adj, v_cols, u, col):
    v_cols[u] = col
    nxts = deque([u])

    while nxts:
        v = nxts.popleft()

        for w in Adj[v]:
            if v_cols[w] is None:
                v_cols[w] = col
                nxts.append(w)


if __name__ == '__main__':
    solve()

Fixed submission:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    c = input()
    boin = {'a', 'e', 'i', 'o', 'u'}

    if c in boin:
        ans = 'vowel'
    else:
        ans = 'consonant'

    print(ans)


if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    H, W, N = map(int, sys.stdin.readline().split())
    nb = [0] * 10
    dx = (1, 0, -1, 0, 1, 1, -1, -1)
    dy = (0, 1, 0, -1, 1, -1, 1, -1)
    bb = []

    for lp in range(N):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1

        if in_field(H, W, a, b):
            bb.append((a,b))

        for i in range(len(dx)):
            if in_field(H, W, a+dx[i], b+dy[i]):
                bb.append((a+dx[i], b+dy[i]))

    bb.sort()
    cnt = 0

    for i, box in enumerate(bb):
        if i == 0:
            cnt += 1
            continue
        if box != bb[i-1]:
            nb[cnt] += 1
            cnt = 1
        else:
            cnt += 1

    if cnt > 0:
        nb[cnt] += 1

    nb[0] = (W-2)*(H-2) - sum(nb)

    print(*nb, sep='\n')

def in_field(H, W, a, b):
    return (1 <= a <= H-2) and (1 <= b <= W-2)

if __name__ == '__main__':
    solve()

Fixed submission:
import sys

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

def solve():
    H, W, N = map(int, sys.stdin.readline().split())
    nb = [0] * 10
    bm = dict()
    bb = set()

    for lp in range(N):
        a, b = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1
        res = search(H, W, bm, bb, a, b)

        if 1 <= a <= H-2 and 1 <= b <= W-2:
            bm[a,b] = 1 + res
        
        bb.add((a,b))

    # debug(bm, locals())
    for i in bm.values():
        nb[i] += 1

    nb[0] = (H-2)*(W-2) - sum(nb)

    print(*nb, sep='\n')

def search(H, W, bm, bb, a, b):
    res = 0
    dx = (1, 0, -1, 0, 1, 1, -1, -1)
    dy = (0, 1, 0, -1, 1, -1, 1, -1)

    for j in range(8):
        if (a + dx[j], b + dy[j]) in bb:
            res += 1

        if a + dx[j] < 1 or a + dx[j] > H - 2:
            continue
        if b + dy[j] < 1 or b + dy[j] > W - 2:
            continue

        if (a + dx[j], b + dy[j]) not in bm:
            bm[a + dx[j], b + dy[j]] = 0

        bm[a + dx[j], b + dy[j]] += 1

    return res

if __name__ == '__main__':
    solve()
Buggy python submission (verdict: Time Limit Exceeded):
number=10**9+7

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

c.sort(reverse=True)
sum=0
for i in range(1, n+1):
    sum=(sum+(4**(n-1))*(i+1)*c[i-1])%number
print(sum)


Fixed submission:

number=10**9+7

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

c.sort(reverse=True)
sum=0
for i in range(1, n+1):
    sum=(sum+(pow(4, (n-1), number))*(i+1)*c[i-1])%number
print(sum)

Buggy python submission (verdict: Time Limit Exceeded):
number=10**9+7

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

c=sorted(c, reverse=True)
sum=0
for i in range(1, n+1):
    sum=(sum+(4**(n-1))*(i+1)*c[i-1])%number
print(sum)


Fixed submission:

number=10**9+7

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

c.sort(reverse=True)
sum=0
for i in range(1, n+1):
    sum=(sum+(pow(4, (n-1), number))*(i+1)*c[i-1])%number
print(sum)

Buggy python submission (verdict: Time Limit Exceeded):
number=10**9+7

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

c=sorted(c, reverse=True)
sum=0
for i in range(1, n+1):
    sum=(sum+(4**(n-1))*(i+1)*c[i-1])%number
print(sum)


Fixed submission:

number=10**9+7

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

c.sort(reverse=True)
sum=0
for i in range(1, n+1):
    sum=(sum+(pow(4, (n-1), number))*(i+1)*c[i-1])%number
print(sum)
Buggy python submission (verdict: Runtime Error):
mod=10**9+7
n, k=map(int, input().split())
a=list(map(int, input().split()))
jibun=0
for i in range(n):
    for j in range(i+1, n):
        if a[i]>a[j]:
            jibun=jibun+1

saki=0
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            saki=saki+1
ans=0

print((jibun*k)%mod+int((1/2)*saki*k*(k-1))%mod)%mod)


Fixed submission:
mod=10**9+7
n, k=map(int, input().split())
a=list(map(int, input().split()))
jibun=0
for i in range(n-1):
    for j in range(i+1, n):
        if a[i]>a[j]:
            jibun=(jibun+1)%mod

saki=0
for i in range(n):
    for j in range(n):
        if a[i]>a[j]:
            saki=(saki+1)%mod

ans=jibun*k+saki*k*(k-1)//2
print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int, input().split()))
x=[0 for i in range(n)]
sum=0
for i in range(n):
    if i%2==0:
        sum=sum+a[i]
    else:
        sum=sum-a[i]

x[0]=sum//2

for i in range(1, n):
    x[i]=a[i-1]-x[i-1]

ans=""
for i in range(n):
    ans=ans+str(x[i]*2)+" "
print(ans)


Fixed submission:
n=int(input())
a=list(map(int, input().split()))
x=[0 for i in range(n)]
sum=0
for i in range(n):
    if i%2==0:
        sum=sum+a[i]
    else:
        sum=sum-a[i]

x[0]=sum//2

for i in range(1, n):
    x[i]=a[i-1]-x[i-1]

x=map(lambda t:t*2, x)
x=map(str, x)

ans=" ".join(x)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int, input().split()))
x=[0 for i in range(n)]
sum=0
for i in range(n):
    if i%2==0:
        sum=sum+a[i]
    else:
        sum=sum-a[i]

x[0]=sum//2

for i in range(1, n):
    x[i]=a[i-1]-x[i-1]

ans=""
for i in range(n):
    ans=ans+str(x[i]*2)+" "
print(ans)


Fixed submission:
n=int(input())
a=list(map(int, input().split()))
x=[0 for i in range(n)]
sum=0
for i in range(n):
    if i%2==0:
        sum=sum+a[i]
    else:
        sum=sum-a[i]

x[0]=sum//2

for i in range(1, n):
    x[i]=a[i-1]-x[i-1]

x=map(lambda t:t*2, x)
x=map(str, x)

ans=" ".join(x)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
#色々とメモリ使用量には気をつける
from collections import deque

n, m=map(int, input().split())
u_list=[]
v_list=[]
for i in range(m):
    u, v=map(int, input().split())
    u_list.append(u)
    v_list.append(v)
s, t=map(int, input().split())
queue=deque()
kenken=[]
for i in range(1, n+1):
    queue.append((i, 0))
    while(len(queue))!=0:
        target=queue.popleft()
        target_pos=target[0]
        target_val=target[1]
        for j in range(m):
            if u_list[j]==target_pos:
                if target_val+1==3:
                    kenken.append((i, v_list[j]))
                else:
                    queue.append((v_list[j], target_val+1))

use_edge=[1 for i in range(len(kenken))]

queue.append((s, 0))
while(len(queue)!=0):
    target=queue.popleft()
    target_pos=target[0]
    target_val=target[1]
    for j in range(m):
        if use_edge[j]:

            if kenken[j][0]==target_pos:
                if kenken[j][1]==t:
                    print(target_val+1)
                    sys.exit()
                else:
                    queue.append((kenken[j][1], target_val+1))
                    use_edge[j]=0
print(-1)


Fixed submission:
import sys
from collections import deque
n, m=map(int,input().split())
"""
頂点1~nを1~3nに3倍加する
"""
edges=[[] for i in range(3*n)]
for i in range(m):
    """
    uからvへの枝を
    uからv+n, u+nからv+2n, u+2nからv+3n
    とする
    (枝を3倍加)
    """
    u, v=map(int, input().split())
    u, v=u-1, v-1
    edges[u].append(v+n)
    edges[u+n].append(v+2*n)
    edges[u+2*n].append(v)
s, t=map(int, input().split())
s, t=s-1, t-1
q=deque()
q.append(s)
dist=[-1]*(3*n)
dist[s]=0
"""
結局求めるものは，s~tへの最短距離を3で割ったもの
"""
while len(q)!=0:
    fr=q.popleft()
    for to in edges[fr]:
        #もし行ったことがなければ
        if dist[to]==-1:
            dist[to]=dist[fr]+1
            q.append(to)
print(dist[t]//3)
Buggy python submission (verdict: Runtime Error):
modulo=10**9+7
n, m=map(int, input().split())
a_list=[]
for i in range(m):
    a=int(input())
    a_list.append(a)
dp=[0 for i in range(n+1)]#0~n
dp[0]=1
if a_list[0]==1:
    dp[1]=0
else:
    dp[1]=1

for i in range(2, n+1):
    if not i in a_list:
        dp[i]=(dp[i-2]+dp[i-1])%modulo
print(dp[n]%modulo)


Fixed submission:
modulo=10**9+7
n, m=map(int, input().split())
a_list=[]
for i in range(m):
    a=int(input())
    a_list.append(a)
a_list.append(-1)
dp=[0 for i in range(n+1)]#0~n
dp[0]=1
if a_list[0]==1:
    dp[1]=0
    j=1
    for i in range(2, n+1):#10^5
        if i!=a_list[j]:
            dp[i]=(dp[i-2]+dp[i-1])%modulo
        else:
            j=j+1
else:
    dp[1]=1
    j=0
    for i in range(2, n+1):#10^5
        if i!=a_list[j]:
            dp[i]=(dp[i-2]+dp[i-1])%modulo
        else:
            j=j+1

print(dp[n]%modulo)

Buggy python submission (verdict: Runtime Error):
modulo=10**9+7
n, m=map(int, input().split())
a_list=[]
for i in range(m):
    a=int(input())
    a_list.append(a)
dp=[0 for i in range(n+1)]#0~n
dp[0]=1
if a_list[0]==1:
    dp[1]=0
else:
    dp[1]=1

for i in range(2, n+1):
    if not i in a_list:
        dp[i]=dp[i-2]+dp[i-1]
print(dp[n]%modulo)


Fixed submission:
modulo=10**9+7
n, m=map(int, input().split())
a_list=[]
for i in range(m):
    a=int(input())
    a_list.append(a)
a_list.append(-1)
dp=[0 for i in range(n+1)]#0~n
dp[0]=1
if a_list[0]==1:
    dp[1]=0
    j=1
    for i in range(2, n+1):#10^5
        if i!=a_list[j]:
            dp[i]=(dp[i-2]+dp[i-1])%modulo
        else:
            j=j+1
else:
    dp[1]=1
    j=0
    for i in range(2, n+1):#10^5
        if i!=a_list[j]:
            dp[i]=(dp[i-2]+dp[i-1])%modulo
        else:
            j=j+1

print(dp[n]%modulo)