Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    ans = 0
    base = 1
    for i in range(60):
        counter = [0, 0]
        buf = 0
        for j in range(N):
            if A[j] & (1 << i):
                buf += counter[0]
                counter[1] += 1
            else:
                buf += counter[1]
                counter[0] += 1
        ans += buf * base
        ans %= MOD
        base = (base * 2) % MOD
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    ans = 0
    base = 1
    for i in range(60):
        counter = [0, 0]
        buf = 0
        for j in range(N):
            if A[j] & (1 << i):
                buf += counter[0]
                counter[1] += 1
            else:
                buf += counter[1]
                counter[0] += 1
        ans += buf * base
        ans %= MOD
        base = (base * 2) % MOD
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):

    # DP1
    # 1からi番目の料理でj分以内に完食できる美味しさの合計の最大値
    DP1 = [[0 for _ in range(T+1)] for __ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP1[i][j] = max(DP1[i][j], DP1[i-1][j-A[i-1]]+B[i-1])
            DP1[i][j] = max(DP1[i][j], DP1[i-1][j], DP1[i][j-1])

    # DP2
    # i番目からN番目の料理でj分以内に完食できる美味しさの合計の最大値
    DP2 = [[0 for _ in range(T+1)] for __ in range(N+2)]
    for i in range(N, 0, -1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP2[i][j] = max(DP2[i][j], DP2[i+1][j-A[i-1]]+B[i-1])
            DP2[i][j] = max(DP2[i][j], DP2[i+1][j], DP2[i][j-1])

    # i番目以外の料理でT-1分以内に完食できる美味しさの合計の最大値
    ans = 0
    for i in range(1, N+1):
        bns = 0
        for j in range(T):
            bns = max(bns, DP1[i-1][j] + DP2[i+1][T-j-1])
        ans = max(ans, bns+B[i-1])
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):

    # DP1
    # 1からi番目の料理でj分以内に完食できる美味しさの合計の最大値
    DP1 = [[0 for _ in range(T+1)] for __ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP1[i][j] = max(DP1[i][j], DP1[i-1][j-A[i-1]]+B[i-1])
            DP1[i][j] = max(DP1[i][j], DP1[i-1][j], DP1[i][j-1])

    # DP2
    # i番目からN番目の料理でj分以内に完食できる美味しさの合計の最大値
    DP2 = [[0 for _ in range(T+1)] for __ in range(N+2)]
    for i in range(N, 0, -1):
        for j in range(1, T+1):
            if j-A[i-1] >= 0:
                DP2[i][j] = max(DP2[i][j], DP2[i+1][j-A[i-1]]+B[i-1])
            DP2[i][j] = max(DP2[i][j], DP2[i+1][j], DP2[i][j-1])

    # i番目以外の料理でT-1分以内に完食できる美味しさの合計の最大値
    ans = 0
    for i in range(1, N+1):
        bns = 0
        for j in range(T):
            bns = max(bns, DP1[i-1][j] + DP2[i+1][T-j-1])
        ans = max(ans, bns+B[i-1])
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
INF = float("inf")


def main():
    # bit DP
    N, M = map(int, input().split())
    a, b, c, d = [], [], [], []

    for i in range(M):
        a_, b_ = map(int, input().split())
        c_ = tuple(map(int, input().split()))
        d_ = 0
        for keta in c_:
            d_ |= 1 << keta-1
        a.append(a_)
        b.append(b_)
        c.append(c_)
        d.append(d_)

    DP = [INF]*(2**N)
    DP[0] = 0

    for i in range(M):
        DPnext = DP[:]
        for k in range(2**N):
            DPnext[k | d[i]] = min(DP[k | d[i]], DP[k]+a[i], DPnext[k | d[i]])
        DP = DPnext
    if DP[-1] == INF:
        print(-1)
    else:
        print(DP[-1])
    pass


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")


def main():
    # bit DP
    N, M = map(int, input().split())
    a, b, c, d = [], [], [], []

    for i in range(M):
        a_, b_ = map(int, input().split())
        c_ = tuple(map(int, input().split()))
        d_ = 0
        for keta in c_:
            d_ |= 1 << keta-1
        a.append(a_)
        b.append(b_)
        c.append(c_)
        d.append(d_)

    DP = [INF]*(2**N)
    DP[0] = 0

    for i in range(M):
        DPnext = DP[:]
        for k in range(2**N):
            DPnext[k | d[i]] = min(DP[k | d[i]], DP[k]+a[i], DPnext[k | d[i]])
        DP = DPnext
    if DP[-1] == INF:
        print(-1)
    else:
        print(DP[-1])
    pass


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
INF = float("inf")


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def solve(N: int, S: str):

    ans = 0
    for i in range(N-1):        # N
        z = z_algorithm(S[i:])  # N
        for j, zz in enumerate(z):  # N
            ans = max(min(j, zz), ans)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def solve(N: int, S: str):

    ans = 0
    for i in range(N-1):        # N
        z = z_algorithm(S[i:])  # N
        for j, zz in enumerate(z):  # N
            ans = max(min(j, zz), ans)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
INF = float("inf")

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        s, t = edge
        self.E[s].append(t)


def solve(N: int, A: "List[List[int]]"):
    a_head = [0]*N
    stack = list(range(N))
    next_stack = []
    day = -1
    flag = True
    g = Graph(N)

    while flag:
        day += 1
        g.E = [[] for _ in range(N)]
        flag = False

        for i in stack:
            h = a_head[i]
            if h == N-1:
                continue
            if i in g.E[A[i][h]-1]:
                a_head[i] += 1
                a_head[A[i][h]-1] += 1
                flag = True
                next_stack.append(i)
                next_stack.append(A[i][h]-1)
                g.E[A[i][h]-1].remove(i)
            else:
                g.add_edge([i, A[i][h]-1])
        stack = next_stack[:]

    for h in a_head:
        if h != N-1:
            print(-1)
            return
    print(day)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(S: str, T: str):
    print(sum([s == t for s, t in zip(S, T)]))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(S, T)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
INF = float("inf")


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    for i in range(1, N):
        if i+Z[i-c] < c+Z[c]:
            Z[i] = Z[i-c]
        else:
            j = max(0, c+Z[c]-i)
            while i+j < N and S[j] == S[i+j]:
                j += 1
            Z[i] = j
            c = i
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    print([i-N-1 for i in range(len(conc)) if Z[i] == N])


def argmax(a):
    m, n = -(1 << 31), -1
    for i, v in enumerate(a):
        if m < v:
            m, n = v, i
    return m, n


def solve(s: str, t: str):

    T = len(t)
    S = len(s)
    counter = 0
    curr = 0
    head = 0
    updated = True
    while updated:
        updated = False
        for i, c in enumerate(s):
            if c == t[curr]:
                curr += 1
                updated = True
                if curr == T:
                    counter += i
                    break
        if curr == T:
            break
        else:
            counter += S
    if updated == False:
        print(-1)
    else:
        print(counter+1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from bisect import bisect_left
from collections import defaultdict
INF = float("inf")


def solve(s: str, t: str):

    S = len(s)
    T = len(t)
    ABC = defaultdict(list)
    for i, c in enumerate(s):
        ABC[c].append(i)

    counter = 0
    head = 0
    # print(ABC)
    for tt in t:
        if len(ABC[tt]) == 0:
            print(-1)
            return
        j = bisect_left(ABC[tt], head) % len(ABC[tt])
        counter += (ABC[tt][j]-head) % S + 1
        # print(tt, ABC[tt], j, ABC[tt][j], "head:",
        # head, ",counter:", counter, S)
        head = (ABC[tt][j]+1) % S
    print(counter)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    solve(s, t)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
INF = float("inf")

import math


class SegmentTree(object):
    # セグメント木

    def __init__(self, N):
        """サイズNの配列を元にしたセグメント木
        """
        # 単位元
        self.idelem = -INF
        # 比較関数
        self.func = max

        self.N0 = 2**(math.ceil(math.log2(N)))
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        """k番目の値をxに更新
        """
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        """区間[l, r)の最大
        """
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s

    def __str__(self):
        return str(self.tree[self.N0-1:-1])


def solve(N: int, A: "List[int]"):
    st = SegmentTree(N)
    for i, a in enumerate(A):
        st.update(i, a)
    print(st.query(1, N))
    for i in range(1, N-1):
        print(max(st.query(0, i), st.query(i+1, N)))
    print(st.query(0, N-1))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")


def argmax(a):
    m, n = -(1 << 31), -1
    for i, v in enumerate(a):
        if m < v:
            m, n = v, i
    return m, n


def solve(N: int, A: "List[int]"):
    m, mi = argmax(A)
    m2, mi2 = argmax(A[:mi]+A[mi+1:])
    for i in range(N):
        if i == mi:
            print(m2)
        else:
            print(m)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
INF = float("inf")
 
 
def solve(N: int, A: "List[int]"):
 
    a = [-INF]
 
    def isOK(index, key):
        return a[index] < key
 
    def binary_search(key):
        ng = -1
        ok = len(a)
 
        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok
 
    ans = 0
    for aval in A:
        ok = binary_search(aval)
        # print(a, a[ok])
        if a[ok] == -INF:
            ans += 1
        a.insert(ok, aval)
    print(ans)
    return
 
 
def main():
 
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)
 
 
if __name__ == '__main__':
    main()

Fixed submission:
#!/usr/bin/env python3
import sys
from bisect import bisect_right

INF = float("inf")


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    dp = [INF]*N
    for i in range(N):
        j = bisect_right(dp, -A[i])
        dp[j] = -A[i]

    print(sum([1 for d in dp if d < INF]))
    # print(dp)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections import deque

INF = float("inf")


def solve(N: int, A: "List[int]"):

    a = deque([-INF])

    def isOK(index, key):
        return a[index] < key

    def binary_search(key):
        ng = -1
        ok = len(a)

        while abs(ok - ng) > 1:
            mid = (ok + ng)//2
            if isOK(mid, key):
                ok = mid
            else:
                ng = mid
        return ok

    ans = 0
    for aval in A:
        ok = binary_search(aval)
        # print(a, a[ok])
        if a[ok] == -INF:
            ans += 1
        a.insert(ok, aval)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from bisect import bisect_right

INF = float("inf")


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]

    dp = [INF]*N
    for i in range(N):
        j = bisect_right(dp, -A[i])
        dp[j] = -A[i]

    print(sum([1 for d in dp if d < INF]))
    # print(dp)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
from collections import deque
from collections import defaultdict
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    # 枝
    edges = defaultdict(list)
    for from_, to_ in zip(a, b):
        edges[from_].append(to_)
        edges[to_].append(from_)

    # 色を決定済みかどうか
    flag = [False]*(N+1)

    def recur(n, preK, prepreK):
        count = 1
        count *= K-preK-prepreK
        count %= MOD
        flag[n] = True
        if edges[n] == 1:
            print(n, preK, prepreK, count)
            return count
        else:
            e = [ee for ee in edges[n] if flag[ee] is False]
            for i, to_ in enumerate(e):
                count *= recur(to_, 1, preK+i)
                count %= MOD
            return count

    print(recur(1, 0, 0) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(100000)
from collections import deque
from collections import defaultdict
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    # 枝
    edges = defaultdict(list)
    for from_, to_ in zip(a, b):
        edges[from_].append(to_)
        edges[to_].append(from_)

    # 色を決定済みかどうか
    flag = [False]*(N+1)

    def recur(n, preK, prepreK):
        count = 1
        count *= K-preK-prepreK
        count %= MOD
        flag[n] = True
        if edges[n] == 1:
            print(n, preK, prepreK, count)
            return count
        else:
            e = [ee for ee in edges[n] if flag[ee] is False]
            for i, to_ in enumerate(e):
                count *= recur(to_, 1, preK+i)
                count %= MOD
            return count

    print(recur(1, 0, 0) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
INF = float("inf")
import bisect
from collections import Counter
from collections import defaultdict
MOD = 1000000007  # type: int


def solve(N: int, M: int, S: "List[int]", T: "List[int]"):

    DP = [[1]*(N+1) for _ in range(M+1)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            DP[j][i] = DP[j-1][i] + DP[j][i-1] - \
                DP[j-1][i-1]
            DP[j][i] %= MOD

            if S[i-1] == T[j-1]:
                DP[j][i] += DP[j-1][i-1]
                DP[j][i] %= MOD
    # print(*DP, sep="\n")
    print(DP[M][N])


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    T = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, S, T)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
INF = float("inf")
MOD = 1000000007  # type: int


def solve(N: int, M: int, S: "List[int]", T: "List[int]"):

    DP = [[1]*(N+1) for _ in range(M+1)]
    for i in range(1, N+1):
        for j in range(1, M+1):
            DP[j][i] = DP[j-1][i] + DP[j][i-1] - \
                DP[j-1][i-1]
            DP[j][i] %= MOD

            if S[i-1] == T[j-1]:
                DP[j][i] += DP[j-1][i-1]
                DP[j][i] %= MOD
    # print(*DP, sep="\n")
    print(DP[M][N])


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    T = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, S, T)


if __name__ == '__main__':
    main()