Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
from operator import xor

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

MOD = 10**9 + 7

acc = list(accumulate(A, xor))
M = max(acc)
dp = [[0, 0, 0] for _ in range(M + 1)]
U = set()
z = 0
for x in acc:
    if x == 0:
        z += 1
        for u in U:
            dp[u][1] = (dp[u][1] + dp[u][0]) % MOD
        U = set()
    else:
        if dp[x][2] < z:
            dp[x][1] = ((z - dp[x][2]) * dp[x][1]) % MOD
            dp[x][2] = z
        dp[x][0] = (dp[x][0] + dp[x][1] + 1) % MOD
        U.add(x)
ans = (
    dp[acc[-1]][1] + 1 if acc[-1] != 0 else
    sum(dp[x][0] for x in range(1, M + 1)) + pow(2, acc.count(0) - 1, MOD)
) % MOD

# 出力
print(ans)


Fixed submission:
from itertools import accumulate
from operator import xor

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

MOD = 10**9 + 7

acc = list(accumulate(A, xor))
M = max(acc)
dp = [[0, 0, 0] for _ in range(M + 1)]
z = 0
for x in acc:
    if x == 0:
        z += 1
    else:
        dp[x][1] = (dp[x][1] + (z - dp[x][2]) * dp[x][0]) % MOD
        dp[x][0] = (dp[x][0] + dp[x][1] + 1) % MOD
        dp[x][2] = z
for x in range(1, M + 1):
    dp[x][1] = (dp[x][1] + (z - dp[x][2]) * dp[x][0]) % MOD
ans = (
    dp[acc[-1]][1] + 1 if acc[-1] != 0 else
    sum(dp[x][0] for x in range(1, M + 1)) + pow(2, acc.count(0) - 1, MOD)
) % MOD

# 出力
print(ans)
Buggy python submission (verdict: Runtime Error):
from itertools import groupby, accumulate

# 入力
N, K = map(int, input().split())
S = input()

# 連続する0または1の数に関する累積和
A = list(accumulate(len(list(seq)) for _, seq in groupby(S))) + [N]
m = (
    1 if S[0] == '0' else
    0
)
# 累積和を用いて解を求める
ans = (
    max(
        A[2 * K - 1],
        A[-1] - A[-(2 * K)],
        max(
            (
                a - b
                for a, b in zip(A[(2 * K + m)::2], ([0] + A)[m::2])
            ),
            default=0
        )
    ) if m < len(A) else
    A[-1]
)

# 出力
print(ans)


Fixed submission:
from itertools import groupby, accumulate

# 入力
N, K = map(int, input().split())
S = input()

# 連続する0または1の数に関する累積和
A = list(accumulate(len(list(seq)) for _, seq in groupby(S))) + [N]
m = (
    1 if S[0] == '0' else
    0
)
# 累積和を用いて解を求める
ans = (
    max(
        A[min(2 * K - 1, len(A) - 1)],
        A[-1] - A[max(-(2 * K), -len(A))],
        max(
            (
                a - b
                for a, b in zip(A[(2 * K + m)::2], ([0] + A)[m::2])
            ),
            default=0
        )
    ) if m < len(A) else
    A[-1]
)

# 出力
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce

# 入力
N, Q = map(int, input().split())
s = input()
t, d = zip(*(input().split() for _ in range(Q)))


# めぐる式二分法
def bis(p, ok=-1, ng=10**18):
    mid = (ok + ng) // 2
    return (
        ok if abs(ok - ng) == 1 else
        bis(p, mid, ng) if p(mid) else
        bis(p, ok, mid)
    )


