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:
import os

N = int(input())
a = [ list(map(int, input().split())) for i in range(N)]


MAXN = 1001
MAXV = MAXN*(MAXN-1)//2
id = [[0 for _ in range(MAXN)]for _ in range(MAXN)]
to = [[] for _ in range(MAXV)]

def to_id(i, j):
    if i > j:
        j, i = i, j
    return id[i][j]

visited = [False for _ in range(MAXV)]
calculated = [False for _ in range(MAXV)]
dp = [-1 for _ in range(MAXV)]
def dfs(i):
    if visited[i]:
        if not calculated[i]:
            return -1
        else:
            return dp[i]
    visited[i] = True
    dp[i] = 1
    for u in to[i]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[i] = max(dp[i], res+1)
    calculated[i] = True
    return dp[i]

v = 0
for i in range(N):
    for j in range(i, N):
        id[i][j] = v
        v += 1

for i in range(N):
    for j in range(N-1):
        a[i][j] = to_id(i, a[i][j]-1)
    for j in range(N-2):
        to[a[i][j+1]].append(a[i][j])

ans = 0
for i in range(v):
    res = dfs(i)
    if res == -1:
        print(-1)
        os.sys.exit()
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
import os

N = int(input())
a = [ list(map(int, input().split())) for i in range(N)]


MAXN = 1000
MAXV = MAXN*(MAXN-1)//2
id = [[0 for _ in range(MAXN)]for _ in range(MAXN)]
to = [[] for _ in range(MAXV)]

def to_id(i, j):
    if i > j:
        j, i = i, j
    return id[i][j]

visited = [False for _ in range(MAXV)]
calculated = [False for _ in range(MAXV)]
dp = [-1 for _ in range(MAXV)]
def dfs(i):
    if visited[i]:
        if not calculated[i]:
            return -1
        else:
            return dp[i]
    visited[i] = True
    dp[i] = 1
    for u in to[i]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[i] = max(dp[i], res+1)
    calculated[i] = True
    return dp[i]

v = 0
for i in range(N):
    for j in range(i, N):
        id[i][j] = v
        v += 1

for i in range(N):
    for j in range(N-1):
        a[i][j] = to_id(i, a[i][j]-1)
    for j in range(N-2):
        to[a[i][j+1]].append(a[i][j])

ans = 0
for i in range(v):
    res = dfs(i)
    if res == -1:
        print(-1)
        os.sys.exit()
    ans = max(ans, res)
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)
#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)
#define lint long long
auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;};
auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail){
  std::cerr << " " << head;
  debug_impl(tail...);
}
#define debug(...) std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
  debug_impl(__VA_ARGS__);\
  std::cerr << std::noboolalpha;

template <typename T>
auto make_vector_impl(size_t sz, T t) {return std::vector<T>(sz, t);}

template <size_t N, typename T, typename U, std::enable_if_t<N == 1, std::nullptr_t> = nullptr>
auto make_vector(size_t sz, U u) {return make_vector_impl(sz, T(u));}

template <size_t N, typename T, std::enable_if_t<N == 1, std::nullptr_t> = nullptr>
auto make_vector(size_t sz) {return std::vector<T>(sz);}

template <size_t N, typename T, typename... Args, std::enable_if_t<N != 1, std::nullptr_t> = nullptr>
auto make_vector(size_t a, Args... args) {return make_vector_impl(a, make_vector<N - 1, T>(args...));}

template <typename T, typename Size_t>
auto& at(T& t, Size_t i) {return t.at(i);}

template <typename T, typename Size_t, typename... Args>
auto& at(T& t, Size_t i, Args... args) {return at(t.at(i), args...);}

template <typename T, typename U>
std::ostream& operator<< (std::ostream& os, const std::pair<T, U>& pair){
  return os << "(" << pair.first << "," << pair.second << ")";
}

template <typename T, typename U>
std::istream& operator>> (std::iostream& is, std::pair<T, U>& pair) {
  return is >> pair.first >> pair.second;
}

