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: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict


import sys
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = defaultdict(set)

    V = set()

    def ij2v(i, j):
        if i > j:
            i, j = j, i
        return i * 10**6 + j
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = ij2v(i, a[j])
            v = ij2v(i, a[j+1])
            g[u].append(v)
            rg[v].add(u)
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if not rg[v]:
            s.append(v)

    done = len(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                # if v in done:
                #     continue
                rg[v].remove(u)
                if len(rg[v]) == 0:
                    ns.append(v)
                    done += 1
        s = ns

    if done != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
A = []
for _ in range(N):
    # 選手番号を0-indexにする
    line = list(map(lambda x: int(x) - 1, input().split()))
    A.append(line)

# cnt[i] = 選手iが現在までに何試合したか
cnt = [0] * N
# recent[i] = 選手iが最後に試合をした日
recent = [0] * N

# Qの初期値 = [0, 1, ..., N-1]
Q = deque(range(N))

while Q:
    # ある選手(p1)について
    p1 = Q.popleft()
    # p1がまだ全試合(N-1試合)を終えていない場合
    # p2 = p1が次に当たるべき選手
    if cnt[p1] < N - 1:
        p2 = A[p1][cnt[p1]]
        # p2もまだ全試合を終えていない場合
        if cnt[p2] < N - 1:
            # p2が次に当たるべき選手がp1の場合 -> (p1,p2)の試合を行うことが可能
            if A[p2][cnt[p2]] == p1:
                # day = (p1,p2)の試合を行う日
                day = max(recent[p1], recent[p2]) + 1
                recent[p1] = day
                recent[p2] = day
                cnt[p1] += 1
                cnt[p2] += 1
                Q.append(p1)
                Q.append(p2)

if min(cnt) != N - 1:
    print(-1)
else:
    print(max(recent))

Submission status: Accepted

Solution code:
from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  tmp=set()
  for p1,p in enumerate(a):
    p2=p[0]
    if p1==a[p2][0]:
      tmp.add(p1)
      tmp.add(p2)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  day=0
  while True:
    day+=1
    tmp=set()
    while q:
      p1=q.popleft()
      if len(a[p1])==0: continue;
      p2=a[p1][0]
      if p1==a[p2][0]:
        tmp.add(p1)
        tmp.add(p2)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    tmp=set()
    if len(q)==0: break;
    
  for i in a:
    if i:
      print(-1)
      exit()
  print(day)


if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  q=deque([])
  tmp=set()
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      tmp.add(x)
      tmp.add(y)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  
  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    tmp=set()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if x == a[y][0]:
        tmp.add(x)
        tmp.add(y)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    if len(q)==0: break;

  for i in range(n):
    if len(a[i])!=0:
      print(-1)
      exit()
  print(day)


if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = [[int(s) - 1 for s in reversed(readline().split())] for _ in range(N)]

    M = N * (N - 1) // 2
    games = 0
    players = set(range(N))

    for d in range(1, M + 1):
        players, players_prev = set(), players
        for i in players_prev:
            if not A[i] or i in players:
                continue
            j = A[i][-1]
            if j not in players and i == A[j][-1]:
                players.add(i)
                players.add(j)
                A[i].pop()
                A[j].pop()
                games += 1

        if games == M:
            print(d)
            break

        if not players:
            print(-1)
            break

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)

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: Accepted

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

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
nums = [0 for i in range(n)]
day = 0
match = 0
flag = True
queue = collections.deque([])
temp = set()
for i in range(1, n + 1):
    i2 = a[i - 1][0]
    if a[i2 - 1][0] == i:
        if i not in temp:
            queue.append([i, i2])
            temp.add(i)
            temp.add(i2)
if not queue:
    flag = False
