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:
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(lr()) for _ in range(N)]
answer = 0
match = 0
candidate = list(range(N))
while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0] - 1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

Submission status: Accepted

Solution code:
import sys
import copy
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(lr()) for _ in range(N)]

answer = 0
match = 0

candidate = list(range(N))
while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

Submission status: Accepted

Solution code:
import sys
import copy
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(lr()) for _ in range(N)]

match = 0
candidate = []
used = set()
for i in range(N):    
    bool = False
    if len(A[i]) == 0:
        continue
    op = A[i][0] - 1
    if op in used or i in used:
        continue
    if A[op][0]-1 == i:
        used.add(i)
        used.add(op)
        candidate.extend([i, op])
        match += 1
        bool = True
        A[i].popleft()
        A[op].popleft()
answer = 1

while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if o == -1:
                continue
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
                w[i] = -1
                w[o] = -1
        if not nxt:
            return -1
        cur = []
        for i in nxt:
            if A[i]:
                w[i] = A[i].pop()
                cur.append(i)
            else:
                r -= 1
    return d


print(main())

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = []
    for _ in range(N):
        a = list(map(int, input().split()))
        a = [i-1 for i in a]
        a.reverse()
        A.append(a)
    t = N * (N - 1) / 2
    d = 0
    n = set(range(N))
    while True:
        p = 0
        l = set()
        d += 1
        for i in n:
            if A[i] == [] or i in l:
                continue
            j = A[i][-1]
            if A[i][-1] not in l and A[j][-1] == i:
                l.add(i)
                l.add(A[i][-1])
                A[j].pop() 
                A[i].pop()
                t -= 1
                p += 1
        n = l
        if t == 0:
            print(d)
            break
        if p == 0:
            print(-1)
            break
main()

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)]

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

stack = []
for i in range(1, N + 1):
  a = A[i].pop()
  pair[i][a] += 1
  if pair[i][a] == pair[a][i] == 1:
    stack.append(i)
    stack.append(a)

r = []
answer = 1
while stack:
  while stack:
    i = stack.pop()
    if A[i]:
      a = A[i].pop()
      pair[i][a] += 1
      if pair[i][a] == pair[a][i] == 1:
        r.append(i)
        r.append(a)
  stack = r
  if r:
    answer += 1
  r = []
  
flag = 1
for i in range(1, N + 1):
  if A[i]:
    flag = 0
    break
if flag:
  print(answer)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque(range(n))

days = [0]*n  # 各選手の現在の日付

while q:
    x = q.popleft()  # 試合する人
    if len(matches[x]) == 0:  # 試合が全て終わってる?
        continue
    y = matches[x][0]  # xの次の対戦相手
    if matches[y][0] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        q.append(x)
        q.append(y)
        _ = matches[x].pop(0)
        _ = matches[y].pop(0)

if not any(matches):  # 全ての試合をしょうか
    print(max(days))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque(range(n))

days = [0]*n  # 各選手の現在の日付
pairs = [-1]*n  # 次の対戦相手を管理(wait的な)

while q:
    x = q.popleft()  # 試合する人
    if len(matches[x]) == 0:  # 試合が全て終わってる?
        continue
    y = matches[x].pop(0)  # xの次の対戦相手
    if pairs[y] == x:
        day = max(days[x], days[y])+1
        days[x] = day
        days[y] = day
        q.append(x)
        q.append(y)
    else:
        pairs[x] = y

if not any(matches):  # 全ての試合をしょうか
    print(max(days))
else:
    print(-1)

Submission status: Accepted

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

q = deque((range(a)))
days=[0]*a
pairs=[-1]*a
while q:
    x = q.popleft()
    if len(l[x]) == 0:continue
    y = l[x].pop(0)
    if pairs[y] == x:
        days[x]=days[y]=max(days[x],days[y])+1
        q.append(x)
        q.append(y)
    else:
        pairs[x]=y
if not any(l):
    print(max(days))
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
A = [deque(map(lambda x: int(x)-1,input().split(" "))) for _ in range(N)]
ans = 0
used_prev = set(range(N))

while any(A):
    used = set()
    for i in used_prev:
        a = A[i]
        if not a or i in used:
            continue
        j = a[0]
        b = A[j]
        if not b or j in used:
            continue
        if i == b[0]:
            A[i].popleft()
            A[j].popleft()
            used.add(i)
            used.add(j)
    if not used:
        ans = -1
        break
    used_prev = used
    ans += 1
print(ans)

Submission status: Accepted

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


