Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(3000000)

    N = int(input())
    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))

    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    dp = [[0]+[None]*N for _ in range(N+1)]

    def f(i,j,cnt):
        #iとjの試合が最速でいつできるかを返す。
        if cnt > N*N:
            print(-1)
            exit()
        if dp[i][j] == None and dp[j][i] == None:
            #iの一つ前の試合がいつおわるかを調べる。
            pre = A[i][reverseMemo[i][j]-1]
            tmp1 = f(i,pre,cnt+1)
            
            #jの一つ前の試合がいつおわるかを調べる。
            pre = A[j][reverseMemo[j][i]-1]
            tmp2 = f(j,pre,cnt+1)

            dp[i][j] = max(tmp1,tmp2)+1

        elif dp[i][j] == None and dp[j][i] != None:
            dp[i][j] = dp[j][i]
        elif dp[i][j] != None and dp[j][i] != None:
            dp[j][i] = dp[i][j]
        return dp[i][j]

    ans = 0
    cnt = 0
    for i in range(1,N+1):
        for j in range(1,N):
            cnt += 1
            if cnt > 500:
                print("good")
            a = A[i][j]
            ans = max(ans,f(i,a,0))
    print(ans)
main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())
    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))

    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    dp = [[0]+[None]*N for _ in range(N+1)]

    def f(i,j,cnt):
        #iとjの試合が最速でいつできるかを返す。
        if cnt > N*N:
            print(-1)
            exit()
        if dp[i][j] == None and dp[j][i] == None:
            #iの一つ前の試合がいつおわるかを調べる。
            pre = A[i][reverseMemo[i][j]-1]
            tmp1 = f(i,pre,cnt+1)
            
            #jの一つ前の試合がいつおわるかを調べる。
            pre = A[j][reverseMemo[j][i]-1]
            tmp2 = f(j,pre,cnt+1)

            dp[i][j] = max(tmp1,tmp2)+1

        elif dp[i][j] == None and dp[j][i] != None:
            dp[i][j] = dp[j][i]
        elif dp[i][j] != None and dp[j][i] != None:
            dp[j][i] = dp[i][j]
        return dp[i][j]

    ans = 0
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            ans = max(ans,f(i,a,0))
    print(ans)
main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000000)

N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N*N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2000000)

N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N*N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N*N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
N = int(input())

def get_id(i, j):
    if j < i:
        i, j = j, i
    return i * N + j

g = [[] for _ in range(N * N)]
S = []
for i in range(N):
    pre = None
    for j in map(int, input().split()):
        j -= 1
        id_ = get_id(i, j)
        if pre is None:
            S.append(id_)
        else:
            g[pre].append(id_)
        pre = id_


dp = [-1] * (N * N)
visited = [False] * (N * N)
def dfs(v):
    visited[v] = True
    if dp[v] != -1:
        return dp[v]
    for u in g[v]:
        if dp[u] != -1:
            res = dp[u]
        else:
            if visited[u]:
                raise ValueError('find loop!')
            res = dfs(u)
        dp[v] = max(dp[v], res + 1)
    if len(g[v]) == 0:
        dp[v] = 1
    return dp[v]

ans = 0
try:
    for s in S:
        ans = max(ans, dfs(s))
    print(ans)
except ValueError:
    print(-1)

Submission status: Runtime Error