template <typename T>
std::istream& operator>> (std::istream& is, std::vector<T>& v) {
  for (auto & x : v) is >> x;
  return is;
}

template <typename T>
std::ostream& operator<< (std::ostream& os, const std::vector<T>& v) {
  auto n = v.size();
  os << "{";
  for (size_t i = 0; i < n; i++)
    os << (i > 0 ? "," : "") << v[i];
  return os << "}";
}

template<typename T>
class fixed_point : T {
  public:
    explicit constexpr fixed_point (T&& t) noexcept
      : T(std::forward<T>(t)) {}
    template<typename... Args>
    constexpr decltype(auto) operator()(Args&&... args) const
      {return T::operator()(*this, std::forward<Args>(args)...);}
};
template<typename T>
static inline constexpr decltype(auto) fix (T&& t) noexcept {
  return fixed_point<T>{std::forward<T>(t)};
}

int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  auto N = n * (n - 1) / 2;
  std::vector<std::pair<int, int>> table(N);
  auto encode = [&] (int i, int j) {
    if (i < j) std::swap(i, j);
    return i * (i - 1) / 2 + j;
  };
  auto list = make_vector<2, int>(n, n - 1);
  rep(i, 0, n) {
    rep(j, 0, n) {
      if (i == j) continue;
      auto code = encode(i, j);
      if (i > j) table.at(code) = {i, j};
      int x; std::cin >> x;
      x--;
      at(list, i, j - (i < j)) = encode(i, x);
    }
  }
  auto graph = make_vector<2, int>(N, 0);
  for (auto const& v : list) {
    rep(j, 0, n - 2) {
      graph.at(v.at(j)).push_back(v.at(j + 1));
    }
  }
  auto err = [&] {
    std::cout << -1 << std::endl;
    exit(0);
  };
  std::vector<int> dp(N, 0);
  std::vector<int> ckd(N, 0);
  auto cal = fix([&](auto f, int crr) -> int {
    ckd.at(crr) = 1;
    for (auto nxt : graph.at(crr)) {
      if (ckd.at(nxt) == 1) err();
      cmx(dp.at(crr), f(nxt) + 1);
    }
    ckd.at(crr) = 2;
    return dp.at(crr);
  });
  rep(i, 0, N) {
    if (ckd.at(i) == 0) cal(i);
  }
  auto ret = *max_element(dp.begin(), dp.end()) + 1;
  std::cout << ret << std::endl;
  return 0;
}

Submission status: Runtime Error

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

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[set() for i in range(N*N)]
EREV=[set() for i in range(N*N)]

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].add(A[i][j])
        EREV[A[i][j]].add(A[i][j-1])

from collections import deque
Q=deque()

H=[0]*N**N

for i in range(N*N):
    if E[i]==set() and len(EREV[i])>0:
        Q.append(i)
        H[i]=1

while Q:
    x=Q.pop()

    for fr in EREV[x]:
        H[fr]=max(H[x]+1,H[fr])
        if H[fr]>N*N:
            print(-1)
            sys.exit()
        Q.append(fr)
        

if max(H)==0:
    print(-1)
else:
    print(max(H))

Submission status: Runtime Error

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[set() for i in range(N*N)]
EREV=[set() for i in range(N*N)]

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].add(A[i][j])
        EREV[A[i][j]].add(A[i][j-1])

from collections import deque
Q=deque()

H=[0]*N**N

for i in range(N*N):
    if E[i]==set() and len(EREV[i])>0:
        Q.append(i)
        H[i]=1

while Q:
    x=Q.pop()

    for fr in EREV[x]:
        H[fr]=max(H[x]+1,H[fr])
        Q.append(fr)

if max(H)==0:
    print(-1)
else:
    print(max(H))

Submission status: Runtime Error

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])

from collections import deque
Q=deque()

H=[0]*N**N

for i in range(N*N):
    if E[i]==[] and len(EREV[i])>0:
        Q.append(i)
        H[i]=1