while queue:
    temp = []
    while queue:
        test = queue.popleft()
        match += 1
        num1, num2 = test[0], test[1]
        nums[num1 - 1] += 1
        nums[num2 - 1] += 1
        temp.append(num1)
        temp.append(num2)
    flag2 = False
    temp2 = set()
    for i in temp:
        if nums[i - 1] <= n - 2:
            new_num = a[i - 1][nums[i - 1]]
            if nums[new_num - 1] <= n - 2 and a[new_num - 1][nums[new_num - 1]] == i:
                if i not in temp2:
                    queue.append([i, new_num])
                    flag2 = True
                    temp2.add(i)
                    temp2.add(new_num)
    if flag2 == False and match < n * (n - 1) // 2:
        flag = False
        break
    day += 1

if flag == True:
    print(day)
else:
    print(-1)

Submission status: Accepted

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


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
Last = set([i for i in range(N)])
while cnt:
    flag = True
    Done = [False] * N
    L = set()
    for i in Last:
        if len(A[i]) == 0:
            continue
        if Done[i]:
            continue
        x = A[i][-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            L.add(i)
            L.add(x)
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1
    Last = L
    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)

Submission status: Accepted

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


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
Last = set([i for i in range(N)])
while cnt:
    flag = True
    Done = [False] * N
    L = set()
    for i in Last:
        if len(A[i]) == 0:
            continue
        if Done[i]:
            continue
        x = A[i][-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            L.add(i)
            L.add(x)
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1
    Last = L
    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit


def encode(i, j):
    if i < j:
        i, j = j, i
    return i * (i - 1) // 2 + j + 1


def dfs(v):
    if visited[v] == 2:
        return dp[v]
    visited[v] = 1
    for nv in g[v]:
        if visited[nv] == 1:
            print(-1)
            exit()
        dp[v] = max(dp[v], dfs(nv) + 1)
    visited[v] = 2
    return dp[v]


setrecursionlimit(10 ** 6)
N = int(input())
GAMES_CNT = N * (N - 1) // 2
g = [[] for _ in range(GAMES_CNT + 1)]
for i in range(N):
    orig = 0
    for j in map(lambda x: int(x) - 1, input().split()):
        dest = encode(i, j)
        g[orig].append(dest)
        orig = dest
dp = [0] * (GAMES_CNT + 1)
visited = [0] * (GAMES_CNT + 1)
print(dfs(0))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(now):
  res=day[now]
  if vis[now]:
    if res==-1:return -1
    else:return res
  res=1
  vis[now]=1
  for to in d[now]:
    r=dfs(to)
    if r==-1:return -1
    res=max(res,r+1)
  day[now]=res
  return res
n=int(input())
v=0
si=[[0]*n for _ in range(n)]
for i in range(n):
  for j in range(i+1,n):
    si[i][j]=v
    v+=1
d=[[] for _ in range(v)]
s=[]
for i in range(n):
  a=list(map(int,input().split()))
  if i<a[0]-1:b=si[i][a[0]-1]
  else:b=si[a[0]-1][i]
  for j in a[1:]:
    j-=1
    if i<j:
      d[b]+=[si[i][j]]
      b=si[i][j]
    else:
      d[b]+=[si[j][i]]
      b=si[j][i]
vis=[0]*v
day=[-1]*v
ans=0
for i in range(v):
  di=dfs(i)
  if di==-1:
    print(-1)
    exit()
  ans=max(ans,di)
print(ans)

Submission status: Accepted

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


def main():
    n = int(read())
    V = 1000000

    g = [[] for _ in range(V)]
    deg = [0] * V
    vlist = set()

    for i in range(n):
        a = list(map(lambda x: int(x) - 1, read().rstrip().split()))
        for j in range(n - 1):
            v1 = min(i, a[j]) * 1000 + max(i, a[j])
            vlist.add(v1)
            if j == n - 2:
                break
            v2 = min(i, a[j + 1]) * 1000 + max(i, a[j + 1])
            g[v1].append(v2)
            deg[v2] += 1

    d = [0] * V
    check_cnt = 0
    q = []
    for v in vlist:
        if deg[v] == 0:
            q.append(v)

    if len(q) == 0:
        print(-1)
        exit()

    for v in q:
        check_cnt += 1
        for nv in g[v]:
            d[nv] = max(d[nv], d[v] + 1)
            deg[nv] -= 1
            if deg[nv] == 0:
                q.append(nv)
    if check_cnt == n * (n - 1) // 2:
        print(max(d) + 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(read())
V = 1001000

g = [[] for _ in range(V)]
deg = [0] * V
vlist = set()

for i in range(1, n + 1):
    a = list(map(int, read().rstrip().split()))
    for j in range(n - 2):
        v1 = min(i, a[j]) * 1001 + max(i, a[j])
        v2 = min(i, a[j + 1]) * 1001 + max(i, a[j + 1])
        vlist.add(v1)
        vlist.add(v2)
        g[v1].append(v2)
        deg[v2] += 1

d = [0] * V
check_cnt = 0
q = []
for v in vlist:
    if deg[v] == 0:
        q.append(v)

if len(q) == 0:
    print(-1)
    exit()

for v in q:
    check_cnt += 1
    for nv in g[v]:
        d[nv] = max(d[nv], d[v] + 1)
        deg[nv] -= 1
        if deg[nv] == 0:
            q.append(nv)
if check_cnt == n * (n - 1) // 2:
    print(max(d) + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    d = dict()
    for i in range(1, n + 1):
        d[i] = input_int_list()[::-1]
    day = 0
    candi = set(range(1, n + 1))
    rest = (n * (n - 1)) // 2
    while rest:
        played = set()
        for a in candi:
            if d[a] and d[d[a][-1]][-1] and a == d[d[a][-1]][-1]:
                played.add(a)
                played.add(d[a][-1])

        if not played:
            break

        candi.clear()

        rest -= len(played) // 2
        for a in played:
            candi.add(a)
            d[a].pop()
            # if d[a]:
            #     candi.add(d[a][-1])
        day += 1

    if rest == 0:
        print(day)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    d = dict()
    for i in range(1, n + 1):
        d[i] = input_int_list()[::-1]
    day = 0
    candi = set(range(1, n + 1))
    rest = (n * (n - 1)) // 2
    while rest:
        played = set()
        for a in candi:
            if d[a] and d[d[a][-1]][-1] and a == d[d[a][-1]][-1]:
                played.add(a)
                played.add(d[a][-1])

        if not played:
            break

        candi.clear()

        rest -= len(played) // 2
        for a in played:
            candi.add(a)
            d[a].pop()
            if d[a]:
                candi.add(d[a][-1])
        day += 1

    if rest == 0:
        print(day)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    idx = [0] * N
    D = [[-1] * (N) for _ in range(N)]
    for j in range(N):
        D[j][0] = 0
    while True:
        f = True
        for i in range(N):
            if idx[i] >= N - 1: continue
            m = A[i][idx[i]]
            if A[m][idx[m]] == i:
                d = max(D[i][idx[i]], D[m][idx[m]])
                idx[i] += 1
                idx[m] += 1
                D[i][idx[i]] = d + 1
                D[m][idx[m]] = d + 1
                f = False
        if f: break
    ans = -1
    for i in range(N):
        ans = max(ans, D[i][N - 1])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, A)

Submission status: Accepted

Solution code:
N = int(input())
A = [None] * N

for i in range(N):
  A[i] = list(map(lambda x:int(x) - 1,input().split()))[::-1]
  
# A[i]の最後尾が、次に対戦する相手

# 次に試合する候補の人を全員洗い出す。最初は全員
playable = set(range(N))

day = 0
while True:
  next_playable = set() # 次の日に試合できる状態になる人
  done = set() # その日に既に試合を終えた人を管理
  for player in playable:
    if player in done:
      continue
    if len(A[player]) == 0:
      continue
    rival = A[player][-1]
    if rival in done:
      continue
    if len(A[rival]) == 0:
      continue
    if A[rival][-1] == player:
      done.add(player)
      done.add(rival)
      A[player].pop()
      A[rival].pop()
      # この二人は次の試合の探索対象となる
      next_playable.add(player)
      next_playable.add(rival)
  if len(next_playable) == 0:
    break
  playable = next_playable
  day += 1

# できる試合がなくなった状態で、全員の試合が終わっていればOK
ok = True
for i in range(len(A)):
  if len(A[i]) != 0:
    ok = False
    break
    
print((-1,day)[ok])

Submission status: Accepted

Solution code:
from collections import deque

def id(i, j):
    return v_id[min(i, j)][max(i, j)]

def TopologicalSort(graph, in_deg, N):
    sorted_v = []
    q = deque()

    for i in range(N):
        if in_deg[i] == 0:
            q.append(i)
    
    while q:
        v = q.popleft()
        for n_v in graph[v]:
            in_deg[n_v] -= 1
            if in_deg[n_v] == 0:
                q.append(n_v)
        
        sorted_v.append(v)

    if len(sorted_v) == N:
        return sorted_v
    else:
        return 0

N = int(input())
v_id = [[-1]*N for _ in range(N)]
graph = [[] for _ in range(N * (N - 1) // 2)]
in_deg = [0]*(N * (N - 1) // 2)

v = 0
for i in range(N):
    for j in range(N):
        if i < j:
            v_id[i][j] = v
            v += 1

for i in range(N):
    a = list(map(lambda x: int(x) - 1, input().split()))
    for j in range(N - 2):
        graph[id(i, a[j])].append(id(i, a[j + 1]))
        in_deg[id(i, a[j + 1])] += 1

sorted_v = TopologicalSort(graph, in_deg, N * (N - 1) // 2)

if not sorted_v:
    print(-1)
else:
    dist = [0]*(N * (N - 1) // 2)

    for v in sorted_v:
        for n_v in graph[v]:
            dist[n_v] = max(dist[n_v], dist[v] + 1)
    
    print(max(dist) + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
def hash(x,y):
    x,y =min(x,y),max(x,y)
    return x*(N+1)+y
s = set()
N = int(input())
edge = [[] for _ in range(N*N+N)]
ind = [0]*(N*N+N)
for i in range(1,N+1):
    A = list(map(int,input().split()))
    s.add(hash(i,A[0]))
    for j in range(N-2):
            edge[hash(i,A[j])].append(hash(i,A[j+1]))
            ind[hash(i,A[j+1])] += 1
d = deque()
nd = deque()
for hash in s:
    if ind[hash] == 0:
        d.append(hash)
ans = 0
finished = 0
while d:
    while d:
        hash = d.popleft()
        finished += 1
        for nhash in edge[hash]:
            ind[nhash] -= 1
            if ind[nhash] == 0:
                nd.append(nhash)
    d = nd
    nd = deque()
    ans += 1
if finished == N*(N-1)//2:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a = [list(map(int, input().split())) + [0] for i in range(n)]
for i in range(n):
    for j in range(n):
        a[i][j] -= 1
l = [0] * n
d = [0] * n
Q = deque(range(n))
while Q:
    p = Q.popleft()
    q = a[p][l[p]]
    if a[q][l[q]] == p:
        m = max(d[p], d[q]) + 1
        d[p] = m
        d[q] = m
        l[p] += 1
        l[q] += 1
        Q.append(p)
        Q.append(q)
for i in l:
    if i != n - 1:
        exit(print(-1))
print(max(d))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=[]
    inf=10**6
    for _ in range(N):
        a=LI()+[inf]
        for j in range(N-1):
            a[j]-=1
        A.append(a)
        
        
    cur=[0]*N#i番目の人が何試合消化したか
    
    st=[]# stackに，みるべき人を入れていいく，変化があった人だけ見れば良い
    nxt=[]
    
    #初日は全員みる，N>=3より初日で終わることはない
    for i in range(N):
        for j in range(i+1,N):
            if A[i][0]==j and A[j][0]==i:
                cur[i]=1
                cur[j]=1
                st.append(i)
                st.append(j)
    day=1
    
    while st:
        used=[0]*N
        day+=1
        
        while st:
            i=st.pop()#みる人
            j=A[i][cur[i]]#相手候補
            
            if used[i]==0 and used[j]==0:
                if A[j][cur[j]]==i:#マッチング
                    cur[i]+=1
                    cur[j]+=1
                    nxt.append(i)
                    nxt.append(j)
                    used[i]=1
                    used[j]=1
               
        while nxt:
            a=nxt.pop()
            if cur[a]!=N-1:
                st.append(a)
        
    if sum(cur)==N*(N-1):
        print(day)
    else:
        print(-1)
        
            
        
        
    

main()

Submission status: Accepted

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 = [[] for _ in range(N)]
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]
    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: Accepted

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)
### サイクル検出 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: Accepted

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]
    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]:
                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: Accepted

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):
    # uからdfs
    seen[u] = True
    ans = 0
    for v in ns[u]:
        if done[v]:
            ans = max(ans, vals[v]+1)
            continue
        elif seen[v]:
            # サイクルを検出
            return 1
        else:
            pos = dfs(v)
            if pos>=0:
                return 1
            ans = max(ans, vals[v]+1)
    done[u] = True
    vals[u] = ans
    return -1
ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos>=0:
        print(-1)
        break
else:
    print(max(vals)+1)

Submission status: Accepted

Solution code:
from collections import deque
def f(s,t):
  if s>t:
    a=s
    s=t
    t=a
  return n*(s-1)-s*(s-1)//2+t-s-1
n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
E=[[] for i in range(n*(n-1)//2)]
EE=[[] for i in range(n*(n-1)//2)]
B=[0]*(n*(n-1)//2)
for i in range(n):
  for j in range(n-2):
    u=f(i+1,A[i][j])
    v=f(i+1,A[i][j+1])
    EE[u].append(v)
    E[v].append(u)
    B[v]+=1
D=deque([])
V=[0]*(n*(n-1)//2)
F=[10**9]*(n*(n-1)//2)
for i in range(n*(n-1)//2):
  if B[i]==0:
    D.append(i)
    V[i]=1
    F[i]=1
while len(D)>0:
  x=D[0]
  D.popleft()
  for i in range(len(EE[x])):
    B[EE[x][i]]-=1
    if B[EE[x][i]]==0:
      D.append(EE[x][i])
      F[EE[x][i]]=F[x]+1
      V[EE[x][i]]=1
ans=-1
for i in range(n*(n-1)//2):
  if F[i]>ans:
    ans=F[i]
if ans==10**9:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
def main():
	from collections import deque
	n=int(input())
	battle=n*(n-1)//2
	lis=[[] for i in range(battle)]
	num=[-1]*(n**2)
	cnt=-1
	for x in range(n**2):
		if x//n<x%n:
			cnt+=1
			num[x]=cnt
	for i in range(n):
		a=list(map(int,input().split()))
		for j in range(n-2):
			x=a[j]-1
			y=a[j+1]-1
			px=num[min(i*n+x,x*n+i)]
			py=num[min(i*n+y,y*n+i)]
			lis[px].append(py)
	node_in=[0]*(battle)
	for i in range(battle):
		for x in lis[i]:
			node_in[x]+=1
	zero=deque([])
	days=[10**9]*(battle)
	for i in range(battle):
		if node_in[i]==0:
			zero.append(i)
			days[i]=1
	while zero:
		r=zero.popleft()
		for x in lis[r]:
			node_in[x]-=1
			if node_in[x]==0:
				zero.append(x)
				days[x]=days[r]+1
	if 10**9 in days:
		print(-1)
	else:
		print(max(days))
if __name__ == '__main__':
	main()