Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def pre_order(E):
    # 有向グラフ上の深さ優先探索(DFS)
    # NlogNくらいありそう
    N = len(E)
    order = []
    parents = [-1]*N
    seen = [-1]*N
    looped = False
    q = [i for i in range(N) if len(E[i]) == 0]
    if not q:
        # これはループがあるケースだが
        q = [0]
        looped = True

    while q:
        v = q.pop()
        order.append(v)
        seen[v] = 1
        for u in E[v]:
            if seen[u] != -1:
                looped = True
                continue
            parents[u] = v
            q.append(u)
            seen[u] = 0
    return order, parents


def main():
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))

    def f(i, j):
        # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = [[] for _ in range(N*(N-1)//2)]
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            # fで書いていたけど遅いので、移す
            frm = f(i, A[i][j])
            to = f(i, A[i][j+1])
            out[frm].append(to)
    # print(out)

    # 閉路検出
    M = (N*(N-1)//2)

    order, parents, looped = pre_order(out)
    if looped:
        print(-1)
        return

    # 最長パスを得る
    # パスは自分より下位の情報が必要なので、post_orderで見る
    depth = [-1]*M
    longest = -1

    for i in reversed(order):
        if depth[i] == -1:
            depth[i] = 1
        for u in out[i]:
            depth[i] = max(depth[i], 1+depth[u])
        longest = max(depth[i], longest)
    print(longest)
    return


if __name__ == '__main__':
    main()


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


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        # print(indices)
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))

    def f(i, j):
        # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = [[] for _ in range(N*(N-1)//2)]
    inn = [[] for _ in range(N*(N-1)//2)]
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            # fで書いていたけど遅いので、移す
            a = i
            b = A[i][j]
            if a > b:
                a, b = b, a
            frm = b-1+(N-2)*a-a*(a-1)//2
            a = i
            b = A[i][j+1]
            if a > b:
                a, b = b, a
            to = b-1+(N-2)*a-a*(a-1)//2
            out[frm].append(to)
            inn[to].append(frm)
    # print(out)

    # 閉路検出
    # 始点からのパスを保持しながらDFSする
    hist = [False]*(N*(N-1)//2)

    def dfs(v):
        hist[v] = True
        longpath = 1
        longlast = v
        for u in out[v]:
            if hist[u] is False:
                curr, last = dfs(u)
                if 1+curr > longpath:
                    longpath = 1+curr
                    longlast = last
            else:
                return INF, -1
        hist[v] = False
        return longpath, longlast

    longest, last = dfs(f(0, A[0][0]))
    if longest == INF:
        print(-1)
        return

    def dfs2(v):
        hist[v] = True
        longpath = 1
        longlast = v
        for u in inn[v]:
            if hist[u] is False:
                curr, last = dfs2(u)
                if 1+curr > longpath:
                    longpath = 1+curr
                    longlast = last
            else:
                return INF, -1
        hist[v] = False
        return longpath, longlast

    longest, last = dfs2(last)
    if longest == INF:
        print(-1)
        return
    else:
        print(longest)
    return


if __name__ == '__main__':
    main()


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


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        # print(indices)
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from collections import defaultdict
from itertools import product
INF = float("inf")


def main():
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))

    def f(i, j):
        # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
        if i > j:
            i, j = j, i
        return j-1 + (N-2)*i-i*(i-1)//2

    out = defaultdict(list)
    inn = defaultdict(list)
    # 対戦カードをノードとみなし、閉路検出と最長パス探索を行う
    for i in range(N):
        for j in range(N-2):
            out[f(i, A[i][j])].append(f(i, A[i][j+1]))
            inn[f(i, A[i][j+1])].append(f(i, A[i][j]))
    # print(out)

    # 閉路検出
    # 始点からのパスを保持しながらDFSする
    hist = [False]*(N*(N-1)//2)

    def dfs(v):
        hist[v] = True
        longpath = 1
        longlast = v
        for u in out[v]:
            if hist[u] is False:
                curr, last = dfs(u)
                if 1+curr > longpath:
                    longpath = 1+curr
                    longlast = last
            else:
                return INF, -1
        hist[v] = False
        return longpath, longlast

    longest, last = dfs(f(0, A[0][0]))
    if longest == INF:
        print(-1)
        return

    def dfs2(v):
        hist[v] = True
        longpath = 1
        longlast = v
        for u in inn[v]:
            if hist[u] is False:
                curr, last = dfs2(u)
                if 1+curr > longpath:
                    longpath = 1+curr
                    longlast = last
            else:
                return INF, -1
        hist[v] = False
        return longpath, longlast

    longest, last = dfs2(last)
    if last == INF:
        print(-1)
        return
    else:
        print(longest)
    return


if __name__ == '__main__':
    main()


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


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        # print(indices)
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/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
    battle = [True]*N
    next_battle = battle[:]

    day = -1
    g = Graph(N)

    while True:
        day += 1
        flag = False

        battle[:] = next_battle
        for i, h in enumerate(a_head):
            # print(battle)
            if h == N-1:
                continue
            if battle[i] == True:
                next_battle[i] = False
            else:
                continue
            # print("day:{}, {}, {}".format(day+1, i+1, A[i][h]-1))
            if i in g.E[A[i][h]-1]:
                a_head[i] += 1
                a_head[A[i][h]-1] += 1
                flag = True

                next_battle[i] = True
                next_battle[A[i][h]-1] = True
                # g.E[A[i][h]-1].remove(i)
                # print("day:{}, {} vs {}".format(day+1, i+1, g.E[i][0]+1))
            else:
                g.add_edge([i, A[i][h]-1])
        # print("E", g.E)
        if flag == False:
            break

    if [h for h in a_head if h != N-1]:
        print(-1)
    else:
        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
from collections import deque
import heapq
INF = float("inf")


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        # print(indices)
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/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
    battle = [True]*N
    next_battle = battle[:]

    day = -1
    g = Graph(N)

    while True:
        day += 1
        flag = False

        battle[:] = next_battle
        for i, h in enumerate(a_head):
            # print(battle)
            if h == N-1:
                continue
            if battle[i] == True:
                next_battle[i] = False
            else:
                continue
            # print("day:{}, {}, {}".format(day+1, i+1, A[i][h]-1))
            if i in g.E[A[i][h]-1]:
                a_head[i] += 1
                a_head[A[i][h]-1] += 1
                flag = True

                next_battle[i] = True
                next_battle[A[i][h]-1] = True
                g.E[A[i][h]-1].remove(i)
                # print("day:{}, {} vs {}".format(day+1, i+1, g.E[i][0]+1))
            else:
                g.add_edge([i, A[i][h]-1])
        # print("E", g.E)
        if flag == False:
            break

    if [h for h in a_head if h != N-1]:
        print(-1)
    else:
        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
from collections import deque
import heapq
INF = float("inf")


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        # print(indices)
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/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
    day = -1

    while True:
        day += 1
        g = Graph(N)
        flag = False

        for i, h in enumerate(a_head):
            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
                # print("day:{}, {} vs {}".format(day+1, i+1, g.E[i][0]+1))
            else:
                g.add_edge([i, A[i][h]-1])
        # print("E", g.E)
        if flag == False:
            break

    if [h for h in a_head if h != N-1]:
        print(-1)
    else:
        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
from collections import deque
import heapq
INF = float("inf")


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        # print(indices)
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/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
    day = -1

    while True:
        day += 1
        g = Graph(N)
        flag = False

        for i, h in enumerate(a_head):
            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
                # print("day:{}, {} vs {}".format(day+1, i+1, g.E[i][0]+1))
            else:
                g.add_edge([i, A[i][h]-1])
        # print("E", g.E)
        if flag == False:
            break

    if [h for h in a_head if h != N-1]:
        print(-1)
    else:
        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
from collections import deque
import heapq
INF = float("inf")


def main():
    # 10**6くらいのループ
    # 毎回、logN以内で閉路を検出できると嬉しい
    # 見るべき場所は、新しく追加したところだけで、即座にわかるのでO(1)か
    N = int(input())
    A = [None]*N
    for i in range(N):
        A[i] = list(map(lambda x: int(x)-1, input().split()))
    # print(A)

    # それぞれの選手の手合進行
    indices = [0]*N
    E = [-1 for _ in range(N)]
    change = []
    for i in range(N):
        # 選手iは次選手A[i][indices[i]]と勝負したい
        E[i] = A[i][indices[i]]
        if E[E[i]] == i:
            # 勝負成立
            change.append(i)
            change.append(E[i])
            indices[i] += 1
            indices[E[i]] += 1
    if len(change) == 0:
        # print("一巡目終了")
        print(-1)
        return

    ans = 0
    while len(change) > 0:
        # print("change", change)
        # print("indices", indices)
        new_change = []
        ans += 1
        for c in change:
            # print("変更", c)
            if indices[c] == N-1:
                continue
            E[c] = A[c][indices[c]]
            if E[E[c]] == c:
                # 勝負成立
                # print("勝負成立, ", c, " vs ", E[c])
                # print(indices)
                new_change.append(c)
                new_change.append(E[c])
                indices[c] += 1
                indices[E[c]] += 1
        change = new_change

    flag = True
    for i in range(N):
        if indices[i] != N-1:
            flag = False
            break
    if flag is False:
        # print(indices)
        print(-1)
        return
    print(ans)

    return


if __name__ == '__main__':
    main()