while Q:
    x=Q.pop()

    for fr in EREV[x]:
        H[fr]=max(H[x]+1,H[fr])
        Q.append(fr)

if max(H)==0:
    print(-1)
else:
    print(max(H))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define REP(i, a, n) for (long long i = (a); i < (long long)(n); ++i)
#define REPC(i, a, n) for (long long i = (a); i <= (long long)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, queue<T> vec) {
  os << "{";
  while (!vec.empty()) {
    os << vec.front() << ",";
    vec.pop();
  }
  os << "}";
  return os;
}
template <typename T>
ostream &operator<<(ostream &os, set<T> &s) {
  os << "{";
  for (auto p : s) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}
VEC<VEC<int>> G;

int main() {
  int N;
  cin >> N;
  VEC<queue<int>> TO(N);
  REP(i, 0, N) {
    REP(j, 0, N - 1) {
      int a;
      scanf("%d", &a);
      a--;
      TO[i].push(a);
    }
  }
  LL cnt = 0;
  LL sum = N * (N - 1);
  LL days = 0;
  int prev = cnt;
  queue<pair<int, int>> tosee;
  REP(i, 0, N) { tosee.push({i, TO[i].front()}); }
  // 変更点をqueueに入れるように舐め方を変えると通るらしい
  // DUMP(tosee);
  // DUMP(tosee);
  while (cnt < sum && days < sum + 2) {
    VEC<int> done(N, 0);
    queue<pair<int, int>> next;
    while (tosee.empty() == false) {
      auto p = tosee.front();
      tosee.pop();
      int i = p.first;
      int j = p.second;
      if (TO[i].front() == j && TO[j].front() == i) {
        cnt++;
        done[i] = 1;
        done[j] = 1;
        // DUMP(days, cnt, i + 1, j + 1);
      } else {
        next.push({i, j});
      }
    }
    days++;
    if (cnt == prev) {
      cout << -1 << endl;
      return 0;
    } else {
      prev = cnt;
    }
    while (next.empty() == false) {
      tosee.push(next.front());
      next.pop();
    }
    REP(i, 0, N) {
      if (done[i]) {
        TO[i].pop();
        tosee.push({i, TO[i].front()});
      }
    }
  }
  if (days == sum + 2) {
    cout << -1 << endl;
    return 0;
  }
  printf("%lld\n", days);

  return 0;
}

Submission status: Runtime Error

Solution code:
n = int(input())
li =[list(map(int,input().split())) for i in range(1,n+1)]

cnt = 0
check = []
kouho = [i for i in range(1,n+1)]
play = 0

while play < n*(n-1) // 2:
    s = play
    for i in kouho:
        if i in check or len(li[i-1]) == 0:
            continue
        temp = li[i-1][0]
        if li[temp-1][0] == i and temp not in check:
            del li[i-1][0]
            del li[temp-1][0]
            play += 1
            check.append(i)
            check.append(temp)
    cnt += 1
    kouho = check.copy()
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)

Submission status: Runtime Error

Solution code:
n = int(input())
li =[list(map(int,input().split())) for i in range(1,n+1)]

cnt = 0
check = []
kouho = list(range(1,n+1))
play = 0

while play < n*(n-1) // 2:
    s = play
    for i in kouho:
        if i in check or len(li[i-1]) == 0:
            continue
        temp = li[i-1][0]
        if li[temp-1][0] == i and temp not in check:
            del li[i-1][0]
            del li[temp-1][0]
            play += 1
            check.append(i)
            check.append(temp)
    cnt += 1
    kouho = check.copy()
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)

Submission status: Runtime Error

Solution code:
MAXN = 10
MAXV = (MAXN * (MAXN - 1)) // 2
to = [[] for _ in range(MAXV)]
ID = [[-1] * MAXN for _ in range(MAXN)]

def toID(i, j):
    if i > j:
        i, j = j, i
    return ID[i][j]