# Q回の呪文詠唱後、マスiにいたゴーレムが移動したマス。ただし、
# 0の場合、マス1から左に移動しようとして消滅したことを、
# N + 1の場合、マスNから右に移動しようとして消滅したことを表す。
def f(i):
    return reduce(
        lambda j, q: (
            0 if j == 0 else
            j - 1 if 1 <= j <= N and s[j - 1] == q[0] and q[1] == 'L' else
            j if 1 <= j <= N and s[j - 1] != q[0] else
            j + 1 if 1 <= j <= N and s[j - 1] == q[0] and q[1] == 'R' else
            N + 1
        ),
        zip(t, d),
        i
    )


# 二分法により、マス1から左に移動しようとして消滅したゴーレムの数と
# マスNから右に移動しようとして消滅したゴーレムの数の和を求める
ans = (
    bis(lambda i: f(i) == N + 1, ok=N + 1, ng=0) -
    bis(lambda i: f(i) == 0, ok=0, ng=N + 1) -
    1
)
print(ans)


Fixed submission:
N, Q = map(int, input().split())
s = input()
t, d = zip(*(input().split() for _ in range(Q)))


def f(i):
    i -= 1
    if i < 0:
        return -1
    if i >= N:
        return 1
    for j in range(Q):
        if s[i] == t[j]:
            i += 1 if d[j] == 'R' else -1
        if i < 0:
            return -1
        elif i >= N:
            return 1
    return 0


h, l = N + 1, 1
while h > l:
    i = (h + l) // 2
    r = f(i)
    if r == 1:
        h = i
    else:
        l = i + 1

ans = N - h + 1

h, l = N, 0
while h > l:
    i = (h + l + 1) // 2
    r = f(i)
    if r == -1:
        l = i
    else:
        h = i - 1

ans = N - ans - l

print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
a, b = zip(*(map(int, input().split()) for _ in range(M)))


G = [set() for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x].add(y)
    G[y].add(x)


# 次数4の頂点間のパスの数が4でないならばTrueを返す
def f():
    assert 0
    x, y = (i for i in range(1, N + 1) if len(G[i]) == 4)
    q = []
    dp = [0 for _ in range(N + 1)]
    q.append(x)
    dp[x] = 1
    while q:
        i = q.pop()
        for j in G[i]:
            if j == y or dp[j] == 0:
                dp[j] += 1
                q.append(j)
    return dp[y] != 4


# 以下のいずれかを満たすならば、かつ、そのときに限りYes
# - 次数4の頂点間を結ぶ異なる4つのパスが存在しない場合
# - 各頂点の次数は2または4であり、次数4の頂点は3個存在する場合
# - 各頂点の次数は偶数であり、次数が6以上の頂点が存在する場合
ans = (
    'Yes' if (
        all(len(G[i]) % 2 == 0 for i in range(1, N + 1)) and
        (
            any(len(G[i]) >= 6 for i in range(1, N + 1)) or
            sum(len(G[i]) == 4 for i in range(1, N + 1)) >= 3 or
            sum(len(G[i]) == 4 for i in range(1, N + 1)) == 2 and f()
        )
    ) else
    'No'
)

print(ans)


Fixed submission:
N, M = map(int, input().split())
a, b = zip(*(map(int, input().split()) for _ in range(M)))


G = [set() for _ in range(N + 1)]
for x, y in zip(a, b):
    G[x].add(y)
    G[y].add(x)


# 次数4の頂点間のパスの数が4でないならばTrueを返す
def f():
    x, y = (i for i in range(1, N + 1) if len(G[i]) == 4)
    q = []
    dp = [0 for _ in range(N + 1)]
    q.append(x)
    dp[x] = 1
    while q:
        i = q.pop()
        for j in G[i]:
            if j != y and dp[j] == 0:
                q.append(j)
            dp[j] += 1
    return dp[y] != 4


