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:

from collections import deque

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


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    # 互いの初めに戦うべき相手がお互いであれば、そのペアで試合を行う
    if next_opponent[b] == a:
        # a,bが今までに試合した回数の多いほう+1（同じ人が日に二度試合を行えないので）
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))

Submission status: Accepted

Solution code:

from collections import deque

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


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
a=[]
for i in range(n):
    a.append(deque(map(lambda x:int(x)-1,input().split())))

nofrag=False
last=[0]*n
for i in range(n):
    stack=[(i,j) for j in list(a[i])[::-1]]
    check=[0]*n
    while stack:
        me,to=stack[-1]
        if a[to][0]==me:#お互いにpop
            a[to].popleft()
            a[me].popleft()
            day=max(last[me],last[to])+1
            last[to]=day
            last[me]=day
            stack.pop()
            check[me]=0
        else:#stackに追加し、自分のチェックもいれる
            if check[to]:#不可能
                nofrag=True
                break
            check[me]=1
            stack.append((to,a[to][0]))
    if nofrag:
        break

if nofrag:
    print(-1)
else:
    print(max(last))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = []
    for _ in range(n):
        a.append(deque(list(map(int, input().split()))))
    
    siai = n*(n-1)
    d = [0]*n

    while siai:
        f = 0
        for i in range(n):
            while a[i] and a[a[i][0]-1][0] == i+1:
                f = 1
                day = max(d[i], d[a[i][0]-1])
                d[i] = day + 1
                d[a[i][0]-1] = day + 1
                siai -= 2
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if not f:
            print(-1)
            break
    else:
        print(max(d))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# BFS的にやるDAGの最長経路
from collections import deque
import copy
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
v=n*(n-1)//2
# 試合を格納
b=[[] for i in range(v)]
# 入次数を記録
indeg = [0 for _ in range(v)]

for i in range(n):
    for j in range(n-1):
        # i+1<a[i][j]で統一
        if i+1>a[i][j]:
            x=a[i][j]
            y=i+1
        else:
            x=i+1
            y=a[i][j]
        # 試合を頂点に変換
        a[i][j]=(n-1+n-x+1)*(x-1)//2+y-x-1
    for j in range(n-2):
        indeg[a[i][j+1]]+=1
        b[a[i][j]].append(a[i][j+1])

dp = [0 for _ in range(v)]
q = deque([])
# 最長辺の候補を入れる
for i in range(v):
    if indeg[i] == 0:
        q.append(i)

while q:
    v = q.popleft()
    for w in b[v]:
        indeg[w] -= 1
        if indeg[w] == 0:
            q.append(w)
            dp[w] = max(dp[w], dp[v] + 1)

# indegが全てゼロになってなければ閉路あり
if sum(indeg)!=0:
    print(-1)
else:
    # 最長経路
    print(max(dp)+1)

Submission status: Accepted

Solution code:
n = int(input())
from collections import defaultdict
link = defaultdict(list)
inc = defaultdict(int)
chg=10**6
for i in range(n):
    tmp=list(map(int,input().split()))
    for j in range(len(tmp)-1):
        me1 = min(i,tmp[j]-1)
        opp1 = max(i,tmp[j]-1)
        me2 = min(i,tmp[j+1]-1)
        opp2 = max(i,tmp[j+1]-1)
        now = me1*chg+opp1
        nxt = me2*chg+opp2
        link[now].append(nxt)
        inc[nxt]+=1

s=[]
for i in range(n):
    for j in range(i+1,n):
        if inc[i*chg+j]==0:
            s.append(i*chg+j)
res=[]
while s:
    nxt=s.pop()
    res.append(nxt)
    for m in link[nxt]:
        inc[m]-=1
        if inc[m]==0:
            s.append(m)
if len(res)!=((n-1)*n)//2:
    print(-1)
    exit()

path=defaultdict(lambda: -1)
for now in res:
    if path[now]==-1:
        path[now]=0
    for nxt in link[now]:
        path[nxt] = max(path[nxt],path[now]+1)
print(max(path.values())+1)

Submission status: Accepted