visited = [False] * MAXV
calculated = [False] * MAXV
dp = [0] * MAXV
def dfs(v):
    if visited[v]: #すでに訪れたことがある時
        if not calculated[v]: #計算されたことがない時 = ループがある
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res + 1)
    calculated[v] = True
    return dp[v]

def main():
    N = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

    V = 0 #頂点の数
    for i in range(N - 1):
        for j in range(i + 1, N):
            ID[i][j] = V
            V += 1
    
    for i in range(N):
        for j in range(N - 1):
            a[i][j] = toID(i, a[i][j]) #対戦相手で管理していたのを試合番号に変える
        for j in range(N - 2):
            to[a[i][j + 1]].append(a[i][j])
    
    # import numpy as np
    # print (np.array(to))
    # print (np.array(ID))

    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print (-1)
            return 0
        ans = max(ans, res)
    print (ans)
    return 0

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# YouTube2
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
input=sys.stdin.readline

def main():
    def dfs(u):
        if dis[u] > 0:
            return dis[u]
        if dis[u] == 0:
            return -1
        dis[u] = 0
        res = 1
        for v in to[u]:
            tmp = dfs(v) + 1
            if tmp == 0: return -1
            res = max(res, tmp)
        dis[u] = res
        return res

    to = defaultdict(list)
    n = int(input()[:-1])
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
    all_game = n * (n - 1) // 2
    dis = [-1] * all_game
    game = [[0] * n for _ in range(n)]
    u = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            game[i][j] = game[j][i] = u
            u += 1

    for i in range(n):
        ai=a[i]
        gi=game[i]
        j = ai[0]
        pre = gi[j]
        for gi in range(1, n - 1):
            j = ai[gi]
            to[pre].append(gi[j])
            pre = gi[j]
#    print(to)

    ans=0
    for i in range(all_game):
        tmp=dfs(i)
        if tmp == -1:
            print(-1)
            exit()
        if tmp>ans:
            ans=tmp
#    print(dis)
    print(ans)

main()

Submission status: Runtime Error