# 以下のいずれかを満たすならば、かつ、そのときに限りYes
# - 次数4の頂点間を結ぶ異なる4つのパスが存在しない場合
# - 各頂点の次数は2または4であり、次数4の頂点は3個存在する場合
# - 各頂点の次数は偶数であり、次数が6以上の頂点が存在する場合
ans = (
    'Yes' if (
        all(len(G[i]) % 2 == 0 for i in range(1, N + 1)) and
        (
            any(len(G[i]) >= 6 for i in range(1, N + 1)) or
            sum(len(G[i]) == 4 for i in range(1, N + 1)) >= 3 or
            sum(len(G[i]) == 4 for i in range(1, N + 1)) == 2 and f()
        )
    ) else
    'No'
)

print(ans)
Buggy python submission (verdict: Runtime Error):
from bisect import bisect_right
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
xs = [int(input()) for i in range(Q)]
for x in xs:
    x = int(input())
    b, d = bisect_right(s, x), bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)


Fixed submission:
from bisect import bisect

A, B, Q = map(int, input().split())
s = [-10**15]
t = [-10**15]
for _ in range(A):
    s.append(int(input()))
s.append(10**15)
for _ in range(B):
    t.append(int(input()))
t.append(10**15)
x = list(map(int, (input() for _ in range(Q))))
for y in x:
    i = bisect(s, y)
    j = bisect(t, y)
    ans = min(
        max(abs(s[i] - y), abs(t[j] - y)),
        max(abs(s[i - 1] - y), abs(t[j - 1] - y)),
        2 * min(abs(s[i] - y), abs(t[j - 1] - y)) + max(abs(s[i] - y), abs(t[j - 1] - y)),
        2 * min(abs(s[i - 1] - y), abs(t[j] - y)) + max(abs(s[i - 1] - y), abs(t[j] - y))
    )
    print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
from functools import lru_cache
sys.setrecursionlimit(2*10**4)

# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))

INF = 10**15
# 各数字の消費マッチ棒
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)


# N=nのときの解に対応するベクトルを返す
@lru_cache(maxsize=None)
def dfs(n):
    return (
        [-INF for _ in range(9)] if n < 0 else
        [0 for _ in range(9)] if n == 0 else
        max(
            (
                [
                    t + 1 if i == a else t
                    for i, t in enumerate(dfs(n - C[a]), start=1)
                ]
                for a in A
            ),
            key=lambda x: [sum(x)] + list(reversed(x))
        )
    )


# 出力
ans = ''.join(str(a) * dfs(N)[a - 1] for a in sorted(A, reverse=True))
print(ans)


Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)

dp = [[0 for _ in range(10)] for _ in range(N + 1)]
dp2 = [-100 for _ in range(N + 1)]
dp2[0] = 0

for i in range(2, N+1):
    x = -1
    opt = -1
    for a in A:
        c = C[a]
        if i >= c and (dp2[i - c] > opt or (dp2[i - c] == opt and a > x)):
            x = a
            opt = dp2[i - c]
    if x == -1:
        continue
    dp2[i] = dp2[i - C[x]] + 1
    c = C[x]
    for a in A:
        if x == a:
            dp[i][a] = dp[i - c][a] + 1
        else:
            dp[i][a] = dp[i - c][a]

ans = ''.join(str(a) * dp[N][a] for a in sorted(A, reverse=True))
print(ans)

Buggy python submission (verdict: Runtime Error):
from functools import lru_cache

# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))

INF = 10**15
# 各数字の消費マッチ棒
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)


# N=nのときの解に対応するベクトルを返す
@lru_cache(maxsize=None)
def dfs(n):
    return (
        [-INF for _ in range(9)] if n < 0 else
        [0 for _ in range(9)] if n == 0 else
        max(
            (
                [
                    t + 1 if i == a else t
                    for i, t in enumerate(dfs(n - C[a]), start=1)
                ]
                for a in A
            ),
            key=lambda x: [sum(x)] + list(reversed(x))
        )
    )

# 出力
ans = ''.join(str(a) * dfs(N)[a - 1] for a in sorted(A, reverse=True))
print(ans)


Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
C = (100, 2, 5, 5, 4, 5, 6, 3, 7, 6)