Solution code:
#閉路判定
#n=頂点数 e=隣接リスト
#flag=0...DAG判定　flag=1...トポロジカルソート
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in edge[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in edge[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t

n=int(input())
edge=[[]for _ in range(n*n)]
inp=[1]*n*n
p=lambda x,y:min(x,y)*n+max(x,y)
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,n-1):
    edge[p(i,a[j-1]-1)].append(p(i,a[j]-1))
if find_loop(n*n,edge,0)==False:print(-1);exit()
t=find_loop(n*n,edge,1)
ans=[1]*n*n
for i in t:
  for j in edge[i]:ans[j]=max(ans[j],ans[i]+1)
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
x=lambda i:int(i)-1
a=[deque(list(map(x,input().split()))+[-1]) for _ in range(n)] 
tcnt,ans=n*(n-1),0
chk=set(range(n))
while tcnt>0:
    chk_next=set()
    for i in chk:
        if a[a[i][0]][0]==i:
            chk_next.add(i)
    if len(chk_next)==0:
        ans=-1
        break
    tcnt-=len(chk_next)
    chk=set()
    for i in chk_next:
        a[i].popleft()
        chk.add(i)
        if a[i][0]!=-1:
            chk.add(a[i][0])
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
vs = n * (n - 1) // 2

vmap = {}
c = 0
for i in range(n):
    for j in range(i):
        vmap[(i, j)] = c
        vmap[(j, i)] = c
        c += 1

edges = [[] for _ in range(vs)]
numin = [0] * vs
for i in range(n):
    for j in range(n - 2):
        j1 = a[i][j] - 1
        j2 = a[i][j + 1] - 1
        edges[vmap[(i, j1)]].append(vmap[(i, j2)])
        numin[vmap[(i, j2)]] += 1

order = []
day = [1] * vs
q = [i for i in range(vs) if numin[i] == 0]
while len(q) > 0:
    index = q.pop(0)
    order.append(index)
    d = day[index]
    for i in edges[index]:
        numin[i] -= 1
        if numin[i] == 0:
            q.append(i)
            day[i] = max(day[i], d + 1)

print(max(day) if len(order) == vs else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    n = int(input())
    n_prev = [[2 for j in range(n)] for i in range(n)]
    post_matches = [[[] for j in range(n)] for i in range(n)]
    q = []
    for i in range(n):
        ai = list(map(int, input().split()))
        ai = [x - 1 for x in ai]
        for j in range(n - 1):
            x = min(i, ai[j])
            y = max(i, ai[j])
            if j == 0:
                n_prev[x][y] -= 1
                if n_prev[x][y] == 0:
                    q.append((x, y))
            else:
                xp = min(i, ai[j - 1])
                yp = max(i, ai[j - 1])
                post_matches[xp][yp].append((x, y))

    time = 0
    while q:
        time += 1
        qn = []
        while q:
            i, j = q.pop()
            for i2, j2 in post_matches[i][j]:
                n_prev[i2][j2] -= 1
                if n_prev[i2][j2] == 0:
                    qn.append((i2, j2))
        q = qn

    for i in range(n):
        for j in range(i + 1, n):
            if n_prev[i][j] > 0:
                print(-1)
                return
    print(time)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    n = int(input())
    n_prev = [[2 for j in range(n)] for i in range(n)]
    post_matches = [[[] for j in range(n)] for i in range(n)]
    q = []
    for i in range(n):
        ai = list(map(int, input().split()))
        for j in range(n - 1):
            x = min(i, ai[j] - 1)
            y = max(i, ai[j] - 1)
            if j == 0:
                n_prev[x][y] -= 1
                if n_prev[x][y] == 0:
                    q.append((x, y))
            else:
                xp = min(i, ai[j - 1] - 1)
                yp = max(i, ai[j - 1] - 1)
                post_matches[xp][yp].append((x, y))

    time = 0
    while q:
        time += 1
        qn = []
        while q:
            i, j = q.pop()
            for i2, j2 in post_matches[i][j]:
                n_prev[i2][j2] -= 1
                if n_prev[i2][j2] == 0:
                    qn.append((i2, j2))
        q = qn

    for i in range(n):
        for j in range(i + 1, n):
            if n_prev[i][j] > 0:
                print(-1)
                return
    print(time)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
input=sys.stdin.readline
n=int(input())
a=[deque(list(map(int,input().split()))) for _ in range(n)]
def find(cand):
  s=set()
  for i in cand:
    if a[i] and a[a[i][0]-1]:
      if i==a[a[i][0]-1][0]-1:
        s.add(i)
        s.add(a[i][0]-1)
  for i in s:
    a[i].popleft()
  return len(s),s
cand=set(range(n))
game=n*(n-1)//2
ans=0
while 1:
  num,cand=find(cand)
  if num==0:
    print(-1)
    break
  ans+=1
  game-=num//2
  if game==0:
    print(ans)
    break

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        dp[x] = max(dp[x], dfs(y)+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1 for i in range(allv)]
done = [False for i in range(allv)]
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, dfs(i))
print(ans)

Submission status: Accepted

Solution code:
def toId(i, j):
    pair = A[i][j]
    if i > pair:
        i, pair = pair, i
    return ids[i][pair]

def dfs(x):
    if dp[x] != -1:
        if done[x]:
            return dp[x]
        else:
            return -1
    dp[x] = 1
    for y in G[x]:
        res = dfs(y)
        if res == -1:
            return -1
        dp[x] = max(dp[x], dfs(y)+1)
    done[x] = True
    return dp[x]

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
ids = [[0]*N for i in range(N)]
num = 0
for i in range(N):
    for j in range(N):
        if i < j:
            ids[i][j] = num
            num += 1
allv = N*N
G = [[] for i in range(allv)]
for i in range(N):
    for j in range(N-2):
        G[toId(i,j+1)].append(toId(i,j))
dp = [-1 for i in range(allv)]
done = [False for i in range(allv)]
ans = 0
for i in range(allv):
    res = dfs(i)
    if res == -1:
        print(-1)
        exit()
    ans = max(ans, dfs(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = set()
    que2 = []
    for n in que:
        if n in done: continue
        pair = A[n][cur[n]]
        if pair in done: continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done.add(n)
            done.add(pair)
            if cur[n] < N-1: que2.append(n)
            if cur[pair] < N-1: que2.append(pair)
    if len(done) > 0: ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1: ok = False
if ok: print(ans)
else: print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(lambda n: int(n)-1, input().split())) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
#ABC139-E League
"""
全試合を頂点として、試合の順序を、先にやる試合→後にやる試合
で辺を張る。この時、後にやる試合の入次数を保持する。
入次数が0である試合は、それより前にやる試合が無いと言えるので、そのような試合から行っていく。
その頂点から出ている辺の入次数を-1する。
これを繰り返した結果、全試合(n(n-1)/2)が行えていればかかった日数を、
そうでないなら-1を出力する。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
edge = [[] for _ in range(2*(10**6))] #桁ずらしで管理。
dim_in = [-1]*(2*(10**6)) #-1のままなら、使われなかったことになる
dig = 10**3
for i in range(n):
    lst1 = list(map(int,readline().split()))
    fr = None
    for j in lst1:
        go = max(i,j-1) + min(i,j-1)*dig
        if fr != None:
            if dim_in[fr] < 0:
                dim_in[fr] = 0
            if dim_in[go] < 0:
                dim_in[go] = 0
            edge[fr].append(go)
            dim_in[go] += 1
        fr = go

#初日に行える試合を求める
can_game = []
count = 0
for idx,i in enumerate(dim_in):
    if i == 0:
        count += 1
        can_game.append(idx)

day = 0
while len(can_game) > 0:
    next_game = []
    for i in can_game:
        for j in edge[i]:
            dim_in[j] -= 1
            if dim_in[j] == 0:
                count += 1
                next_game.append(j)
    can_game = next_game
    day += 1

if count >= n*(n-1)//2:
    print(day)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = [LIST() for i in range(N)]

match_id = [[0] * N  for i in range(N)]


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

def toid(i, j):
    if i > j:
        i, j = j, i
    return match_id[i][j]

V = N * (N - 1) // 2
gout = [[] for _ in range(V)]
deg = [0] * V
for i in range(N):
    for j in range(N - 2):
        gout[toid(i, A[i][j]-1)].append(toid(i, A[i][j+1]-1))
        deg[toid(i, A[i][j+1]-1)] += 1

topo = [v for v in range(V) if deg[v] == 0]
day = [0] * V
q = deque(topo)
ans = 0
while q:
    v = q.popleft()
    for t in gout[v]:
        deg[t] -= 1
        if deg[t] == 0:
            q.append(t)
            day[t] = day[v] + 1
            ans = day[t]
if any(deg):
    # まだ1とかがある
    print(-1)
    exit()
print(ans + 1)

Submission status: Accepted

Solution code:
n = int(input())
# キュー
from collections import deque

a = [None] * (n+1)
for i in range(1,n+1):
    a_tmp = tuple(map(int, input().split()))
    a[i] = deque(a_tmp)

d = deque(range(1,n+1))

ans = 0
games = 0
while(True):
    players = set()
    while(d):
        tmp = d.pop()
        next = a[tmp][0]
        if(a[next][0] == tmp):
            players.add(tmp)
            players.add(next)

    if(len(players)==0):
        break

    for i in players:
        games += 1
        a[i].popleft()
        if(a[i]):
            d.append(i)

    ans += 1

if(games == n*(n-1)):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 4
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print(n*(n-1)//2)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(n):
    for j in range(n-1):
        a[i][j]-=1
    a[i].reverse()
# print(a)
day=[0]*n
pair=[-1]*n

q=deque(range(n))

while q:
    me=q.popleft()
    if not a[me]:
        continue
    oppo=a[me].pop()
    if pair[oppo]==me:
        now=max(day[me],day[oppo])+1
        day[me]=now
        day[oppo]=now
        q.append(me)
        q.append(oppo)
    else:
        pair[me]=oppo


for i in range(n):
    if a[i]:
        print(-1)
        break
else:
    print(max(day))

Submission status: Accepted

Solution code:
from collections import deque

def is_not_empty(A):
    for x in A:
        if x: return True
    return False

N = int(input())
A = [deque([int(i) - 1 for i in input().split()]) for _ in range(N)]

ans = 0
yesterday = set(range(N))
while is_not_empty(A):
    today = set()
    for my in yesterday:
        if not A[my]: continue
        if my in today: continue
        enemy = A[my][0]
        if my == A[enemy][0] and enemy not in today:
            today.add(A[my].popleft())
            today.add(A[enemy].popleft())

    if not today:
        ans = -1
        break

    ans += 1
    yesterday = today

print(ans)

Submission status: Accepted

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

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

for i in range(N):
    for j in range(i+1, N):
        serial[i][j] = c
        serial[j][i] = c
        c += 1
        
ins = [0]*(N*(N-1)//2)
outs = defaultdict(list)

for i in range(N):
    for j in range(1, N-1):
        s = serial[i][A[i][j-1]-1]
        t = serial[i][A[i][j]-1]
        ins[t] += 1
        outs[s].append(t)

q = deque([i for i in range(N*(N-1)//2) if ins[i]==0])
ans = 0

while True:
    if len(q)==0:
        break
    
    nq = deque([])
    
    while q:
        v = q.popleft()
        
        for nv in outs[v]:
            ins[nv] -= 1
            
            if ins[nv]==0:
                nq.append(nv)
    
    ans += 1
    q = nq

if ins!=[0]*(N*(N-1)//2):
    print(-1)
    exit()
    
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[[] for i in range(0,N)]
nodes=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        nodes.append((i,j))

order={i:[0 for j in range(0,N)] for i in range(0,N)}
for i in range(0,N):
    A[i]=list(map(int,input().split()))
    for j in range(0,N-1):
        order[i][A[i][j]-1]=j
        #i番目の人がj番目の人と戦うのが何番目か


q=set([])
for battle in nodes:
    i,j=battle
    if order[i][j]==0 and order[j][i]==0:
        q.add(battle)

flag=[0 for i in range(0,N)]

day=0
sub=set([])
while q:
    while q:
        i,j=q.pop()
        flag[i]+=1
        flag[j]+=1
        if flag[i]!=N-1:
            s=A[i][order[i][j]+1]-1
            if flag[s]>=order[s][i]:
                sub.add((i,s))
        if flag[j]!=N-1:
            t=A[j][order[j][i]+1]-1
            if flag[t]>=order[t][j]:
                sub.add((j,t))

        if not q:
            day+=1
            q=sub
            sub=set([])
            break

able=True
for i in range(0,N):
    if flag[i]!=N-1:
        able=False

if able:
    print(day)
else:
    print(-1)

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

A = [[-1]] + A


def check(a, q=[]):
    if not A[a]:
        return False

    b = A[a][-1]
    b_op = A[b][-1]

    ok = False
    if a == b_op:
        ok = True

        if b < a:
            a, b = b, a
        q.append((a, b))

    return ok


q = []
for i in range(1, N + 1):
    check(i, q)

q = list(set(q))

day = 0
while q:
    nq = []
    for a, b in q:
        A[a].pop()
        A[b].pop()
        check(a, nq)
        check(b, nq)

    day += 1
    q = list(set(nq))

for i in range(1, N + 1):
    if len(A[i]) != 0:
        print(-1)
        exit()

print(day)
exit()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque([(i, x) for x in lr()]) for i in range(1, N+1)]
day = 0
candidate = {A[i][0] for i in range(N)}
match = 0

while candidate:
    day += 1
    used = set()
    next = set()
    for a, b in candidate:
        if a in used or b in used:
            continue
        if A[b-1][0] == (b, a):
            match += 1
            A[a-1].popleft()
            A[b-1].popleft()
            if A[a-1]:                
                next.add(A[a-1][0])
            if A[b-1]:
                next.add(A[b-1][0])
            used.add(a)
            used.add(b)
    if match == N * (N-1) // 2:
        break
    candidate = next
    if not used:
        print(-1); exit()

print(day)
#

Submission status: Accepted

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque([(i, x) for x in lr()]) for i in range(1, N+1)]
day = 0
candidate = {A[i][0] for i in range(N)}
match = 0

while candidate:
    day += 1
    used = set()
    next = set()
    for a, b in candidate:
        if a in used or b in used:
            continue
        if A[b-1][0] == (b, a):
            match += 1
            A[a-1].popleft()
            A[b-1].popleft()
            if A[a-1]:                
                next.add(A[a-1][0])
            if A[b-1]:
                next.add(A[b-1][0])
            used |= {a, b}
    if match == N * (N-1) // 2:
        break
    candidate = next
    if not used:
        print(-1); exit()

print(day)
# 10

Submission status: Accepted

Solution code:
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque([(i, x) for x in lr()]) for i in range(1, N+1)]
day = 0
candidate = set()
match = 0
for i in range(N):
    c = A[i][0]
    candidate.add(c)

while candidate:
    day += 1
    used = set()
    next = set()
    for a, b in candidate:
        if a in used or b in used:
            continue
        if A[b-1][0] == (b, a):
            match += 1
            A[a-1].popleft()
            A[b-1].popleft()
            if A[a-1]:                
                next.add(A[a-1][0])
            if A[b-1]:
                next.add(A[b-1][0])
            used.add(a)
            used.add(b)
    if match == N * (N-1) // 2:
        break
    candidate = next
    if not used:
        print(-1); exit()

print(day)
# 10

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        if r[x] != None:
            return 1
        f = 1
        res = 0
        for y in v[x]:
            if d[y]:
                d[y] = 0
                f &= dfs(y)
                d[y] = 1
            else:
                res = float("inf")
                f = 0
                break
            if res < r[y]:
                res = r[y]
        r[x] = res+1
        return f

    n = I()
    a = LIR(n)
    N = n*(n-1)
    f = [0]*N
    v = [[] for i in range(N)]
    lis = set()
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
        k = a[i][0]
        x = n*min(i,k)+max(i,k)
        for j in range(1,n-1):
            l = a[i][j]
            y = n*min(i,l)+max(i,l)
            v[y].append(x)
            f[x] += 1
            lis.add(x)
            lis.add(y)
            x = y
    if min([f[i] for i in lis]):
        print(-1)
        return
    d = [1]*N
    r = defaultdict(lambda : None)
    for i in lis:
        if not f[i]:
            d[i] = 0
            if not dfs(i):
                print(-1)
                return
    print(max(r.values()))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N=int(input())
def proc(x):
  return int(x)-1
from collections import deque
A=[deque(list(map(proc,input().split()))+[-1]) for i in range(N)]

ans = 0
rest = N*(N-1)
cand = set(range(N))
while rest>0:
  cand_next=set()
  for n in cand:
    if A[A[n][0]][0]==n:
      cand_next.add(n)
  if len(cand_next)==0:
    ans=-1
    break
  rest-=len(cand_next)
  cand=set()
  for n in cand_next:
    A[n].popleft()
    cand.add(n)
    if A[n][0]!=-1:
      cand.add(A[n][0])
  ans+=1
    

print(ans)