def main():
    N = int(input())
    A = [deque(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
    ans = 0
    used_prev = set(range(N))
    while any(A):
        used = set()
        for i in used_prev:
            a = A[i]
            if not a or i in used:
                continue
            j = a[0]
            b = A[j]
            if not b or j in used:
                continue
            if i == b[0]:
                A[i].popleft()
                A[j].popleft()
                used.add(i)
                used.add(j)
        if not used:
            ans = -1
            break
        used_prev = used
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def solve(N: int, A: "List[List[int]]"):
    for i in range(N):
        A[i] = A[i][::-1]
    
    answer = 0
    totalGame = 0
    MAXGAME = (N*(N-1))//2
    match = set()

    while True:
        if totalGame == 0:
            for i in range(N):
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1
        else:
            if totalGame == MAXGAME:
                break

            check_needed = list(match)
            # 既にこのターンでマッチしたインデックスを保持
            match = set()

            for i in check_needed:
                if not A[i]:
                    continue
                match_index = A[i][-1]-1

                if not A[match_index]:
                    continue

                if match_index in match or i in match:
                    continue

                if A[match_index][-1]-1 == i:
                    A[i].pop()
                    A[match_index].pop()
                    match.add(i)
                    match.add(match_index)
                    totalGame += 1

        if len(match) == 0:
            print(-1)
            return

        answer += 1

    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N - 1)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

A = [None] * N
# インデックス：-1で先頭にアクセスするため前後反転
# 最初の選手を指す場合０になるように-1した値を保持
# 全組み合わせを試合し終わった時は−１になるようにする
for i in range(N):
    A[i] = [-1] + [int(x) - 1 for x in input().split()[::-1]]


def f(candi):
    
    played = []
    
    # 次に試合する可能性のある選手を順次チェック
    for n in candi:
        target = A[n][-1]
        if A[target][-1] == n:
            played.append(n)
        
    new_candi = set()    
    for n in played:
        # 試合ずみの組み合わせを削除
        A[n].pop()
        # 試合する人の候補に追加
        new_candi.add(n)
        # 次の対戦相手を試合の候補に追加
        if A[n][-1] != -1:
            new_candi.add(A[n][-1])
            
    return len(played), new_candi


answer = 0
# 最悪の試合数（二倍された値）
rest = N*(N-1)
# 試合する人の候補
play_candi = set(range(N))

while True:
    answer += 1
    x, play_candi = f(play_candi)
    # 行われた試合数を確認
    if x == 0:
        answer = -1
        break
        
    rest -= x
    if rest ==0:
        break
        
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
league = [0]*(n+1)
cnt = 0

while True:
  topop = []
  if cnt == 0:
    for i,player in enumerate(a):
      x = player[-1]
      if league[x] == i+1:
        topop.append(x)
        topop.append(i+1)
      else:
        league[i+1] = x
  else:
    for player in popped:
      if a[player-1] == []:
        continue
      x = a[player-1][-1]
      if league[x] == player:
        topop.append(x)
        topop.append(player)
      else:
        league[player] = x
  popped = []
  if topop == []:
    print(-1)
    exit()
  for t in topop:
    if a[t-1] == []:
      print(-1)
      exit()
    a[t-1].pop()
    popped.append(t)
  cnt += 1
  if not any(a[i] for i in range(n)):
    break
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = []
for _ in range(N):
    A.append([x - 1 for x in map(int, input().split())])

game = []
for p1 in range(N):
    p2 = A[p1][0]
    if A[p2][0] == p1 and p1 < p2:
        game.append((p1, p2))

cursors = [0] * N
days = 0
while game:
    days += 1
    new_game = []
    for p1, p2 in game:
        cursors[p1] += 1
        if cursors[p1] < N - 1:
            p3 = A[p1][cursors[p1]]
            if cursors[p3] < N - 1 and A[p3][cursors[p3]] == p1:
                new_game.append((p1, p3))
        cursors[p2] += 1
        if cursors[p2] < N - 1:
            p3 = A[p2][cursors[p2]]
            if cursors[p3] < N - 1 and A[p3][cursors[p3]] == p2:
                new_game.append((p2, p3))
    game = new_game

if all(c == N - 1 for c in cursors):
    print(days)
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
    id = [[0]*n for _ in range(n)]
    V = 0
    for i in range(n):
        for j in range(n):
            if i<j:
                id[i][j] = V
                V += 1
    def toID(i, j):
        if i<j:
            return id[i][j]
        else:
            return id[j][i]
    
    to = [[] for _ in range(V)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toID(i, a[i][j])
        for j in range(n-2):
            to[a[i][j+1]].append(a[i][j])

    dp, visited, calculated = [1] * V, [0] * V, [0] * V

    def dfs(v, dp, visited, calculated):
        if visited[v]:
            if not calculated[v]:
                return -1
            return dp[v]
        visited[v] = 1
        for u in to[v]:
            res = dfs(u, dp, visited, calculated)
            if res == -1:
                return -1
            dp[v] = max(dp[v], res+1)
        calculated[v] = 1
        return dp[v]

    ans = 0
    for v in range(V):
        res = dfs(v, dp, visited, calculated)
        if res == -1:
            print(-1)
            return
        ans = max(ans, res)
    print(ans)
    return

main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [list(map(lambda x : int(x)-1, input().split())) for _ in range(n)]
    for i in range(n):
        a[i].reverse()
    # print(a)
    s = set()

    def check(i, s):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if len(a[j]) == 0:
            return
        if a[j][-1] == i:
            if i < j:
                s.add((i, j))
            else:
                s.add((j, i))
    
    for i in range(n):
        check(i, s)
    day = 0
    while s:
        day += 1
        prevS = set()
        s, prevS = prevS, s
        for p in prevS:
            i = p[0]
            j = p[1]
            a[i].pop()
            a[j].pop()
        for p in prevS:
            i = p[0]
            j = p[1]
            check(i, s)
            check(j, s)
    
    for i in range(n):
        if len(a[i]):
            print(-1)
            return
    print(day)
    return

main()

Submission status: Accepted

Solution code:
#%%
n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]
count = [0] * n
tmp = [_ for _ in range(n)]
ans = 0

while len(tmp) >= 1:
    check = [0] * n
    t = []
    for i in tmp:
        if check[i] == 0 :
            j = a[i][count[i]]
            if i == a[j][count[j]] and check[j] == 0:
                count[i] += 1
                count[j] += 1
                check[i], check[j] = 1, 1
                if count[i] < n-1:
                    t.append(i)
                if count[j] < n-1:
                    t.append(j)
    tmp = t
    ans += 1

if count.count(n-1) == n:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N=int(input())
A=[[] for _ in range(N)]

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

NE=[0]*N#i番目の人が，次何番目の試合をするかのリスト
F=[0]*N#i番目の人が，該当する日に試合をしたか記憶しておく

#i+1日目の試合をする人はi日目に試合をした人なので，それを2つのqueueに記憶．
Q=[[],[]]

#初日
for i in range(N):
    opp=A[i][0]-1
    if A[opp][0]-1==i:
        NE[i]+=1
        Q[0].append(i)

ans=1
#d日目
for d in range(N*(N-1)//2):
    F=[0]*N
    a=d%2
    b=(d+1)%2
    while len(Q[a])!=0:
        i=Q[a].pop()
        if NE[i]==N-1:
            continue
        opp=A[i][NE[i]]-1
        if F[i]==1 or F[opp]==1:#その日に試合したことがある人はスルー,oppの重複防止
            continue
        if A[opp][NE[opp]]-1==i:
            NE[i]+=1
            NE[opp]+=1
            F[i]=1
            F[opp]=1
            if NE[i]!=N-1:
                Q[b].append(i)
            if NE[opp]!=N-1:
                Q[b].append(opp)
    ans+=1
    if len(Q[a])==0 and len(Q[b])==0:
        break

for i in range(N):
    if NE[i]!=N-1:
        ans=-1
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.buffer.readline

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

    adj = defaultdict(list)
    in_num = defaultdict(int)
    for i in range(N):
        for j in range(N-2):
            x1 = x2 = i+1
            y1 = A[i][j]
            y2 = A[i][j+1]
            if x1 > y1:
                x1, y1 = y1, x1
            if x2 > y2:
                x2, y2 = y2, x2
            adj[x1*(N+1)+y1].append(x2*(N+1)+y2)
            in_num[x2*(N+1)+y2] += 1
    st = []
    ng = (N * (N - 1)) // 2
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if in_num[i*(N+1)+j] == 0:
                st.append(i*(N+1)+j)
                ng -= 1
    ans = 0
    while st:
        ans += 1
        st_new = []
        for par in st:
            for child in adj[par]:
                if in_num[child] == 1:
                    st_new.append(child)
                    ng -= 1
                in_num[child] -= 1
        if st_new:
            st = st_new
        else:
            break

    if ng:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=[list(map(int,input().split())) for i in range(n)]
now=[0]*n
rest=n*(n-1)//2
for i in range(n):
    for j in range(n-1):
        A[i][j]=A[i][j]-1

S={i for i in range(n)}
tmp=set()
while rest and S:
    used=[0]*n  
    # print(now)
    count+=1
    for si in S:
        if n-1<=now[si]:
            continue
        ene=A[si][now[si]]
        if n-1<=now[ene]:
            continue
        if A[ene][now[ene]] == si and not(used[si] or used[ene]):
            rest-=1
            now[si]+=1; now[ene]+=1
            used[si]=used[ene]=1
            tmp.add(si); tmp.add(ene)
    S=tmp.copy(); tmp=set()
for ni in now:
    if ni != n-1:
        print(-1)
        break
else:
    print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    M=[None]*n
    for i in range(n):
        M[i]=list(map(lambda x:int(x)-1,input().split()))[::-1]

    # i が誰かしらと対戦できるか
    def check(i):
        if(not M[i]): # 既に試合を終えている
            return False
        j=M[i][-1]
        if(not M[j]): # これは起こり得ない
            return False
        return i==M[j][-1]

    # 初日に対戦できる人をピックアップ
    # 重複が起こるが、後で unique を取る
    Q=[]
    for i in range(n):
        if(check(i)):
            j=M[i][-1]
            if(i>j): i,j=j,i # i<j
            Q.append((i,j))

    # 処理を行なっていく
    day=0
    nQ=[] # 次の試合相手
    while(Q):
        # Q には重複があるので unique
        Q=list(set(Q))
        # 先に全ての試合を終わらせる必要がある
        for i,j in Q:
            M[i].pop(); M[j].pop()
        # 試合を終えた人は次の試合を行える可能性がある
        for i,j in Q:
            if(check(i)):
                k=M[i][-1]
                nQ.append((min(i,k),max(i,k)))
            if(check(j)):
                k=M[j][-1]
                nQ.append((min(j,k),max(j,k)))
        Q,nQ=nQ,[]
        day+=1

    print(day if(all(M[i]==[] for i in range(n))) else "-1")
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
  N=int(input())
  A=[deque()]+[deque(map(int,input().split())) for _ in range(N)]
  Days=[0]*(N+1)
  NOW=[0]*(N+1)
  
  q=deque([i+1 for i in range(N)])
  
  while q:
    i=q.popleft()

    if not A[i]:
      continue
    a=A[i].popleft()
    
    if NOW[a]==i:
      Days[a]=Days[i]=max(Days[a],Days[i])+1
      q.append(i)
      q.append(a)
      NOW[a]=NOW[i]=0
    else:
      NOW[i]=a
    
  for i in range(1,N+1):
    if A[i]:
      print(-1)
      return
  print(max(Days))
      

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

def main():

  n=int(input())

  A=[list(map(int,input().split()))[::-1] for i in range(n)]

  day=0
  zan=[n-1]*n
  zann=sum(zan)
  sumi=set(range(n))

  while True:
    day+=1

    kouho=list(sumi)
    sumi=set()
  
    for i in kouho:
      try:
        if A[A[i][-1]-1][-1]-1==i:
          sumi.add(i)
          sumi.add(A[i][-1]-1)
      except:
        pass

    for k in sumi:
      A[k].pop()
      zan[k]-=1

    if zann==sum(zan):
      print(-1)
      exit(0)
  
    zann=sum(zan)
  
    if zann==0:
      print(day)
      exit(0)
    
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n=int(input())

A=[list(map(int,input().split()))[::-1] for i in range(n)]

day=0
zan=[n-1]*n
zann=sum(zan)
sumi=set(range(n))

while True:
  day+=1

  kouho=list(sumi)
  sumi=set()
  
  for i in kouho:
    try:
      if A[A[i][-1]-1][-1]-1==i:
        sumi.add(i)
        sumi.add(A[i][-1]-1)
    except:
      pass

  for k in sumi:
    A[k].pop()
    zan[k]-=1

  if zann==sum(zan):
    print(-1)
    exit(0)
  
  zann=sum(zan)
  
  if zann==0:
    print(day)
    exit(0)

Submission status: Accepted

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


def main():
	n = int(input())

	def label(a, b):
		if a > b:
			a, b = b, a
		return (a - 1) * (2 * n - a) // 2 + b - a - 1

	m = n * (n - 1) // 2
	g = [[] for _ in range(m)]
	deg = [0] * m
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for x, y in zip(l, l[1:]):
			t = label(i, y)
			g[label(i, x)].append(t)
			deg[t] += 1

	depth = [None] * m
	q = deque()
	ans = 1
	for i, d in enumerate(deg):
		if not d:
			depth[i] = 1
			q.append(i)
	while q:
		cur = q.popleft()
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				depth[nxt] = depth[cur] + 1
				if ans < depth[nxt]:
					ans = depth[nxt]
				q.append(nxt)
	print(ans if all(depth) else -1)

if __name__ == "__main__":
	main()

Submission status: Accepted

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

def f(g: list, deg: list):
	l = len(g)
	depth = [0] * l
	ret = []
	q = []
	for i, d in enumerate(deg):
		if not d:
			ret.append(i)
			q.append(i)
	while q:
		cur = q.pop(0)
		for nxt in g[cur]:
			deg[nxt] -= 1
			if not deg[nxt]:
				depth[nxt] = depth[cur] + 1
				ret.append(nxt)
				q.append(nxt)
	if l > len(ret):
		return False
	return max(depth)

def label(a, b, n):
	if a > b:
		a, b = b, a
	return (a - 1) * (2 * n - a) // 2 + b - a - 1


def main():
	n = int(input())
	g = [[] for _ in range(n * (n - 1) // 2)]
	deg = [0] * (n * (n - 1) // 2)
	for i in range(1, n + 1):
		l = list(map(int, input().split()))
		for x, y in zip(l, l[1:]):
			t = label(i, y, n)
			g[label(i, x, n)].append(t)
			deg[t] += 1
	depth = f(g, deg)
	if not depth:
		print(-1)
		exit()
	print(depth + 1)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N=int(input())
MAXN=1005
MAXV=N*(N-1)//2

a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1

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

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

to=[[] for i in range(MAXV)]
for i in range(N):
  for j in range(N-1):
    a[i][j]=toId(i,a[i][j])
  for j in range(N-2):
    to[a[i][j+1]].append(a[i][j])
    
visited=[False for i in range(MAXV)]
calculated=[False for i in range(MAXV)]
dp=[0 for i in range(MAXV)]

def dfs(v):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v]=True
  for u in to[v]:
    val=dfs(u)
    if val==-1:
      return -1
    if val+1>dp[v]:
      dp[v]=val+1
  calculated[v]=True
  return dp[v]
    
ans=0
for i in range(v):
  res=dfs(i)
  if res==-1:
    print(-1)
    break
  if ans<res:
    ans=res
else:
  print(ans+1)

Submission status: Accepted

Solution code:
N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
stack=[]

def addmatch(i):
  if len(a[i])==0:
    return
  j=a[i][-1]
  if a[j][-1]==i:
    stack.append([i,j])

for i in range(N):
  addmatch(i)

day=0
while stack:
  day+=1
  member=set()
  for i in range(len(stack)):
    g=stack.pop()
    y=g[0]
    x=g[1]
    if len(a[y])>0 and a[y][-1]==x:
      a[y].pop()
      a[x].pop()
      member.add(y)
      member.add(x)
  for m in member:
    addmatch(m)

for i in range(len(a)):
  if len(a[i])>0:
    print(-1)
    break
else:
  print(day)

Submission status: Accepted

Solution code:
N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)

Submission status: Accepted

Solution code:
from collections import deque

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

M = N*(N-1)//2

for i in range(N):
    for j in range(N-1):
        p = min(i+1,A[i][j])
        q = max(i+1,A[i][j])
        match = M-(N-p+1)*(N-p)//2+q-p-1
        A[i][j] = match
        
graph = [[] for _ in range(M)]
indegree = [0 for _ in range(M)]

for i in range(N):
    for j in range(1,N-1):
        graph[A[i][j-1]].append(A[i][j])
        indegree[A[i][j]] += 1
        
dist = [None for _ in range(M)]
queue = deque([])

for k in range(M):
    if indegree[k]==0:
        dist[k] = 0
        queue.append(k)

cycle = False

while queue:
    node = queue.popleft()
    for adj in graph[node]:
        indegree[adj] -= 1
        dist[adj] = dist[node] + 1
        if indegree[adj]==0:
            queue.append(adj)
            
if any(indegree):
    cycle = True

print(-1 if cycle else max(dist)+1)

Submission status: Accepted

Solution code:
n=int(input())
match=[]
for i in range(n):
    a=list(map(int, input().split()))
    match.append(a)

select=[list(range(n))]

day=0
mat=0
for _ in range(int(n*(n-1)/2)):
    nex=[]
    for x in select[day]:
        if len(match[x]) != 0 and not x in nex and not match[x][0]-1 in nex and match[match[x][0]-1][0] == (x+1):
            nex.append(x)
            nex.append(match[x][0]-1)
            match[match[x][0]-1].pop(0)
            match[x].pop(0)
            mat+=1

    if len(nex) == 0 and mat==int(n*(n-1)/2):
        break
    
    if len(nex) == 0:
        print(-1)
        exit()

    select.append(nex)
    day+=1

print(day)