Solution code:
// template for atcode
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {

    private static final int MOD = (int)1e9 + 7; //998244353;
    // private static final long INF = (long)1e17;
    private static final int INF = (int)1e9;

    int N, M;
    List<Integer>[] adj;
    int[] cnt;
    int[] marked;

    public Main(FastScanner in, PrintWriter out) {
        N = in.nextInt();
        M = N * (N - 1) / 2;
        cnt = new int[M];
        adj = new List[M];
        for (int i = 0; i < M; i++)
            adj[i] = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int u = -1;
            for (int j = 0; j < N - 1; j++) {
                int v = node(i, in.nextInt() - 1);
                if (u >= 0) {
                    adj[u].add(v);
                    cnt[v]++;
                }
                u = v;
            }
        }
        marked = new int[M];
        for (int i = 0; i < M; i++) {
            if (marked[i] == 0)
                if (hasCycle(i)) {
                    out.println(-1);
                    return;
                }
        }
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < M; i++) {
            if (cnt[i] == 0) q.add(i);
        }
        int res = 0;
        while (!q.isEmpty()) {
            res++;
            int sz = q.size();
            while (sz-- > 0) {
                int v = q.remove();
                for (int w : adj[v]) {
                    if (--cnt[w] == 0) q.add(w);
                }
            }
        }
        out.println(res);
    }

    boolean hasCycle(int v) {
        marked[v] = 1;
        for (int w : adj[v]) {
            if (marked[w] == 0) {
                if (hasCycle(w)) return true;
            } else if (marked[w] == 1)
                return true;
        }
        marked[v] = 2;
        return false;
    }

    private int node(int i, int j) {
        if (i > j) {
            int t = i;
            i = j;
            j = t;
        }
        return (N - 1 + N - i) * i / 2 + j - i - 1;
    }

    private int gcd(int a, int b) {
        while (true) {
            if (b == 0) return a;
            int tmp = a;
            a = b;
            b = tmp % b;
        }
    }

    private long gcd(long a, long b) {
        while (true) {
            if (b == 0) return a;
            long tmp = a;
            a = b;
            b = tmp % b;
        }
    }

    private long powm(long x, long p) {
        long res = 1;
        while (p > 0) {
            if (p % 2 == 1)
                res = res * x % MOD;
            x = x * x % MOD;
            p /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        // Scanner in = new Scanner(
                // new BufferedReader(new InputStreamReader(System.in)));
        FastScanner in = new FastScanner(System.in);

        Main sol = new Main(in, out);
        out.close();
    }
}

// Pair
class Pair<T extends Comparable<? super T>, U extends Comparable<? super U>> implements Comparable<Pair<T, U>> {
    T a;
    U b;
    Pair() { }
    Pair(T a, U b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public String toString() { return "("+a.toString()+", "+b.toString()+")"; }

    @Override
    public int hashCode() { return Objects.hash(a, b); }

    @Override
    public boolean equals(Object obj) {
        if(this == obj) return true;
        if(obj == null) return false;
        if(this.getClass() != obj.getClass()) return false;
        Pair that = (Pair) obj;
        if(this.a.getClass() != that.a.getClass()) return false;
        if(this.b.getClass() != that.b.getClass()) return false;
        if(!this.a.equals(that.a)) return false;
        if(!this.b.equals(that.b)) return false;
        return true;
    }

    @Override
    public int compareTo(Pair<T, U> that) {
        int c = (this.a).compareTo(that.a);
        if(c == 0) c = (this.b).compareTo(that.b);
        return c;
    }
}


class FastScanner{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public FastScanner(InputStream stream)
    {
        this.stream = stream;
    }