dp = [[0 for _ in range(10)] for _ in range(N + 1)]
dp2 = [-100 for _ in range(N + 1)]
dp2[0] = 0

for i in range(2, N+1):
    x = -1
    opt = -1
    for a in A:
        c = C[a]
        if i >= c and (dp2[i - c] > opt or (dp2[i - c] == opt and a > x)):
            x = a
            opt = dp2[i - c]
    if x == -1:
        continue
    dp2[i] = dp2[i - C[x]] + 1
    c = C[x]
    for a in A:
        if x == a:
            dp[i][a] = dp[i - c][a] + 1
        else:
            dp[i][a] = dp[i - c][a]

ans = ''.join(str(a) * dp[N][a] for a in sorted(A, reverse=True))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 入力
N, K = map(int, input().split())
A = list(map(int, input().split()))


# MSBから順に0or1を決めていく
# 0にする場合、下位ビットの最適値は貪欲に求まる
def s(i):
    return sum((a >> (i - 1)) & 1 for a in A)


def g(L, b):
    return (
        0 if b == 0 else
        g(L, b - 1) + 2**(b - 1) * s(b) if L < 2**(b - 1) else
        g(L >> 1, b - 1) + 2**(b - 1) * max(
            s(b),
            N - s(b)
        ) if L == (2**b - 1) else
        max(
            g(2**(b - 1) - 1, b - 1) + 2**(b - 1) * s(b),
            g(L - 2**(b - 1), b - 1) + 2**(b - 1) * (N - s(b))
        )
    )


ans = g(K, max(K, *A).bit_length())

# 出力
print(ans)


Fixed submission:
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = K.bit_length()
b = [sum((a >> k) & 1 for a in A) for k in range(m)]
opt = [0] + list(accumulate(1 << k if 2 * b[k] < N else 0 for k in range(m)))


def f(x):
    return sum(x ^ a for a in A)


def g(k, s):
    if k == 0:
        return f(s)
    r = k.bit_length()
    return max(
      f(s + opt[r - 1]),
      g(k - (1 << (r - 1)), s + (1 << (r - 1)))
    )


ans = g(K, 0)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
h = list(map(int, input().split()))


# 貪欲に極大区間に対して水やりする
def f(y):
    L = next(
        (
            i
            for i, x in enumerate(y)
            if x > 0
        ),
        N
    )
    R = next(
        (
            i
            for i, x in enumerate(y[L:], L)
            if x == 0
        ),
        N
    )
    return (
        0 if L == N else
        1 + f(
            [x for x in y[:L]] +
            [x - 1 for x in y[L:R]] +
            [x for x in y[R:]]
        )
    )


ans = f(h)

print(ans)


Fixed submission:
N = int(input())
h = list(map(int, input().split()))
ans = 0
while max(h) > 0:
    k = 0
    flag = False
    for i in range(N):
        if h[i] > 0:
            h[i] -= 1
            flag = True
        elif flag:
            k += 1
            flag = False
    if flag:
        k += 1
    ans += k

print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
P, Y = zip(*(map(int, input().split()) for _ in range(M)))
ans = ['' for _ in range(M)]
c = [1 for _ in range(N + 1)]
for i, t in sorted(enumerate(zip(P, Y)), key=lambda t: t[1][1]):
    ans[i] = f'{t[0]:06}{c[t[0]]:06}'
    c[t[0]] += 1
print('\n'.join(ans))

Fixed submission:
N, M = map(int, input().split())
P, Y = zip(*(map(int, input().split()) for _ in range(M)))
ans = ['' for _ in range(M)]
c = [1 for _ in range(N + 1)]
for i, t in sorted(enumerate(zip(P, Y)), key=lambda t: t[1][1]):
    ans[i] = '{:06}{:06}'.format(t[0], c[t[0]])
    c[t[0]] += 1
