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 defaultdict, deque
n=int(input())
es=[]

for i in range(n):
    *A,=map(int,input().split())
    for j in range(n-2):
        a=A[j]
        x,y=min(a-1,i),max(a-1,i)
        ith=((n-x)+(n-1))*x//2-1+(y-x)
        b=A[j+1]
        x,y=min(b-1,i),max(b-1,i)
        jth=((n-x)+(n-1))*x//2-1+(y-x)
        es.append([ith, jth])
#print(es)
v=n*(n-1)//2
outs = defaultdict(list)
ins = defaultdict(int)
for i,j in es:
    outs[i].append(j)
    ins[j] += 1
#print(outs, ins)
q = deque((v1,0) for v1 in range(n*(n-1)//2) if ins[v1] == 0)
res = []
while q:
    v1,cnt = q.popleft()
    res.append((v1,cnt))
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append((v2,cnt+1))

x=len(res)
if x!=n*(n-1)//2:
    print(-1)
else:
    print(res[-1][1]+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
import time

#A
def A():
    s = S()
    t = S()
    ans = 0
    for i in range(3):
        if s[i] == t[i]:
            ans += 1
    print(ans)
    return

#B
def B():
    a, b = LI()
    ans = 0
    b -= 1
    while b > 0:
        b -= a - 1
        ans += 1
    print(ans)

    return

#C
def C():
    n = II()
    h = LI()
    i = 0
    ans = 0
    while i < n:
        down = i+1
        while down < n:
            if h[down - 1] >= h[down]:
                down += 1
            else:
                break
        ans = max(ans, down - i - 1)
        i = down
    print(ans)
    return

#D
def D():
    n = II()
    print(n * (n - 1) // 2)
    return

#E
def E():
    start = time.time()
    n = II()
    a = LIR_(n)
    ans = 0
    tern = [0] * n
    while 1:
        ans += 1
        f = True
        c = defaultdict(int)
        for i in range(n):
            if c[i]:
                continue
            if tern[i] == n - 1:
                continue
            rival = a[i][tern[i]]
            if c[rival]:
                continue
            if tern[rival] == n - 1:
                continue
            if a[rival][tern[rival]] == i:
                c[i] += 1
                c[rival] += 1
                tern[rival] += 1
                tern[i] += 1
                f = False
        if time.time() - start >= 1:
            print(n * (n - 1) // 2)
            return
        if f:
            if tern == [n - 1] * n:
                print(ans-1)
                return
            else:
                print(-1)
                return
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7


def dfs(u):
    if memo[u] == -2:
        print(-1)
        exit()
    if memo[u] != -1:
        return memo[u]
    memo[u] = -2
    res = 0
    for v in nodes[u]:
        res = max(res, dfs(v))
    memo[u] = res + 1
    return res + 1

N = INT()
NN = N * N
nodes = [set() for i in range(NN+1)]
for a in range(N):
    B = [b-1 for b in LIST()]
    for j in range(N-2):
        a1 = a2 = a
        b1 = B[j]
        b2 = B[j+1]
        if a1 > b1:
            a1, b1 = b1, a1
        if a2 > b2:
            a2, b2 = b2, a2
        nodes[a1*N+b1].add(a2*N+b2)
        if j == 0:
            nodes[NN].add(a1*N+b1)

memo = [-1] * (NN+1)
ans = dfs(NN) - 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque


def Topological_sorting(E):
    N = len(E)
    in_deg = [0]*N
    for i in range(N):        # ２重ループでO(E)
        for to_ in E[i]:
            in_deg[to_] += 1

    ans = [v for v in range(N) if in_deg[v] == 0]
    deq = deque(ans)

    while deq:                  # O(V+E)
        v = deq.popleft()
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
                deq.append(t)
    if len(ans) != N:
        return False
    return ans


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

    # 0<=i<j<Nを満たすi,jの組を整数へ対応付ける
    MP = [[0]*N for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            MP[i][j] = cnt
            MP[j][i] = cnt
            cnt += 1

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

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

    order = Topological_sorting(out)
    if order is False:
        print(-1)
        return

    # 最長パスを得る
    # 枝の格納方法から、パスは自分の下位の情報から作る。
    # post_order-likeに見る
    depth = [1]*M
    longest = 1
    for i in reversed(order):
        for u in out[i]:
            depth[i] = max(depth[i], 1+depth[u])
        longest = max(depth[i], longest)
    print(longest)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

INF = float("inf")


def Topological_sorting(E):
    N = len(E)
    in_deg = [0]*N
    for i in range(N):        # ２重ループでO(E)
        for to_ in E[i]:
            in_deg[to_] += 1

    ans = [v for v in range(N) if in_deg[v] == 0]
    deq = deque(ans)

    while deq:                  # O(V+E)
        v = deq.popleft()
        for t in E[v]:
            in_deg[t] -= 1
            if in_deg[t] == 0:
                ans.append(t)
                deq.append(t)
    if len(ans) != N:
        return False
    return ans


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

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

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

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

    order = Topological_sorting(out)
    if order is False:
        print(-1)
        return

    # 最長パスを得る
    # パスは自分より下位の情報が必要なので、post_orderで見る
    depth = [-1]*M
    longest = -1
    for i in reversed(order):
        if depth[i] == -1:
            depth[i] = 1
        for u in out[i]:
            depth[i] = max(depth[i], 1+depth[u])
        longest = max(depth[i], longest)
    print(longest)
    # print(depth)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

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

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
  N=int(input())
  A=[deque(int(a)-1 for a in input().split()) for _ in range(N)]

  P,W=[0]*N,[-1]*N
  c=deque(range(N))

  while c:
    i=c.popleft()
    j=A[i].popleft()
    W[i]=j

    if W[j]==i:
      P[i]=P[j]=max(P[i],P[j])+1
      if A[i]:
        c.append(i)
      if A[j]:
        c.append(j)

  print(-1 if any(len(a) for a in A) else max(P))

main()

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
a_list = []
for i in range(n):
    a_list.append(deque([int(aa) - 1 for aa in input().split()]))
day = 0
battle = 0
for _ in range(n * (n - 1) // 2):
    if battle == n * (n - 1) // 2:
        break
    day += 1
    battle_today = 0
    tomorrow = set([])
    if (day == 1):
        player = set([i for i in range(n)])
    for i in player:
        if len(a_list[i]) == 0:
            continue
        j = a_list[i][0]
        if (i == a_list[j][0]) & (j not in tomorrow) & (len(a_list[j]) > 0) & (i not in tomorrow):
            tomorrow.add(i)
            tomorrow.add(a_list[i][0])
            battle += 1
            battle_today += 1
            a_list[i].popleft()
            a_list[j].popleft()
    player = tomorrow
    if battle_today == 0:
        day = -1
        break
print(day)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

adj = defaultdict(list)
in_deg = defaultdict(int)
for u, row in enumerate(a, 1):
    for v1, v2 in zip(row, row[1:]):
        uu1, vv1 = min(u, v1), max(u, v1)
        uu2, vv2 = min(u, v2), max(u, v2)
        match1 = uu1 + vv1 * 1000
        match2 = uu2 + vv2 * 1000
        adj[match1].append(match2)
        in_deg[match1]
        in_deg[match2] += 1

now = [key for key, val in in_deg.items() if val == 0]
day = 0
while now:
    day += 1
    nxt = []
    for u in now:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt.append(v)

    now = nxt

if max(in_deg.values()) > 0:
    day = -1

print(day)

Submission status: Accepted

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

N = int(input().strip("\n"))
A = [list(map(lambda x :int(x)-1, input().split())) for _ in range(N)]

# 対戦カード (インデックス0>インデックス[1]だけ使う)
all_patterns = [[[] for _ in range(N)] for _ in range(N)]
lines_to_here = [[0 for _ in range(N)] for _ in range(N)]

for i in range(len(A)):
    for j in range(len(A[i])-1):
        playerA = i
        playerB = A[i][j]
        if playerA < playerB:
            playerA, playerB = playerB, playerA
        next_playerA = i
        next_playerB = A[i][j+1]
        if next_playerA < next_playerB:
            next_playerA, next_playerB = next_playerB, next_playerA
        
        all_patterns[playerA][playerB].append((next_playerA,next_playerB))
        lines_to_here[next_playerA][next_playerB] += 1

next_out = deque()
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] == 0:
            next_out.append([i,j])

if len(next_out) == 0:
    print(-1)
    sys.exit()
    

indexin_topological_sorted = [[0 for _ in range(N)] for _ in range(N)]

# topological sort
topological_sorted = []
while len(next_out) > 0:
    added = next_out.pop()
    topological_sorted.append(added)
    indexin_topological_sorted[added[0]][added[1]] = len(topological_sorted)-1
    for direction in all_patterns[added[0]][added[1]]:
        lines_to_here[direction[0]][direction[1]]-=1
        if lines_to_here[direction[0]][direction[1]] == 0:
            next_out.append(direction)

# if there is closed circuit, number remain(not 0 exists)
for i in range(1,N):
    for j in range(i):
        if lines_to_here[i][j] > 0:
            print(-1)
            sys.exit()

costs = [0 for _ in range(len(topological_sorted))]

max_cost = 0
for i in range(len(topological_sorted)):
    processing = topological_sorted[i]
    now_cost = costs[i]
    for direction in all_patterns[processing[0]][processing[1]]:
        direction_in_topological_sorted = indexin_topological_sorted[direction[0]][direction[1]]        
        costs[direction_in_topological_sorted] = max(1+now_cost,costs[direction_in_topological_sorted])
        max_cost = max(max_cost,costs[direction_in_topological_sorted])
print(max_cost+1)

Submission status: Accepted

Solution code:
#https://qiita.com/vain0x/items/fbde8b66927b84080811
#http://kmjp.hatenablog.jp/entry/2019/09/01/1000
#2人の選手が互いに相手を次の対戦相手に指定しているとき以外組めない
#したがって貪欲で一意

n = int(input())
a = []

for i in range(n):
    ai = list(map(int, input().split( )))
    ai.reverse()
    for j in range(n-1):
        ai[j]-=1
    a.append(ai)

##キューの管理のどこがおかしいかわからなかったがあきらめる

can={i for i in range(n)}
nxt=set()
cnt = 0
rem=n*(n-1)//2
while rem:
    cnt+=1
    for i in can:
        if i not in nxt and a[i]:
            p = a[i][-1]
            if p not in nxt:##この判定しないと1日に複数回試合することになる
                if a[p][-1]==i:
                    a[p].pop();a[i].pop()
                    nxt.add(i);nxt.add(p)
    rem-=len(nxt)//2

    can=nxt.copy()###copy
    nxt=set()
    if not can:
        break
       
if rem:
    print(-1)
else:       
    print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input().strip("\n"))
ALL = N*(N-1)//2
A = [deque(list(map(lambda x :int(x)-1, input().split()))) for _ in range(N)]

day = 0
candidates = set(range(N))
while len(candidates)>0:
    day += 1
    nextday = set()
    checked = set()
    #print(candidates)
    for candidate in candidates:
        if len(A[candidate]) == 0:
            continue
        if candidate in checked:
            continue
        opponent = A[candidate][0]
        if opponent in checked:
            continue
        if A[opponent][0] == candidate:
            A[opponent].popleft()
            A[candidate].popleft()
            nextday.add(candidate)
            nextday.add(opponent)
            checked.add(candidate)
            checked.add(opponent)
    candidates = nextday

for p in A:
    if len(p) > 0:
        print(-1)
        break
else:
    print(day-1)

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for _ in range(n ** 2)]
inv = [0] * (n ** 2)
for i in range(n):
    a = list(map(lambda x: int(x)-1, input().split()))
    for j in range(n - 2):
        p, q = min(i, a[j]), max(i, a[j])
        r, s = min(i, a[j + 1]), max(i, a[j + 1])
        g[p * n + q].append(r * n + s)
        inv[r * n + s] += 1
s = []
for i in range(n):
    for j in range(i + 1, n):
        if inv[i * n + j] == 0:
            s.append(i * n + j)
d = [0] * (n ** 2)
while s:
    p = s.pop()
    for node in g[p]:
        d[node] = max(d[node], d[p] + 1)
        inv[node] -= 1
        if inv[node] == 0:
            s.append(node)
for i in range(n):
    for j in range(i + 1, n):
        if inv[i * n + j] > 0:
            print(-1)
            exit(0)
print(max(d) + 1)

Submission status: Accepted

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

def main():
    N = int(input())
    memo = []
    base = 0
    for i in range(N-1):
        memo.append(base)
        base += N-i-1
    edge = [[] for _ in range((N*(N-1))//2)]
    IN = [0]*((N*(N-1))//2)
    
    for i in range(N):
        a = list(map(int,input().split()))
        b = []
        for j in a:
            j -= 1
            if i < j:
                b.append(memo[i]+j-i-1)
            else:
                b.append(memo[j]+i-j-1)
        for i in range(N-2):
            edge[b[i]].append(b[i+1])
            IN[b[i+1]] += 1

    def t_sort():
        que = deque([i for i,c in enumerate(IN) if c == 0])
        l = []
        while que:
            now = que.popleft()
            l.append(now)
            for fol in edge[now]:
                IN[fol] -= 1
                if IN[fol] == 0:
                    que.append(fol)
        if len(l) != (N*(N-1))//2:
            print(-1)
            exit()
        return l
    
    ts = t_sort()
    dp = [1]*((N*(N-1))//2)
    for now in ts:
        for fol in edge[now]:
            dp[fol] = max(dp[fol],dp[now]+1)
    
    print(max(dp))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
n=int(input())
m=[]
for i in range(n):
  a=list(map(int,input().split()))
  a.reverse()
  m.append(a)
ans=0
count=0
failflag=0
previous=set()
for i in range(n):
  previous.add(i)
while count<(n*(n-1)):
  ans+=1
  tempcount=count
  r=set()
  for i in previous:
    if m[i]:
      t=m[i][-1]
      if m[t-1]:
        if m[t-1][-1]==i+1:
          count+=1
          r.add(i)
          r.add(t-1)
  previous=set()
  for k in r:
    m[k].pop()
    previous.add(k)
    if m[k]:
      previous.add(m[k][-1]-1)
  if tempcount==count:
    failflag=1
    break
if failflag==1:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

c = [0 for _ in range(N+1)]
p = []

for i in range(1, N+1):
    j = A[i][c[i]]
    if i==A[j][c[j]] and i<j:
        p.append((i,j))

ans = 0
while p:
    q = []
    for i,j in p:
        c[i] += 1
        c[j] += 1
        if c[i] < N-1:
            k = A[i][c[i]]
            if A[k][c[k]] == i:
                q.append((i,k))
        if c[j] < N-1:
            k = A[j][c[j]]
            if A[k][c[k]] == j:
                q.append((j,k))
    ans += 1
    p = q

ans = (ans if all(c[i]==N-1 for i in range(1, N+1)) else -1)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


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

    days = 0
    ta = [i for i in range(N)]
    while True:
        ta2 = []
        aset = set()
        for i in ta:
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta2.append(i)
                ta2.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta2) > 0:
            for t in ta2:
                A[t].popleft()
            days += 1
            ta = ta2
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()


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

    # print(A)

    days = 0
    ta = [i for i in range(N)]
    while True:
        ta2 = []
        aset = set()
        for i in ta:
            if len(A[i]) == 0 or i in aset:
                continue
            if i == A[A[i][0]][0]:
                ta2.append(i)
                ta2.append(A[i][0])
                aset |= set([i])
                aset |= set([A[i][0]])
        if len(ta2) > 0:
            for t in ta2:
                A[t].pop(0)
            days += 1
            ta = ta2
        else:
            break

    empty = True
    for i in range(N):
        if len(A[i]) != 0:
            empty = False
            break

    if empty:
        print(days)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# 次に試合したい相手をdequeで管理
# お互いの試合したい相手(dequeの先頭)が一致すれば試合できる
# 次の日のチェック対象は「前日に試合した人」だけ。これをキュー管理

import sys
readline = sys.stdin.readline

N = int(readline())
ALL = (N * (N - 1)) // 2 # 試合数

from collections import deque
player = [None] * N
for i in range(N):
  player[i] = deque(list(map(lambda x:int(x) - 1,readline().split())))
  
# 明日試合する候補の人
q = set(range(N))

day = 0
while q:
  day += 1
  nextday = set()
  checked = set()
  for p in q:
    if p in checked:
      continue
    if len(player[p]) == 0:
      continue
    op = player[p][0] # 次の対戦相手
    if op in checked:
      continue
    if player[op][0] == p:
      # 試合成立
      player[p].popleft()
      player[op].popleft()
      checked.add(op)
      checked.add(p)
      if player[p]:
        nextday.add(p)
      if player[op]:
        nextday.add(op)
  q = nextday 

for p in player:
  if len(p) > 0:
    print(-1)
    break
else:
  print(day)

Submission status: Accepted

Solution code:
# PyPy3 (2.4.0)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
from collections import defaultdict, deque
class DAG:
    def __init__(self, adjList, inDegreeArray):
        self.A = adjList
        self.In = inDegreeArray
        self.n = len(inDegreeArray)
        self.depth = [-1]*(self.n)
        self.nodes = []

    def sort(self):
        dq = deque()
        # 入次数が 0 の頂点を deque に入れる
        for i in range(self.n):
            if self.In[i] == 0:
                dq.append(i)
                self.depth[i] = 0
        while dq:
            v1 = dq.popleft()
            self.nodes.append(v1)
            for v2 in self.A[v1]:
                self.In[v2] -= 1
                self.depth[v2] = max(self.depth[v2], self.depth[v1] + 1)
                if In[v2] == 0:
                    dq.append(v2)
    
    def get_node_array(self):
        if len(self.nodes) == self.n:
            return self.nodes
        else:
            return []
    
    def get_depth(self):
        if len(self.depth) == self.n:
            return self.depth
        else:
            return []

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]

# 試合と頂点の対応表
M = [[-1 for _ in range(N)] for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1

# 試合 j が 試合 i の翌日以降にしか行えない -> G[i][j]

G = [[] for _ in range((N*(N-1)//2))]
# 頂点(試合) の入次数
In = [0]*(N*(N-1)//2)
# 入力からグラフ, 配列を生成
for i in range(N):
    for j in range(N-2):
        gagem_id = M[i][ A[i][j] - 1 ]
        next_game_id = M[i][ A[i][j+1] - 1 ]
        G[gagem_id].append(next_game_id)
        In[next_game_id] += 1

dag = DAG(G, In)
dag.sort()
node = dag.get_node_array()
depth = dag.get_depth()

if len(node) == 0:
    print(-1)
else:
    print(max(depth) + 1)

Submission status: Accepted

Solution code:
# PyPy3 (2.4.0)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
from collections import defaultdict, deque
class DAG:
    def __init__(self, adjList, inDegreeArray):
        self.A = adjList
        self.In = inDegreeArray
        self.n = len(inDegreeArray)
        self.depth = [-1]*(self.n)
        self.nodes = []

    def sort(self):
        dq = deque()
        # 入次数が 0 の頂点を deque に入れる
        for i in range(self.n):
            if self.In[i] == 0:
                dq.append(i)
                self.depth[i] = 0
        while dq:
            v1 = dq.popleft()
            self.nodes.append(v1)
            for v2 in self.A[v1]:
                self.In[v2] -= 1
                self.depth[v2] = max(self.depth[v2], self.depth[v1] + 1)
                if In[v2] == 0:
                    dq.append(v2)
    
    def get_node_array(self):
        if len(self.nodes) == self.n:
            return self.nodes
        else:
            return []
    
    def get_depth(self):
        return self.depth

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]

# 試合と頂点の対応表
M = [[-1 for _ in range(N)] for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1

# 試合 j が 試合 i の翌日以降にしか行えない -> G[i][j]

G = [[] for _ in range((N*(N-1)//2))]
# 頂点(試合) の入次数
In = [0]*(N*(N-1)//2)
# 入力からグラフ, 配列を生成
for i in range(N):
    for j in range(N-2):
        gagem_id = M[i][ A[i][j] - 1 ]
        next_game_id = M[i][ A[i][j+1] - 1 ]
        G[gagem_id].append(next_game_id)
        In[next_game_id] += 1

dag = DAG(G, In)
dag.sort()
node = dag.get_node_array()
depth = dag.get_depth()

if len(node) == 0:
    print(-1)
else:
    print(max(depth) + 1)

Submission status: Accepted

Solution code:
# PyPy3 (2.4.0)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
from collections import defaultdict, deque
class DAG:
    def __init__(self, adjList, inDegreeArray):
        self.A = adjList
        self.In = inDegreeArray
        self.n = len(inDegreeArray)
        self.depth = [-1]*(self.n)
        self.nodes = []

    def sort(self):
        dq = deque()
        # 入次数が 0 の頂点を deque に入れる
        for i in range(self.n):
            if self.In[i] == 0:
                dq.append(i)
                self.depth[i] = 0
        while dq:
            v1 = dq.popleft()
            self.nodes.append(v1)
            for v2 in self.A[v1]:
                self.In[v2] -= 1
                self.depth[v2] = max(self.depth[v2], self.depth[v1] + 1)
                if In[v2] == 0:
                    dq.append(v2)
    
    def get_node_array(self):
        return self.nodes
    
    def get_depth(self):
        return self.depth

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]

# 試合と頂点の対応表
M = [[-1 for _ in range(N)] for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1

# 試合 j が 試合 i の翌日以降にしか行えない -> G[i][j]

G = [[] for _ in range((N*(N-1)//2))]
# 頂点(試合) の入次数
In = [0]*(N*(N-1)//2)
# 入力からグラフ, 配列を生成
for i in range(N):
    for j in range(N-2):
        gagem_id = M[i][ A[i][j] - 1 ]
        next_game_id = M[i][ A[i][j+1] - 1 ]
        G[gagem_id].append(next_game_id)
        In[next_game_id] += 1

dag = DAG(G, In)
dag.sort()
node = dag.get_node_array()
depth = dag.get_depth()

if len(node) != len(In):
    print(-1)
else:
    print(max(depth) + 1)

Submission status: Accepted

Solution code:
import sys
N = int(input())
T = []
for i in range(N):
    a = [i-1 for i in map(int,input().split())]
    T.append(a)

update = list(range(N))
ans = 0
L = [N-1]*N
while(True):
    K = []
    M = [0]*N
    for i in update:
        if L[i] != 0 and M[i] == 0:
            s = T[i][0]
            if L[s] != 0:
                if T[s][0] == i and M[s] == 0:
                    K.append(i)
                    K.append(s)
                    M[i] = 1
                    M[s] = 1
    for j in K:
        del T[j][0]
        L[j] -= 1
    if len(K) == 0:
        break
    ans += 1
    update = K

for i in range(N):
    if L[i] != 0:
        print(-1)
        sys.exit()
print(ans)