    int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars){
            curChar = 0;
            try{
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    boolean isSpaceChar(int c)
    {
        return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
    }

    boolean isEndline(int c)
    {
        return c=='\n'||c=='\r'||c==-1;
    }

    int nextInt()
    {
        return Integer.parseInt(next());
    }

    long nextLong()
    {
        return Long.parseLong(next());
    }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String next(){
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isSpaceChar(c));
        return res.toString();
    }

    String nextLine(){
        int c = read();
        while (isEndline(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isEndline(c));
        return res.toString();
    }
}

Submission status: Runtime Error

Solution code:
from collections import deque
def c_check(a):
    global flag
    if flag==1:return
    for b in G[a][1]:
        if hist[b]==1:
            flag = 1
            return
        hist[b] = 1
        c_check(b)
        hist[b] = 0
N = int(input())
G = {}
for i in range(1,N+1):
    a = list(map(int,input().split()))
    i1 = i
    i2 = a[0]
    if i1>i2:
        i1,i2 = i2,i1
    if (i1,i2) not in G:
        G[(i1,i2)] = [0,[]]
    for j in range(1,N-1):
        i1 = i
        i2 = a[j-1]
        i3 = i
        i4 = a[j]
        if i1>i2:
            i1,i2 = i2,i1
        if i3>i4:
            i3,i4 = i4,i3
        G[(i1,i2)][1].append((i3,i4))
        if (i3,i4) not in G:
            G[(i3,i4)] = [0,[]]
        G[(i3,i4)][0] += 1
que = deque([])
hist = {}
for a in G:
    hist[a] = 0
flag = 0
for a in G:
    if flag==1:break
    if G[a][0]==0:
        hist[a] = 1
        c_check(a)
        if flag==1:break
        que.append((a,1))
if len(que)==0:
    flag = 1
if flag==0:
    cnt = 0
    while que:
        a,d = que.popleft()
        for b in G[a][1]:
            G[b][0] -= 1
            if G[b][0]==0:
                que.append((b,d+1))
                cnt = d+1
                hist[b] = 1
if flag==1:
    print(-1)
else:
    print(cnt)

Submission status: Runtime Error

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

B = set()
tmp = [0 for i in range(N + 1)]
tmp[0] = 1

battle = 0
count = 0
while sum(tmp) > 0:
    tmp = [0 for i in range(N + 1)]
    for i in range(1, N+1):
        if len(A[i]) == 0 or tmp[i] == 1:
            continue
        else:
            a = A[i][0]
            if i < a:
                if (i,a) in B:
                    B.remove((i,a))
                    A[i].popleft()
                    A[a].popleft()
                    tmp[i] = 1
                    tmp[a] = 1
                    battle += 1
                else:
                    B.add((i,a))
            else:
                if (a,i) in B:
                    B.remove((a,i))
                    A[i].popleft()
                    A[a].popleft()
                    tmp[i] = 1
                    tmp[a] = 1
                    battle += 1
                else:
                    B.add((a,i))
    count += 1
    if battle == N*(N-1)//2:
        break

if battle == N*(N-1)//2:
    print(count)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

es = [[[] for j in range(i)] for i in range(N)]
indeg = [[0]*i for i in range(N)]
for i,row in enumerate(A):
    for x,y in zip(row,row[1:]):
        x,y = x-1,y-1
        a0,b0 = (i,x) if i>x else (x,i)
        a1,b1 = (i,y) if i>y else (y,i)
        es[a0][b0].append((a1,b1))
        indeg[a1][b1] += 1

status = [[-1]*i for i in range(N)] #-1:new 0:active 1:finished
def has_cycle(v):
    a0,b0 = v
    status[a0][b0] = 0
    for a1,b1 in es[a0][b0]:
        if status[a1][b1] == 0: return True
        if status[a1][b1] == -1:
            if has_cycle((a1,b1)): return True
    status[a0][b0] = 1
    return False

for i in range(N):
    for j in range(i):
        if status[i][j] != -1: continue
        if has_cycle((i,j)):
            print(-1)
            exit()

from collections import deque
q = deque()
for i in range(N):
    for j in range(i):
        if indeg[i][j] == 0:
            q.append((i,j,1))

ans = -1
while q:
    a0,b0,d = q.popleft()
    ans = max(ans,d)
    for a1,b1 in es[a0][b0]:
        indeg[a1][b1] -= 1
        if indeg[a1][b1] == 0:
            q.append((a1,b1,d+1))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = [[0]*(n) for i in range(n)]
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i][j] = ind
        index[j][i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i][a[i][j]]
        v = index[i][a[i][j+1]]
        ns[u].append(v)
assert False
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            # 非負の値: 新しい頂点に到達
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    # 閉路発見
                    return True
        else:
            u = ~u
            done[u] = True
            # ここに帰りがけ処理を書く
            val = 0
            for v in ns[u]:
                # uの子はすべて処理が終わっている
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print(-1)
        break
else:
    print(max(vals)+1)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)
assert False
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            # 非負の値: 新しい頂点に到達
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    # 閉路発見
                    return True
        else:
            u = ~u
            done[u] = True
            # ここに帰りがけ処理を書く
            val = 0
            for v in ns[u]:
                # uの子はすべて処理が終わっている
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print(-1)
        break
else:
    print(max(vals)+1)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    seen[u] = True
    while s:
        u = s.pop()
        if u>=0:
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    seen[v] = True
                    s.append(v)
                else:
                    # 閉路発見
                    return True
        else:
            u = ~u
            done[u] = True
            # ここに帰りがけ処理を書く
            val = 0
            for v in ns[u]:
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print(-1)
        break
else:
    raise RuntimeError
    print(max(vals)+1)

Submission status: Runtime Error

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
def bfs(u):
  P[u]=0
  B.append(u)
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      if i in B:
        ans=-1
        break
      if P[v]+1>P[i]:
        P[v]+1>P[i]
        P[i]=P[v]+1
        queue.append(i)
ans=-1
for i in range(M):
  B=[]
  if len(F[i])==0:
    ans=0
    bfs(i)
  if ans==-1:
    print(-1)
    exit()

if min(P)==-1:
  print(-1)
