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 math
import collections
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


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

    v = 0  # 頂点数
    # 頂点にIDをふる
    Id = [[-1 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:  # 1-3 ,2-4など　3-1はダメ
                Id[i][j] = v
                v += 1

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

    # 頂点間の辺を貼る
    e = [[] 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):
            e[a[i][j + 1]].append(a[i][j])

    # トポロジカルソート
    calculated = [False for i in range(maxv)]
    dp = [-1 for i in range(maxv)]

    def dfs(v):
        if dp[v] != -1:  # サイクル検知
            if not calculated[v]:
                return -1
            return dp[v]
        dp[v] = 1
        for u in e[v]:
            ret = dfs(u)
            if ret == -1:
                return -1
            dp[v] = max(dp[v], ret + 1)
        calculated[v] = True
        return dp[v]

    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  # detected cycle
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

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

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

print(max(day))

Submission status: Accepted

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


def main():
    n = int(input())
    maxv = n*(n-1)//2
    a = [list(map(int, input().split())) for i in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    v = 0
    Id = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if i < j:
                Id[i][j] = v
                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 = [-1 for i in range(maxv)]

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

    ans = 0
    for i in range(v):
        ret = dfs(i)
        if ret == -1:  # detected cycle
            print(-1)
            exit()
        ans = max(ans, ret)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import time
start = time.time()
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] #それぞれ何試合目か
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] #今日試合をするかどうか
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 # firstが対戦したい相手
            second_num = s[second] # #secondの対戦番号
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
    now = time.time()-start
    if now > 1.835:
        print(n*(n-1)//2)
        exit()
print(ans)

Submission status: Accepted

Solution code:
import time
start = time.time()
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] #それぞれ何試合目か
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] #今日試合をするかどうか
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 # firstが対戦したい相手
            second_num = s[second] # #secondの対戦番号
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
    now = time.time()-start
    if now > 1.83:
        print(n*(n-1)//2)
        exit()
print(ans)

Submission status: Accepted

Solution code:
import time
start = time.time()
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] #それぞれ何試合目か
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] #今日試合をするかどうか
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 # firstが対戦したい相手
            second_num = s[second] # #secondの対戦番号
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print(-1)
        exit()
    now = time.time()-start
    if now > 1.81:
        print(n*(n-1)//2)
        exit()
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    A = [[0 for _ in range(N - 1)] for _ in range(N)]

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

    day = 0
    # 選手毎に明日の試合の有る/無しを1,0で管理
    M = defaultdict(int)
    # 全選手を試合有り(1)で初期化
    for i in range(N):
        M[i] += 1

    # 選手毎の次の対戦相手リスト
    W = [0] * N

    while M:
        day += 1
        # 選手毎に次の対戦相手のリストを作成
        for m in M:
            # 全試合が終った選手は-1にする
            W[m] = A[m].pop(0) if A[m] else -1

        # 明日の試合一覧を初期化
        _M = defaultdict(int)
        for m in M:
            # 選手が次の対戦相手と相思相愛なら
            if W[m] >= 0 and W[W[m]] == m:
                # 両方を明日は試合有りにする
                _M[m] += 1
                _M[W[m]] += 1

        M = _M

    if sum(W) != -N:
        print(-1)
    else:
        print(day - 1)
            

main()

Submission status: Accepted

Solution code:
# ABC139E - League
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(x: int, y: int) -> None:
    scheduled[x] = 1
    for i in range(cur[x], N - 1):
        z = A[x][i]  # scheduled i-th opponent of player x
        if z == y:
            cur[x] = i + 1
            scheduled[x] = 0
            days[x] += 1
            days[z] += 1
            days[x] = days[z] = max(days[x], days[z])
            return
        if scheduled[z]:  # the schedule contradicts
            print(-1)
            exit()
        dfs(z, x)


def main():
    global N, A, cur, days, scheduled
    N = int(input())
    A = [0] + list(list(map(int, input().split())) for _ in range(N))
    cur, days, scheduled = [0] * (N + 1), [0] * (N + 1), [0] * (N + 1)
    for i in range(1, N + 1):
        dfs(i, 0)
    ans = max(days)  # the last day of games
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import time
from collections import deque

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
A = [0] * N
l = [[int(x) for x in stdin.readline().rstrip().split()] for _ in A]
d = 1
k = N * (N - 1)

while sum(A) < k and d < 10 ** 4:
    L = [1] * N
    y = 0
    d += 1
    for i in range(N):
        if A[i] < N - 1:
            x = l[i][A[i]] - 1
            if l[x][A[x]] * L[x] * L[i] == i + 1:
                A[i] += 1
                A[x] += 1
                L[i] = L[x] = 0
                y = 1

print([k // 2, d * y - 1][d * y < 9999])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
n=int(input())
A=["dammy"]+[deque(list(map(int,input().split()))) for _ in range(n)]
Q,planned,day=deque([_ for _ in range(1,n+1)]),[0]*(n+1),[0]*(n+1)
cnt=0

while Q:
    x=Q.popleft()
    if not A[x]:
        pass
    else:
        y=A[x].popleft()
        if planned[y]==x:
            day[x],day[y]=max(day[x],day[y])+1,max(day[x],day[y])+1
            cnt+=1
            planned[x],planned[y]=0,0
            Q.append(x)
            Q.append(y)
        else:
            planned[x]=y

if cnt!=(n*(n-1))//2:
    print(-1)
else:
    print(max(day))

Submission status: Accepted

Solution code:
from collections import deque

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

# how many times each player matched
c = [0 for _ in range(N + 1)]
predeq = deque([])

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

ans = 0
while predeq:
    # print(predeq)
    postdeq = deque([])
    for i, j in predeq:
        c[i] += 1
        c[j] += 1
        if c[i] < N - 1:
            k = A[i][c[i]] # next player
            if A[k][c[k]] == i:
                postdeq.append((i, k))
        if c[j] < N - 1:
            k = A[j][c[j]]
            if A[k][c[k]] == j:
                postdeq.append((j, k))
    ans += 1
    predeq = postdeq

if c == [0] + [N - 1] * N:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
from pprint import pprint
N = int(input())
nextGame = [deque()] + [deque(map(int , input().split())) for _ in range(N)]
#print(nextGame)

canPlay = [[False] * (N + 1) for _ in range(N + 1)]
#pprint(canPlay)
days = [0] * (N + 1)
que = ([i for i in range(N + 1)])

while que:
    now = que.pop()
    #print("------------------------")
    if not nextGame[now]:
        continue
    enemy = nextGame[now].popleft()
    canPlay[now][enemy] = True
    #print("now : ",now)
    #print("enemy : ",enemy)
    #pprint(canPlay)

    if canPlay[now][enemy] and canPlay[enemy][now]:
        days[now] = days[enemy] = max(days[now], days[enemy]) + 1
        que.append(now)
        que.append(enemy)
    #print("days : ",days)

for test in nextGame:
    if test:
        print("-1")
        exit(0)
print(max(days))

Submission status: Accepted

Solution code:
#
import sys
from collections import deque

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

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(al)

    ans = 0

    def find_next(idx, q, m):
        if agrid_pointer[idx] == n - 1 or i in m:  # もう全部対戦済み or この日対戦済み
            return

        target = agrid[idx][agrid_pointer[idx]]
        if agrid_pointer[target] == n - 1 or target in m:  # もう全部対戦済み or この日対戦済み
            return

        if agrid[target][agrid_pointer[target]] != idx:
            return

        q.append((idx, target))
        m.add(idx)
        m.add(target)

    que = deque()
    first_matching = set()
    for i in range(n):
        find_next(i, que, first_matching)

    while que:
        ans += 1

        changed = []
        while que:
            i, j = que.popleft()
            agrid_pointer[i] += 1
            agrid_pointer[j] += 1
            changed.append(i)
            changed.append(j)

        next_que = deque()
        match = set()
        for i in changed:
            find_next(i, next_que, match)

        # print(match)
        que = next_que

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())

    nextGame = [deque()] + [deque(map(int, input().split())) for _ in range(N)]

    canPlay = [[False] * (N + 1) for _ in range(N + 1)]
    days = [0] * (N + 1)

    que = deque([i for i in range(1, N + 1)])

    while que:
        now = que.pop()
        if not nextGame[now]:
            continue
        enemy = nextGame[now].popleft()
        canPlay[now][enemy] = True

        if canPlay[now][enemy] and canPlay[enemy][now]:
            days[now] = days[enemy] = max(days[now], days[enemy]) + 1
            que.append(now)
            que.append(enemy)

    for a in nextGame:
        if a:
            print('-1')
            return

    ans = max(days)
    print(ans)


sol()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = [[0 for _ in range(N - 1)] for _ in range(N)]
for i in range(N):
  A[i] = [int(x) - 1 for x in input().split()]
day = 0
M = defaultdict(int)
for i in range(N):
  M[i] += 1
W = [0] * N
while M:
  day += 1
  for m in M:
    W[m] = A[m].pop(0) if A[m] else -1
  _M = defaultdict(int)
  for m in M:
    if W[m] >= 0 and W[W[m]] == m:
      _M[m] += 1
      _M[W[m]] += 1
  M = _M
for w in W:
  if w > 0:
    print(-1)
    break
else:
  print(day - 1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque

def main():
    N = int(input())
    M = [[]]
    for cm in range(N):
        A = list(map(int,input().split()))
        M.append(A)

    q = deque(range(1, N+1))
    day = [0] * (N+1)
    opponent = [-1] * (N+1)

    while q:
        a = q.popleft()
        if len(M[a]) > 0:
            b = M[a][0]
            if opponent[b] == a:
                day[a] = day[b] = max(day[a],day[b]) + 1
                opponent[a] = opponent[b] = -1
                M[a].pop(0)
                M[b].pop(0)
                q.append(a)
                q.append(b)
            else:
                opponent[a] = b

    remain = max([len(Mx) for Mx in M])
    if remain > 0:
        print(-1)
    else:
        answer = max(day)
        answer = answer if answer > 0 else -1
        print(answer)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input());a=[0]*n;l=[list(map(int,input().split()))for i in a];d=1;k=n*~-n
while sum(a)<k and d<1e4:
 L=[1]*n;y=0;d+=1
 for i in range(n):
  if-~a[i]-n:
   x=l[i][a[i]]-1
   if l[x][a[x]]*L[x]*L[i]==i+1:a[i]+=1;a[x]+=1;L[i]=L[x]=0;y=1
print([k//2,d*y-1][d*y<1e4])

Submission status: Accepted

Solution code:
n=int(input());a=[0]*n;l=[list(map(int,input().split()))for i in a];d=1;k=n*~-n
while sum(a)<k and d<1e4:
 L=[1]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]*L[x]*L[i]==i+1:a[i]+=1;a[x]+=1;L[i]=L[x]=0;y=1
print([k//2,d*y-1][d*y<1e4])

Submission status: Accepted

Solution code:
def e_league():
    import sys
    sys.setrecursionlimit(10**6)
    N = int(input())
    A = [[int(i) - 1 for i in input().split()] for j in range(N)]

    # 各試合に識別番号をつける
    match_num = 0
    identification = [[None] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i < j:
                identification[i][j] = match_num
                match_num += 1

    vertex_max = N * (N - 1) // 2  # 試合数だけ頂点を作る
    # match_allocation[n]: n番の選手はこの要素で指定された試合をする必要がある
    match_allocation = [row for row in A]
    # next_match[n]: n番の試合の後に行わなければならない試合の番号
    next_match = [[] for _ in range(vertex_max)]

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

    # 上で定義したリストの要件を満たすように値を入れていく
    for i in range(N):
        for j in range(N - 1):
            match_allocation[i][j] = to_id(i, match_allocation[i][j])
        for j in range(N - 2):
            next_match[match_allocation[i][j]].append(match_allocation[i][j + 1])

    # ここから、グラフはDAGか？　DAGなら最長パスはいくらか？
    # 最長パスの長さが解になるようにグラフを作っている
    is_visited = [False] * vertex_max
    is_calculated = [False] * vertex_max
    dp = [0] * vertex_max  # dp[v]: 頂点vからの最大パス長

    def dfs(v):
        if is_visited[v]:
            # 計算結果が確定していない頂点に再度訪れた→DAGじゃない
            if not is_calculated[v]:
                return -1
            return dp[v]

        is_visited[v] = True
        dp[v] = 1
        for u in next_match[v]:
            ret = dfs(u)
            if ret == -1:
                return -1  # vから先でDAGじゃないところがあった
            dp[v] = max(dp[v], ret + 1)  # v-u間の分、+1
        is_calculated[v] = True  # ここでようやく結果が確定
        return dp[v]

    ans = 0
    for v in range(match_num):
        res = dfs(v)
        if res == -1:
            return -1
        ans = max(ans, res)
    return ans

print(e_league())

Submission status: Accepted

Solution code:
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*~-n
while sum(a)<k and d<9999:
 L=[1]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]*L[x]*L[i]==i+1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=0;y=1
print([k//2,d*y-1][d*y<9999])

Submission status: Accepted

Solution code:
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*~-n
while sum(a)<k and d<9999:
 L=[0]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
print([k//2,d*y-1][d*y<9999])

Submission status: Accepted

Solution code:
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*(n-1)
while sum(a)<k and d<9999:
 L=[0]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
print([k//2,d*y-1][d*y<9999])

Submission status: Accepted

Solution code:
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*(n-1)
while sum(a)<k and d<9999:
 L=[0]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
d*=y;print([k//2,d-1][d<9999])

Submission status: Accepted

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


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    N = int(input())
    X = [[] for i in range(N)]
    for i in range(N):
        for j in LI():
            X[i].append(j-1)
        X[i].reverse()

    Q = []
    def check(i):
        if len(X[i])==0:
            return
        j = X[i][-1]
        if len(X[j])==0:
            return
        if i==X[j][-1]:
            if i<j:
                Q.append((i,j))
            else:
                Q.append((j,i))

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

    day = 0
    while len(Q)>0:
        day += 1
        Q.sort()
        Q = list(set(Q))
        prevQ = Q.copy()
        Q = []
        for i,j in prevQ:
            X[i].pop()
            X[j].pop()
        for i,j in prevQ:
            check(i)
            check(j)

    for i in range(N):
        if len(X[i])>0:
            print("-1")
            return

    print(day)
    return

main()

Submission status: Accepted

Solution code:
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0]*n;d=1;k=n*(n-1)
while sum(a)<k and 0<d<9999:
 L=[0]*n;y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
 d*=y
print([k//2,d-1][d<9999])

Submission status: Accepted

Solution code:
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0 for i in[0]*n];d=1;k=n*(n-1)
while sum(a)<k and 0<d<9999:
 L=[];y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if not(l[x][a[x]]-1!=i or x in L or i in L):
    a[i]+=1;a[x]+=1;L+=[i,x];y=1
 d*=y
print([k//2,d-1][d<9999])

Submission status: Accepted

Solution code:
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0 for i in[0]*n];d=1;k=n*(n-1)
while sum(a)<k and 0<d<9999:
 L=[];y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and not(x in L or i in L):
    a[i]+=1;a[x]+=1;L+=[i,x];y=1
 d*=y
print([k//2,d-1][d<9999])

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(input())
matches = [None] + [list(map(int, line.split())) for line in sys.stdin]
q = deque(range(1, n + 1))
depth = [0] * (n + 1)
waiting = [-1] * (n + 1)

while q:
    a = q.popleft()
    b = matches[a].pop()
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        if matches[a]:
            q.append(a)
        if matches[b]:
            q.append(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
q = deque(range(n))
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    b = matches[a].pop()
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        if matches[a]:
            q.append(a)
        if matches[b]:
            q.append(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
q = deque(range(n))
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    ma = matches[a]
    if not ma:
        continue
    b = ma.pop()
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        q.append(a)
        q.append(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))

Submission status: Accepted

Solution code:
n=int(input());l=[list(map(int,input().split()))for i in[0]*n];a=[0 for i in[0]*n];d=1;k=n*(n-1)
while sum(a)<k and 0<d<9999:
 L=[0 for i in[0]*n];y=0;d+=1
 for i in range(n):
  if a[i]<n-1:
   x=l[i][a[i]]-1
   if l[x][a[x]]-1==i and L[x]+L[i]<1:
    a[i]+=1;a[x]+=1;L[i]=L[x]=y=1
 d*=y
print([k//2,d-1][d<9999])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, A):
    ans = 0
    A = [list(reversed(a)) for a in A]

    s1 = set()
    s2 = set()

    def update(i):
        if not A[i-1]:
            return

        d = A[i-1][-1]
        n = (min(i, d), max(i, d))
        if n not in s1:
            s1.add(n)
        else:
            s2.add(n)
            s1.remove(n)

    for i in range(1, N+1):
        update(i)

    while s2:
        ans += 1
        s2_, s2 = s2, set()
        for k in s2_:
            a, b = k
            A[a-1].pop()
            A[b-1].pop()
            update(a)
            update(b)


    for a in A:
        if a:
            return -1
    return ans


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, A):
    ans = 0
    A = [list(reversed(a)) for a in A]

    s1 = set()
    s2 = set()

    def update(i):
        if not A[i-1]:
            return

        d = A[i-1][-1]
        n = (min(i, d), max(i, d))
        if n not in s1:
            s1.add(n)
        else:
            s2.add(n)
            s1.remove(n)

    for i in range(1, N+1):
        update(i)

    while s2:
        ans += 1
        for k in tuple(s2):
            a, b = k
            A[a-1].pop()
            A[b-1].pop()
            update(a)
            update(b)
            s2.remove(k)


    for a in A:
        if a:
            return -1
    return ans


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().split()))


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, A):
    ans = 0
    A = [list(reversed(a)) for a in A]

    s1 = set()
    s2 = set()

    def update(i):
        if not A[i-1]:
            return

        d = A[i-1][-1]
        n = (min(i, d), max(i, d))
        if n not in s1:
            s1.add(n)
        else:
            s2.add(n)
            s1.remove(n)

    for i in range(1, N+1):
        update(i)

    while s2:
        ans += 1
        for k in list(s2):
            a, b = k
            A[a-1].pop()
            A[b-1].pop()
            update(a)
            update(b)
            s2.remove(k)


    for a in A:
        if a:
            return -1
    return ans


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

    # N = 1000
    # A = []

    # while True:
    #     for i in range(1, N+1):
    #         t = list(range(1, N+1))
    #         t.remove(i)
    #         random.shuffle(t)
    #         A.append(t)
    #     print(slv(N, A))


if __name__ == '__main__':
    main()