print('\n'.join(ans))
Buggy python submission (verdict: Runtime Error):
%%test_input https://abc108.contest.atcoder.jp/tasks/abc108_b
x1, y1, x2, y2 = map(int, input().split())
dx = x2 - x1
dy = y2 - y1
x3, y3 = x2 - dy, y2 + dx
x4, y4 = x3 - dx, y3 - dy
print('{} {} {} {}'.format(x3, y3, x4, y4))

Fixed submission:
x1, y1, x2, y2 = map(int, input().split())
dx = x2 - x1
dy = y2 - y1
x3, y3 = x2 - dy, y2 + dx
x4, y4 = x3 - dx, y3 - dy
print('{} {} {} {}'.format(x3, y3, x4, y4))
Buggy python submission (verdict: Runtime Error):
%%test_input https://abc108.contest.atcoder.jp/tasks/abc108_c
N, K = map(int, input().split())
ans = sum(((N + a % K) // K)**2 for a in range(1, N + 1) if (2 * a) % K == 0)
print(ans)

Fixed submission:
N, K = map(int, input().split())
ans = sum(((N + a % K) // K)**2 for a in range(1, N + 1) if (2 * a) % K == 0)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

# 入力
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

# (i + j) % 3 = k のマスを色cに塗り替える際の違和感の和
dp = {
    k: [
        sum(
            D[c[i][j] - 1][k - 1] if (i + j) % 3 == m else
            0
            for i in range(N)
            for j in range(N)
        )
        for m in range(3)
    ]
    for k in range(1, C + 1)
}

# dpを用いて全探索し解を得る
ans = min(
    dp[i][0] + dp[j][1] + dp[k][2]
    for i, j, k in permutations(range(1, C + 1), 3)
)

# 出力
print(ans)


Fixed submission:
from itertools import permutations

# 入力
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

# (i + j) % 3 = k のマスを色cに塗り替える際の違和感の和
dp = {
    k: [
        sum(
            D[c[i][j] - 1][k - 1] if (i + j) % 3 == m else
            0
            for i in range(N)
            for j in range(N)
        )
        for m in range(3)
    ]
    for k in range(1, C + 1)
}

# dpを用いて全探索し解を得る
ans = min(
    dp[i][0] + dp[j][1] + dp[k][2]
    for i, j, k in permutations(range(1, C + 1), 3)
)

# 出力
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
x = []
acc = 0
ans = 0
for a in A:
    while acc & a:
        acc ^= x.pop(0)
    x.append(a)
    acc ^= a
    ans += len(x)
print(ans)


Fixed submission:
from collections import deque
N = int(input())
A = list(map(int, input().split()))
x = deque()
acc = 0
ans = 0
for a in A:
    while acc & a:
        acc ^= x.popleft()
    x.append(a)
    acc ^= a
    ans += len(x)
print(ans)
Buggy python submission (verdict: Runtime Error):
# 入力
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))

INF = 10**20

# Y = A_1, .., A_N のときの X - Y の最小値を求める
# Y を決め打つと、 X - Y の最小値はO(NlogN)で求められる


def f(b):
    i = 0
    T = []
    while i < N:
        S = []
        while i < N and A[i] >= b:
            S.append(A[i])
            i += 1
        if len(S) >= K:
            T.extend(sorted(S)[:(len(S) - K + 1)])
        i += 1
    return (
        sorted(T)[Q - 1] if len(T) >= Q else
        INF
    )


ans = min(f(b) - b for b in B)

# 出力
print(ans)


Fixed submission:
# 入力
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))

INF = 10**20

# Y = A_1, .., A_N のときの X - Y の最小値を求める
# Y を決め打つと、 X - Y の最小値はO(NlogN)で求められる