else:
  print(max(P)+1

Submission status: Runtime Error

Solution code:
N = int(input())

arr = {(i,j):set([]) for i in range(1,N+1) for j in range(i+1,N+1)}
dic = {(i,j):0 for i in range(1,N+1) for j in range(i+1,N+1)}
used = {(i,j):0 for i in range(1,N+1) for j in range(i+1,N+1)}
visited = {(i,j):0 for i in range(1,N+1) for j in range(i+1,N+1)}
rlt = {(i,j):0 for i in range(1,N+1) for j in range(i+1,N+1)}

def dfs(t):
  for u in arr[t]:
    if visited[u] == 1 and used[u] == 0:
      return -1
    rlt[u] = max(rlt[u], rlt[t]+1)
    if visited[u] == 0:
      visited[u] = 1
      dfs(u)
  used[t] = 1
  return 0

for i in range(1,N+1):
  As = map(int, input().split())
  b = 0
  for a in As:
    if b > 0:
      if i < a and i < b:
        arr[(i,b)].add((i,a))
        dic[(i,a)] += 1
      elif i > a and i < b:
        arr[(i,b)].add((a,i))
        dic[(a,i)] += 1
      elif i < a and i > b:
        arr[(b,i)].add((i,a))
        dic[(i,a)] += 1
      elif i > a and i > b:
        arr[(b,i)].add((a,i))
        dic[(a,i)] += 1
    b = a
    
cnt = N+1
for t in rlt:
  cnt = min(cnt, dic[t])
if cnt > 0:
  print(-1)
  exit()
  
cnt = 0
for t in rlt:
  if dic[t] > 0:
    continue
  rlt[t] = 1
  r = dfs(t)
  if r == -1:
    print(-1)
    exit()
        
for t in rlt:
  cnt = max(rlt[t], cnt)
print(cnt)

Submission status: Runtime Error

Solution code:
def solve():
  ans = 0
  N = int(input())
  stacks = [list(map(lambda x:int(x)-1, input().split()))[::-1] for _ in range(N)]
  lis = [0]*N
  cnt = 0
  now = 0
  flag = 0
  while cnt<N*(N-1)//2:
    if not stacks[now]:
      now += 1
    a = stacks[now][-1]
    if stacks[a][-1] == now:
      lis[now] = max(lis[now],lis[a])+1
      lis[a] = lis[now]
      stacks[a].pop(-1)
      stacks[now].pop(-1)
      cnt += 1
    else:
      now = a
      flag += 1
    if flag==N:
      return -1
  ans = max(lis)
  return ans
print(solve())

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

d = {k:1 for k in nodes}
f = {k:0 for k in nodes}
in_cnt = {k:0 for k in nodes}
for x in nodes:
  for y in graph[x]:
    in_cnt[y] += 1
ret = []
q = deque([i for i in nodes if not in_cnt[i]])
if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.popleft()
  ret.append(x)
  f[x] = 1
  for y in graph[x]:
    if f[y]:
      print(-1)
      exit()
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in range(N) if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def topological_sort(graph):
  d = {i:1 for i in nodes}
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      d[y] = max(d[x]+1,d[y])
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in nodes if in_cnt[i]]:
    return None
  return ret,d

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

ans,d = topological_sort(graph)
if not ans:
  print(-1)
else:
  print(max(d[i] for i in nodes))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

def topological_sort(graph):
  in_cnt = {k:0 for k in nodes}
  for x in nodes:
    for y in graph[x]:
      in_cnt[y] += 1
  ret = []
  q = deque([i for i in nodes if not in_cnt[i]])
  while q:
    x = q.popleft()
    ret.append(x)
    for y in graph[x]:
      in_cnt[y] -= 1
      if not in_cnt[y]:
        q.append(y)
  if [i for i in nodes if in_cnt[i]]:
    return None
  return ret

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:set() for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].add(now)
    prev = now

ans = topological_sort(graph)
if not ans:
  print(-1)
else:
  d = {i:1 for i in nodes}
  for x in ans:
    for y in graph[x]:
      d[y] = max(d[x]+1,d[y])
  print(max(d[i] for i in nodes))

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

H, W, D = MAP()
A = [LIST() for _ in range(H)]

dic = defaultdict(tuple)

for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y+1, x+1)

power = [[] for _ in range(D)]
for i in range(1, H*W+1):
	if i <= D:
		power[i%D].append(0)
	else:
		idx = i%D
		tmp = abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
		power[i%D].append(tmp)

#print(power)
power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))
power_acc[0].insert(0, 0)
#print(power_acc)

Q = INT()
for _ in range(Q):
	L, R = MAP()
	print(power_acc[R%D][R//D-1] - power_acc[L%D][L//D-1])