Solution code:
#"""
import sys
input = sys.stdin.readline
#"""
def main()
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]

    V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
    Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0) if i<a0 else (a0,i)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1) if i<a1 else (a1,i)
            Ef[k0].append(k1)
            V[k1] += 1

    q = [k for k in V if V[k] == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for k in q:
            for k2 in Ef[k]:
                V[k2] -= 1
                rmv += 1
                if V[k2] == 0 : qq.append(k2)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()

Submission status: Runtime Error

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

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

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    k1 = (i,B[0]-1)
    for j in range(N-2):
        a1 = B[j+1]-1
        k0 = k1
        k1 = (i,a1) if i<a1 else (a1,i)
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

Submission status: Runtime Error

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

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

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    k1 = (0,B[0]-1)
    for j in range(N-2):
        a1 = B[j+1]-1
        k0 = k1
        k1 = (j,a1) if j<a1 else (a1,j)
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

Submission status: Runtime Error

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

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

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    k1 = (0,B[0]-1)
    for j in range(N-2):
        a1 = B[j+1]-1
        k0 = k1
        k1 = (i,a1) if i<a1 else (a1,i)
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

Submission status: Runtime Error

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

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

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    k1 = (0,B[0])
    for j in range(N-2):
        a1 = B[j+1]-1
        k0 = k1
        k1 = (i,a1) if i<a1 else (a1,i)
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
from collections import deque


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

    done = True
    ans = 0
    cand = [i for i in range(N)]
    while(True):
        done = False
        today = set()
        next_cand = set()
        # 向き合ってるかチェック
        for i in cand:
            if i in today or A[i][0] in today:
                continue
            elif(A[A[i][0]][0] == i):
                done = True
                today.add(A[i][0])
                A[A[i][0]].popleft()
                if len(A[A[i][0]]) != 0:
                    next_cand.add(A[i][0])
                    next_cand.add(A[A[i][0]][0])
                A[i].popleft()
                if len(A[i]) != 0:
                    next_cand.add(i)
                    next_cand.add(A[i][0])
        cand = next_cand
        ans += 1
        if not done:
            ans = -1
            break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# YouTube2
from collections import defaultdict

def main():
    def dfs(u):
        if dis[u] > 0:
            return dis[u]
        if dis[u] == 0:
            return -1
        dis[u] = 0
        res = 1
        for v in to[u]:
            tmp = dfs(v) + 1
            if tmp == 0: return -1
            res = max(res, tmp)
        dis[u] = res
        return res

    to = defaultdict(list)
    n = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
    all_game = n * (n - 1) // 2
    dis = [-1] * all_game
    game = [[0] * n for _ in range(n)]
    u = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            game[i][j] = game[j][i] = u
            u += 1

    for i in range(n):
        j = a[i][0]
        pre = game[i][j]
        for gi in range(1, n - 1):
            j = a[i][gi]
            to[pre].append(game[i][j])
            pre = game[i][j]
#    print(to)

    for i in range(all_game):
        if dfs(i) == -1:
            print(-1)
            exit()
#    print(dis)
    print(max(dis))

main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = [[int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]

total_match=n*(n-1)//2
match=0
day=0


for _ in range(total_match):
    day+=1
    today_match=[]

    for i in range(n):
        try:
            m=league[i][-1]-1
            if not i in today_match and not m in today_match:
                if league[m][-1]-1==i:
                    today_match.extend((i,m))
                    league[i].pop()
                    league[m].pop()
        except:
            continue
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2
    if match>=total_match:
        break

print(day)

Submission status: Runtime Error

Solution code:
inf=10**9+7
n=int(input())
size=n*(n-1)//2

graph=[[] for _ in range(size)]

idx={}
cnt=0
for i in range(n-1):
    for j in range(i+1, n):
        idx[(i,j)]=cnt
        cnt+=1

for i in range(n):
    a=tuple(map(int,input().split()))
    l=(min(i, a[0]-1), max(i,a[0]-1))
    for j in a[1:]:
        r=(min(i, j-1), max(i, j-1))
        graph[idx[l]].append(idx[r])
        l=r

def dfs(start, node, depth):
    next=graph[node]
    if len(next)==0:
        return depth
    if start in next:
        return inf
    for i in next:
        return max(dfs(start, i, depth+1), depth)

ans=-1
for i in range(n):
    ans=max(ans, dfs(i, i, 1))

ans=-1 if ans>=inf else ans
print(ans)

Submission status: Runtime Error

Solution code:
import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(lambda x:x-1, list(map(int, input().split()))))for i in range(n)]


    # 試合を頂点とする(ex 1-2,2-4 : i < j)
    v = 0  # 頂点数
    # 頂点にIDをふる
    Id = [[-1 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                Id[j][i] = v
                v += 1

    # 頂点間の辺を貼る
    e = [[] for i in range(maxv)]
    for i in range(n):
        # a[i][j]にIDを代入する Id[1][3]=1 => a[1][3] = a[3][1] = 1
        for j in range(n - 1):
            a[i][j] = Id[i][a[i][j]]

        # 辺をはる
        for j in range(n - 2):
            e[a[i][j]].append(a[i][j+1])


    calculated = [False for i in range(maxv)]
    dp = [-1 for i in range(maxv)]
    def dfs(v):
        if dp[v] != -1:
            if not calculated[v]:
                return -1
            return dp[v]
        dp[v] = 1
        for u in e[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True　#帰りがけ
        return dp[v]
    

    #トポロジカルソート
    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  # サイクル検知
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(lambda x:x-1, list(map(int, input().split()))))
         for i in range(n)]


    # 試合を頂点とする(ex 1-2,2-4 : i < j)
    v = 0  # 頂点数
    # 頂点にIDをふる
    Id = [[-1 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                Id[j][i] = v
                v += 1

    # 頂点間の辺を貼る
    e = [[] for i in range(maxv)]
    for i in range(n):
        # a[i][j]にIDを代入する Id[1][3]=1 => a[1][3] = a[3][1] = 1
        for j in range(n - 1):
            a[i][j] = Id[i][a[i][j]]

        # 辺をはる
        for j in range(n - 2):
            e[a[i][j]].append(a[i][j+1])


    calculated = [False for i in range(maxv)]
    dp = [-1 for i in range(maxv)]
    def dfs(v):
        if dp[v] != -1:
            if not calculated[v]:
                return -1
            return dp[v]
        dp[v] = 1
        for u in e[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True　#帰りがけ
        return dp[v]
    

    #トポロジカルソート
    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  # サイクル検知
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [IL()[::-1] for i in range(N)]

used = [-1]*N
total = N*(N-1)//2
flag = 1
cnt = 0
days = 0
while flag:
  flag = 0
  for i in range(N):
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        flag = 1
        cnt += 1
  else:
    if flag == 1:
      #days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline #高速化期待
from collections import deque

def main():
    N = int(input())
    A = [deque()] + [deque( map( int, input().split())) for _ in range(N)]
    NOW = [0]*(N+1)
    Days = [0]*(N+1)
    q = deque( [ i+1 for i in range(N)])
    while q:
      i = q.popleft()
      if not A[i]:
        continue
      
      a = A[i].popleft()
      
      if NOW[a] == i:
        NOW[a] = 0
        Days[a] = Days[i] = max((Days[i], Days[a])) + 1
        q.apppend(i)
        q.apppend(a)
      else:
        NOW[i] = a
    for i in range(N+1):
      if A[i]:
        print(-1)
        return
    print(max(Days))
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
a = [list(map(lambda x:int(x)-1,input().split())) + [-1] for _ in range(n)] + [0]

l,day = [0]*n,[0]*n

que = deque([i for i in range(n)])

while que:
    u = que.popleft()
    v = a[u][l[u]]
    if a[v][l[v]] == u:
        day[u] = max(day[u],day[v]) + 1
        day[v] = day[u]
        l[u] += 1
        l[v] += 1
        que.append(u)
        que.append(v)

if any(x != n-1 for x in l):
    print(-1)
    exit()

print(max(day))

Submission status: Runtime Error

Solution code:
from collections import deque

n = int(input())
a = [list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]

l,day = [0]*n,[0]*n

que = deque([i for i in range(n)])

while que:
    u = que.popleft()
    v = a[u][l[u]]
    if a[v][l[v]] == u:
        day[u] = max(day[u],day[v]) + 1
        l[u] += 1
        l[v] += 1
        que.append(u)
        que.append(v)

if any(x != n-1 for x in l):
    print(-1)
    exit()

print(max(day))

Submission status: Runtime Error

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())

    edges = [[] for i in range(N*N)]
    index = {}
    prev = (0, 0)
    index.setdefault(prev, len(index))
    for a in range(1,N+1):
        l = [int(x) for x in input().split()]
        previ = 0
        for y in l:
            x = a 
            if x > y:
                x, y = y, x 
            vi = index.setdefault((x, y), len(index))
            edges[previ].append(vi)
            previ = vi

    if not order(edges, index):
        print(-1)
    else:
        print(longestpath(edges, index))

def order(edges, index):
    NEW = 0
    TMP = 1
    DONE = 2
    status = [0] * len(index)

    def visit(n):
        if status[n] == 1:
            return False
        elif status[n] == 0:
            status[n] = 1
            for u in edges[n]:
                if visit(u) == False:
                    return False
            status[n] = 2
        return True

    for n in range(len(index)):
        if visit(n) == False:
            return False
    return True

def longestpath(edges, index):
    from heapq import heappop, heappush
    q = [(0, 0)]
    D = [0] * len(index)
    while q:
        d, u = heappop(q)
        for v in edges[u]:
            if D[v] < d + 1:
                D[v] = d + 1
                heappush(q, (d+1, v))
    return max(D)

main()