def f(b):
    i = 0
    T = []
    while i < N:
        S = []
        while i < N and A[i] >= b:
            S.append(A[i])
            i += 1
        if len(S) >= K:
            T.extend(sorted(S)[:(len(S) - K + 1)])
        i += 1
    return (
        sorted(T)[Q - 1] if len(T) >= Q else
        INF
    )


ans = min(f(a) - a for a in sorted(A))

# 出力
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
p = [0] + list(map(int, input().split()))
x, y = zip(*(map(int, input().split()) for _ in range(M)))
E = [[] for _ in range(N + 1)]
for a, b in zip(x, y):
    E[a].append(b)
    E[b].append(a)
v = [True for _ in range(N + 1)]


def f(i, P, Q):
    v[i] = False
    P.add(i)
    Q.add(p[i])
    for a in E[i]:
        if v[a]:
            f(a, P, Q)


ans = 0
for i in range(1, N + 1):
    if v[i]:
        P = set()
        Q = set()
        f(i, P, Q)
        ans += len(P & Q)
print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(2*10**5)

N, M = map(int, input().split())
p = [0] + list(map(int, input().split()))
x, y = zip(*(map(int, input().split()) for _ in range(M)))
E = [[] for _ in range(N + 1)]
for a, b in zip(x, y):
    E[a].append(b)
    E[b].append(a)
v = [True for _ in range(N + 1)]


def f(i, P, Q):
    v[i] = False
    P.add(i)
    Q.add(p[i])
    for a in E[i]:
        if v[a]:
            f(a, P, Q)


ans = 0
for i in range(1, N + 1):
    if v[i]:
        P = set()
        Q = set()
        f(i, P, Q)
        ans += len(P & Q)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 入力
N = int(input())
S = [list(input()) for _ in range(N)]

# 解は、B = 0として、A = 0, 1, ..., N - 1 のうち、よい盤面になるものの個数のN倍
ans = N * sum(
    all(
        S[i][j] == S[(j - A) % N][(i + A) % N]
        for i in range(N)
        for j in range(i + 1)
    )
    for A in range(N)
)

# 出力
print(ans)


Fixed submission:
# 入力
N = int(input())
S = [list(input()) for _ in range(N)]

# 解は、B = 0として、A = 0, 1, ..., N - 1 のうち、よい盤面になるものの個数のN倍
ans = N * sum(
    all(
        S[i][j] == S[(j - A) % N][(i + A) % N]
        for i in range(N)
        for j in range(N)
    )
    for A in range(N)
)

# 出力
print(ans)
Buggy python submission (verdict: Runtime Error):
H, W = tuple(map(int, input().split()))
s = [input() for _ in range(H)]
def f(q, h):
    if len(q) == 0:
        return float('inf')
    i, j, k = q[0]
    if i == H - 1 and j == W - 1:
        return k
    a = [(u, v)
         for u, v in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1))
         if 0 <= u < H and 0 <= v < W and s[u][v] == '.' and (u, v) not in h]
    _q = q[1:] + [(u, v, k + 1) for u, v in a]
    _h = h | set(a)
    return f(_q, _h)
print(max(-1, sum(t.count('.') for t in s) - f([(0, 0, 0)], {(0, 0)}) - 1))


Fixed submission:
H, W = tuple(map(int, input().split()))
s = [input() for _ in range(H)]
q = [(0, 0, 0)]
h = {(0, 0)}
opt = float('inf')
while q:
    i, j, k = q.pop(0)
    if i == H - 1 and j == W - 1:
        opt = k
        break
    a = [(u, v)
         for u, v in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1))
         if 0 <= u < H and 0 <= v < W and s[u][v] == '.' and (u, v) not in h]
    q += [(u, v, k + 1) for u, v in a]
    h |= set(a)
print(max(-1, sum(t.count('.') for t in s) - opt - 1))
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
E = [[] for i in range(N + 1)]
for _ in range(M):
    l, r, d = map(int, input().split())
    E[l].append((r, d))
    E[r].append((l, -d))
INF = 10**10
dp = [INF for i in range(N + 1)]


def dfs(i):
    for r, d in E[i]:
        if dp[r] == INF:
            dp[r] = dp[i] + d
            if not dfs(r):
                return False
        elif dp[r] != dp[i] + d:
            return False
    return True


for i in range(1, N + 1):
    if dp[i] == INF:
        dp[i] = 0
        if not dfs(i):
            print('No')
            break
else:
    print('Yes')


Fixed submission:
import sys
sys.setrecursionlimit(2*10**5)
N, M = map(int, input().split())
E = [[] for i in range(N + 1)]
for _ in range(M):
    l, r, d = map(int, input().split())
    E[l].append((r, d))
    E[r].append((l, -d))
INF = 10**10
dp = [INF for i in range(N + 1)]


def dfs(i):
    for r, d in E[i]:
        if dp[r] == INF:
            dp[r] = dp[i] + d
            if not dfs(r):
                return False
        elif dp[r] != dp[i] + d:
            return False
    return True


for i in range(1, N + 1):
    if dp[i] == INF:
        dp[i] = 0
        if not dfs(i):
            print('No')
            break
else:
    print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product, combinations

# 入力
N = int(input())
D = list(map(int, input().split()))

# N >=23 ならば鳩の巣原理より、max(s)=0である
# N <=22 ならば全探索で解を求める
ans = (
    0 if N >= 24 else
    max(
        int(len(set(t)) == N + 1) if N >= 12 else
        min(
            min(abs(a - b), 24 - abs(a - b))
            for a, b in combinations(t, 2)
        )
        for t in (
            product(
                (0,),
                *(
                    (d,) if d == 0 else
                    (d, 24 - d)
                    for d in D
                )
            )
        )
    )
)

# 出力
print(ans)


Fixed submission:
from itertools import product, combinations

# 入力
N = int(input())
D = list(map(int, input().split()))

# N >= 24 ならば鳩の巣原理より、max(s)=0である
# N <= 23 ならば全探索で解を求める
ans = (
    0 if N >= 24 else
    int(
        (0 not in D) and
        (D.count(12) <= 1) and
        all(
            D.count(i) <= 2
            for i in range(1, 12)
        )
    ) if 12 <= N < 24 else
    max(
        min(
            min(abs(a - b), 24 - abs(a - b))
            for a, b in combinations(t, 2)
        )
        for t in (
            product(
                (0,),
                *(
                    (d, 24 - d)
                    for d in D
                )
            )
        )
    )
)

# 出力
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product, combinations

# 入力
N = int(input())
D = list(map(int, input().split()))

# N >=23 ならば鳩の巣原理より、max(s)=0である
# N <=22 ならば全探索で解を求める
ans = (
    0 if N >= 24 else
    max(
        int(len(set(t)) == N + 1) if N >= 12 else
        min(
            min(abs(a - b), 24 - abs(a - b))
            for a, b in combinations(t, 2)
        )
        for t in (
            product(
                (0,),
                *(
                    (d,) if d == 0 else
                    (d, 24 - d)
                    for d in D
                )
            )
        )
    )
)

# 出力
print(ans)


Fixed submission:
from itertools import product, combinations

# 入力
N = int(input())
D = list(map(int, input().split()))

# N >= 24 ならば鳩の巣原理より、max(s)=0である
# N <= 23 ならば全探索で解を求める
ans = (
    0 if N >= 24 else
    int(
        (0 not in D) and
        (D.count(12) <= 1) and
        all(
            D.count(i) <= 2
            for i in range(1, 12)
        )
    ) if 12 <= N < 24 else
    max(
        min(
            min(abs(a - b), 24 - abs(a - b))
            for a, b in combinations(t, 2)
        )
        for t in (
            product(
                (0,),
                *(
                    (d, 24 - d)
                    for d in D
                )
            )
        )
    )
)

# 出力
print(ans)