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:
N = int(input())
A = [[x - 1 for x in list(map(int, input().split()))] for _ in range(N)]

def can_match(i, A, next_set):
	if not A[i]:
		return
	j = A[i][-1]
	if A[j][-1] == i:
		if i < j:
			next_set.add((i, j))
		else:
			next_set.add((j, i))

next_set = set()
for i in range(N):
	can_match(i, A, next_set)

day = 0
battle = 0
while next_set:
	day += 1
	current_set = next_set.copy()
	next_set = set()
	for match in current_set:
		battle += 1
		del A[match[0]][-1]
		can_match(match[0], A, next_set)
		del A[match[1]][-1]
		can_match(match[1], A, next_set)

if battle == N*(N-1) // 2:
	print(day)
else:
	print(-1)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
a = [0] + list(deque(map(int, input().split())) for _ in range(n))
cnt, cur, days = 0, [0] * (n + 1), [0] * (n + 1)
q = deque(list(range(1, n + 1)))
while q:
	x = q.popleft()
	if not a[x]:
		continue
	y = a[x].popleft()
	if cur[y] == x:
		cnt += 1
		days[x] = days[y] = max(days[x], days[y]) + 1
		cur[x], cur[y] = 0, 0
		q.append(x)
		q.append(y)
	else:
		cur[x] = y
res = max(days) if cnt == n * (n - 1) // 2 else -1
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
# （１行読み込み→splitしてlist化→各要素に対して-1する）←を逆順にする（[::-1]）をN回繰り返す
A = [[x-1 for x in list(map(int, input().split()))][::-1] for i in range(N)]

def can_match(i, A, next_set):
    if not A[i]: # A[i]が空の場合
        return
    j = A[i][-1] # j = iさんの次の対戦相手

    if A[j][-1] == i: # jさんの次の対戦相手がiさんの場合（＝相思相愛の場合）
        if i < j: # 常に(小, 大)で格納する
            next_set.add((i,j))
        else: # 常に(小, 大)で格納する
            next_set.add((j,i))

# next_setの初期化
next_set = set() # setは集合を表す
for i in range(N):
    can_match(i, A, next_set)

# 試合できるか？何日かかるか？を判別する
day = 0
battle = 0
while next_set:
    day += 1
    current_set, next_set = next_set, set()
    for match in current_set:
        battle += 1
        del A[match[0]][-1]
        can_match(match[0], A, next_set)
        del A[match[1]][-1]
        can_match(match[1], A, next_set)

if battle == N*(N-1)//2:
    print(day)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [[x-1 for x in list(map(int, input().split()))[::-1]] for _ in range(N)]

def can_match(i, A, next_set):
  if not A[i]:
    return
  j = A[i][-1]
  if A[j][-1] == i:
    if i < j:
      next_set.add((i,j))
    else:
      next_set.add((j,i))
      
next_set = set()
for i in range(N):
  can_match(i, A, next_set)
  
day = 0
battle = 0
while next_set:
  day += 1
  current_set, next_set = next_set, set()
  for match in current_set:
    battle += 1
    del A[match[0]][-1]
    can_match(match[0], A, next_set)
    del A[match[1]][-1]
    can_match(match[1], A, next_set)
    
if battle == N*(N-1)//2:
  print(day)
else:
  print(-1)

Submission status: Accepted

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

def can_match(i, A, next_set):
  if not A[i]:
    return
  j = A[i][-1]
  if A[j][-1] == i:
    if i < j:
      next_set.add((i,j))
    else:
      next_set.add((j,i))
      
next_set = set()
for i in range(N):
  can_match(i, A, next_set)
  
day = 0
battle = 0
while next_set:
  day += 1
  current_set, next_set = next_set, set()
  for match in current_set:
    battle += 1
    del A[match[0]][-1]
    can_match(match[0], A, next_set)
    del A[match[1]][-1]
    can_match(match[1], A, next_set)
    
if battle == N*(N-1)//2:
  print(day)
else:
  print(-1)

Submission status: Accepted

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

def can_match(i, A, next_set):
  if not A[i]:
    return
  j = A[i][-1]
  if A[j][-1] == i:
    if i < j:
      next_set.add((i,j))
    else:
      next_set.add((j,i))
      
next_set = set()
for i in range(N):
  can_match(i, A, next_set)
  
day = 0
battle = 0
while next_set:
  day += 1
  current_set, next_set = next_set.copy(), set()
  for match in current_set:
    battle += 1
    del A[match[0]][-1]
    can_match(match[0], A, next_set)
    del A[match[1]][-1]
    can_match(match[1], A, next_set)
    
if battle == N*(N-1)//2:
  print(day)
else:
  print(-1)

Submission status: Accepted

Solution code:

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


def can_match(i, A, next_set):
  if not A[i]:
    return
  j = A[i][-1]
  if A[j][-1] == i:
    if i < j:
      next_set.add((i,j))
    else:
      next_set.add((j,i))

      
next_set = set()
for i in range(N):
  can_match(i, A, next_set)
  
day = 0
battle = 0
while next_set:
  day += 1
  current_set = next_set.copy()
  next_set = set()
  for match in current_set:
    battle += 1
    del A[match[0]][-1]
    can_match(match[0], A, next_set)
    del A[match[1]][-1]
    can_match(match[1], A, next_set)
if battle == N*(N-1)//2:
  print(day)
else:
  print(-1)

Submission status: Accepted

Solution code:
def f_e():
    n = int(input())
    a = [list(map(lambda x: int(x)-1, input().split()))[::-1] for _ in range(n)]
    q, bench, days = list(range(n)), [-1]*n, [0]*n
    while q:
        i = q.pop(0)
        if not a[i]:
            continue
        you = a[i].pop()
        if bench[you] == i:
            days[i] = days[you] = max(days[i], days[you])+1
            bench[i] = bench[you] = -1
            q.append(i); q.append(you)
        else:
            bench[i] = you
    o = -1 if max(bench)>=0 else max(days)
    print(o)

if __name__ == "__main__":
    f_e()

Submission status: Accepted

Solution code:
from collections import deque

if __name__ == '__main__':
    N = int(input())
    matches = [[int(x) - 1 for x in input().split()] for _ in range(N)]
    q = deque(range(N))
    days = [0] * N
    pairs = [-1] * N
    while q:
        a = q.popleft()
        match = matches[a]
        if not match:
            continue
        b = match.pop(0)
        if pairs[b] == a:
            days[a] = days[b] = max(days[a], days[b]) + 1
            q.append(a)
            q.append(b)
        else:
            pairs[a] = b
    print(max(days) if not any(matches) else -1)

Submission status: Accepted

Solution code:
N = int(input())
Ass = tuple(tuple(map(int, input().split())) for _ in range(N))
index = [0 for _ in range(N)]

Q = set(range(N))
ans = -1
while Q:
    ans += 1
    Q2 = Q.copy()
    Q.clear()
    for i in Q2:
        if index[i] >= N - 1:
            continue
        t = Ass[i][index[i]] - 1
        if Ass[t][index[t]] == i + 1:
            Q.add(i)
            Q.add(t)
    for i in Q:
        index[i] += 1

if min(index) < N - 1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
N = int(input())
Ass = tuple(deque(map(int, input().split())) for _ in range(N))
 
Q = set(range(N))
ans = -1
while Q:
    ans += 1
    Q2 = Q.copy()
    Q.clear()
    for i in Q2:
        if not Ass[i]:
            continue
        t = Ass[i][0] - 1
        if Ass[t][0] == i + 1:
            Q.add(i)
            Q.add(t)
    for i in Q:
        Ass[i].popleft()

if any(Ass):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
N = int(input())
Ass = tuple(deque(map(int, input().split())) for _ in range(N))
 
Q = set(range(N))
ans = -1
while Q:
    ans += 1
    Q2 = Q.copy()
    Q.clear()
    for i in Q2:
        if Ass[i]:
            t = Ass[i][0] - 1
            if Ass[t][0] == i + 1:
                Q.add(i)
                Q.add(t)
    for i in Q:
        Ass[i].popleft()

if any(Ass):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
N = int(input())
Ass = tuple(deque(map(int, input().split())) for _ in range(N))
 
dp = [0 for _ in range(N)]
Q = set(range(N))
ans = -1
while Q:
    ans += 1
    Q2 = Q.copy()
    Q.clear()
    for i in Q2:
        if not Ass[i]:
            continue
        t = Ass[i][0] - 1
        if not Ass[t]:
            continue
        if Ass[t][0] == i + 1:
            Q.add(i)
            Q.add(t)
    for i in Q:
        Ass[i].popleft()

if any(Ass):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
match = [deque([int(i)-1 for i in input().split()]) for _ in range(n)]
q = deque(range(n)) # 走査対象を格納したキュー
wait = [-1] * n # 次に試合する相手リスト
finish_day = [0] * n # 参加者の全日程終了日
match_count = 0 # 試合数

while q:
    x = q.popleft()
    y = match[x].popleft()
    if wait[y] != x: # 次に試合したい相手を記録
        wait[x] = y
    else:
        match_count += 1
        match_day = max(finish_day[x], finish_day[y]) + 1
        finish_day[x] = finish_day[y] = match_day
        wait[x], wait[y] = -1, -1
        if match[x]: q.append(x)
        if match[y]: q.append(y)

if match_count != (n*(n-1)) /2:
    print(-1)
else:
    print(max(finish_day))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = set()

def check(i):
    if len(A[i]) == 0:
        return
    j = A[i][0]
    if len(A[j]) == 0:
        return
    if A[j][0] == i:
        if i > j:
            i, j = j, i
        Q.add((i, j))

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

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = Q.copy()
    Q = set()
    for q in Q2:
        A[q[0]].popleft()
        A[q[1]].popleft()
    for q in Q2:
        check(q[0])
        check(q[1])

for i in range(N):
    if len(A[i]) > 0:
        print(-1)
        exit()

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import deque


def getN():
    return int(input())


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


import math

n = getN()

match = [0 for i in range((n * (n - 1)) // 2)]
child = [[] for i in range((n * (n - 1)) // 2)]
iriji = [0 for i in range((n * (n - 1)) // 2)]


def toposo(n, iriji, child):
    order = [0 for i in range((n*(n+1))//2)]
    q = deque([])
    for i, iri in enumerate(iriji):
        if iri == 0:
            q.append(i)
            order[i] = 1
    while(q):
        start = q.popleft()
        target = child[start]
        for tgt in target:
            iriji[tgt] -= 1
            if iriji[tgt] == 0:
                q.append(tgt)
                order[tgt] = order[start] + 1

    if sum(iriji) != 0:
        return -1

    else:
        return max(order)


for idd in range(n):
    nums = getList()
    i = idd + 1
    for j, k in zip(nums, nums[1:]):
        ii, j = min(i, j), max(i, j)
        iii, k = min(i, k), max(i, k)
        idx1 = ((j - 1) * (j - 2)) // 2 + (ii - 1)
        idx2 = ((k - 1) * (k - 2)) // 2 + (iii - 1)
        iriji[idx2] += 1
        child[idx1].append(idx2)
        # print(i, j, k)
        # print(idx1, idx2)

#
# print(child)
# print(isroot)
# # sys.exit()
#
# bfs()
# # print("gg")
# ans = 1
# for m in match:
#     if m > ans:
#         ans = m
#     if m == 0:
#         print(-1)
#         sys.exit()
# print(iriji, child)

print(toposo(n, iriji, child))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [[i-1 for i in map(int,input().split())][::-1] for j in range(n)]
def check(i):
  if a[i] == []:
    return
  elif a[a[i][-1]][-1] == i:
    q.add((min(a[i][-1],i),max(a[i][-1],i)))
q = set()
for i in range(n):
  check(i)
d = 0
while q:
  d += 1
  pq = set()
  pq,q = q,pq
  for i in pq:
    del a[i[0]][-1],a[i[1]][-1]
    check(i[0])
    check(i[1])
for i in a:
  if i != []:
    print(-1)
    exit()
print(d)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from collections import deque

import queue

def get_ind(pre_tuple, num):
    a, b = pre_tuple
    ans = (a - 1) * num + b
    return ans



def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]

    graph_data = [set() for i in range(num * num)]
    parent_node = [0 for i in range(num * num)]

    for i in range(num):
        now_node = i + 1
        pre_tuple = (0, 0)
        for j in range(num - 1):
            next_node = data[i][j]
            now_tuple = (min(now_node, next_node), max(now_node, next_node))
            if j == 0:
                pass
                # parent_node[now_tuple] += 0
            else:
                index = get_ind(pre_tuple, num)
                # print(index, pre_tuple)
                graph_data[index].add(now_tuple)
                index2 = get_ind(now_tuple, num)
                parent_node[index2] += 1
            pre_tuple = now_tuple

    q = deque([])
    count_node, ans = 0, 0

    for i in range(1, num + 1):
        for j in range(i + 1, num + 1):
            node = (i, j)
            index = get_ind(node, num)
            if parent_node[index] == 0:
                q.append((node, 1))
                count_node += 1

    ans = 0
    while len(q) > 0:
        now_node, length = q.popleft()
        ans = max(ans, length)
        index = get_ind(now_node, num)
        for next_node in graph_data[index]:
            index2 = get_ind(next_node, num)
            parent_node[index2] -= 1
            if parent_node[index2] == 0:
                q.append((next_node, length + 1))
                count_node += 1

    if count_node < (num * (num - 1)) // 2:
        print(-1)
    else:
        print(ans)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from collections import deque

import queue

def get_ind(pre_tuple, num):
    a, b = pre_tuple
    ans = (a - 1) * num + b
    return ans



def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]

    graph_data = [set() for i in range(num * num)]
    parent_node = [0 for i in range(num * num)]

    for i in range(num):
        now_node = i + 1
        pre_tuple = (0, 0)
        for j in range(num - 1):
            next_node = data[i][j]
            now_tuple = (min(now_node, next_node), max(now_node, next_node))
            if j == 0:
                pass
                # parent_node[now_tuple] += 0
            else:
                index = get_ind(pre_tuple, num)
                # print(index, pre_tuple)
                graph_data[index].add(now_tuple)
                index2 = get_ind(now_tuple, num)
                parent_node[index2] += 1
            pre_tuple = now_tuple

    q = deque([])
    count_node, ans = 0, 0

    for i in range(1, num + 1):
        for j in range(i + 1, num + 1):
            node = (i, j)
            index = get_ind(node, num)
            if parent_node[index] == 0:
                q.append((node, 1))
                count_node += 1

    while len(q) > 0:
        now_node, length = q.popleft()
        index = get_ind(now_node, num)
        for next_node in graph_data[index]:
            index2 = get_ind(next_node, num)
            parent_node[index2] -= 1
            if parent_node[index2] == 0:
                q.append((next_node, length + 1))
                count_node += 1

    if count_node < (num * (num - 1)) // 2:
        print(-1)
    else:
        print(length)







if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
maxmatch=n*(n-1)
day=0
q=[i for i in range(n)]
nq=[]
match=[0]*(n+1)
check=[0]*(n+1)
while q:
  day+=1
  for i in q:
    if match[i]==n-1 or check[i]==day:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[vs]!=day and check[i]!=day and a[vs][match[vs]]-1==i and a[i][match[i]]-1==vs:
        match[i]+=1
        match[vs]+=1
        match[n]+=2
        check[i]=day
        check[vs]=day
        check[n]=day
        nq.append(i)
        nq.append(vs)
      
    if i==q[-1]:
      if check[n]!=day:
        print(-1)
        sys.exit()
  if match[n]==maxmatch:
    break
  q=nq[:]
  nq=[]
        
print(day)

Submission status: Accepted

Solution code:
import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
maxmatch=n*(n-1)
day=0
q=[i for i in range(n)]
nq=[]
match=[0]*(n+1)
check=[0]*(n+1)
while q:
  day+=1
  for i in q:
    if match[i]==n-1 or check[i]==day:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[vs]!=day and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        match[n]+=2
        check[i]=day
        check[vs]=day
        check[n]=day
        nq.append(i)
        nq.append(vs)
      
    if i==q[-1]:
      if check[n]!=day:
        print(-1)
        sys.exit()
  if match[n]==maxmatch:
    break
  q=nq[:]
  nq=[]
        
print(day)

Submission status: Accepted

Solution code:
#E
from collections import deque
n = int(input())
matches = [list(a -1 for a in map(int,input().split()))
     for _ in range(n)]
q = deque(range(n))
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    ma = matches[a]
    if not ma:
        continue
    # gyaku kara kanngaeteru
    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:
import sys

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

canUse = set(range(N))

ans = 0
done = 0
while done < N:
    ans += 1
    canUseNew = set()
    # print("LC", len(canUse))
    for n in canUse:
        if not A[n]:
            continue

        first = A[n][-1]
        if first in canUseNew or n in canUseNew:
            continue

        if A[first][-1] == n:
            # print("Do", n + 1, first + 1)
            A[n].pop()
            if len(A[n]) == 0:
                done += 1
            A[first].pop()
            if len(A[first]) == 0:
                done += 1
            canUseNew.add(n)
            canUseNew.add(first)

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

print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep="\n") if type(a)!=type("a") else print(a)
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    """
    #この試合はこの試合のあとでないといけない、という条件がいくつもあるので
    #クリティカルパスを求めるイメージ(トポロジカルソート)
    #もしDAGでなければ無理なので-1
    N = I()
    A = LLIN_(N)
    #M = 0 #試合数
    edge = defaultdict(list)
    matches = set()
    for i,a in enumerate(A):
        for j,rival in enumerate(a):
            p1,p2 = sorted([i,rival])
            match = (p1,p2)
            matches.add(match)
            if j != N-2:
                p1,p2 = sorted([i,a[j+1]])
                next_match = (p1,p2)
                edge[match].append(next_match)

    dp = {}
    visited = set()
    def dfs(match):
        #print("dfs",match,visited,sep="\n")
        if match in visited:
            #print(match,dp)
            if match in dp:
                return dp[match]
            else:
                print(-1)
                exit()
        visited.add(match)
        dp[match] = 0
        for next_match in edge[match]:
            dp[match] = max(dp[match], dfs(next_match)+1)

        #print(match,dp[match])
        return dp[match]

    ans = 0
    for match in matches:
        #print(match)
        res = dfs(match) + 1
        ans = max(ans,res)
    print(ans)"""




    #O(試合数)
    N = I()
    A = []
    #消化した試合は削除していく
    for _ in range(N):
        *a, = reversed(LI_())
        A.append(a)
    #pprint("A",A)
    
    match = set()
    for i,a in enumerate(A):
        rival = a[-1]
        rival_of_rival = A[rival][-1]
        if rival_of_rival == i:
            match.add(i)
            match.add(rival)

    
    day = 0
    while match:
        day += 1
        last_match = set()
        last_match,match = match,last_match

        for i in last_match:
            A[i].pop()
        
        for i in last_match:
            if A[i]:
                rival = A[i][-1]
                rival_of_rival = A[rival][-1]
                if rival_of_rival == i:
                    match.add(i)
                    match.add(rival)
    for a in A:
        if a:
            print(-1)
            exit()

    print(day)

    """ O(N^3)
    N = I()
    A = LLIN_(N)
    indexes = [0] * N
    cnt = 0
    match = set()
    for i in range(N*N):
        update = False
        today_players = set()
        for k in range(N):
            index = indexes[k]
            if index >= N-1: #全試合done
                continue
            rival = A[k][index]
            if (k,rival) in match: #前回の希望相手との試合がまだ
                continue
            if (rival,k) in match :
                if not {k,rival} & today_players:
                    cnt += 1
                    update = True
                    match.remove((rival,k))
                    today_players.add(k)
                    today_players.add(rival)
                    indexes[k] += 1
                    indexes[rival] += 1
            else:
                match.add((k,rival))


            
        if not update:
            if cnt != (N*(N-1))//2:
                print(-1)
                exit()
            else:
                print(i)
                exit()"""

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)

Submission status: Accepted

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

N=int(input())
L=[list(map(lambda x:int(x)-1,input().split())) for _ in range(N)]
q=deque(range(N))
days=[0]*N
pairs=[-1]*N
while q:
	a=q.popleft()
	if len(L[a])==0:continue
	b=L[a].pop(0)
	if pairs[b]==a:
		days[a]=days[b]=max(days[a],days[b])+1
		q.append(a);q.append(b)
	else:
		pairs[a]=b
print(max(days) if not any(L)else -1)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())

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


match_q = set([])
for i in range(N):
    a = A[i][0] #iの先頭
    b = A[a][0] #aの先頭
    if i == b:
        if i > a:
            i, a = a, i
        
        match_q.add((i, a))


def check(pair):
    i, j = pair
    if i > j:
        i, j = j, i
    if len(A[i]) == 0:
        return
    if len(A[j]) == 0:
        return
    
    A[i].popleft()
    A[j].popleft()

    for idx in [i, j]:
        if len(A[idx]) != 0:
            a = A[idx][0] # iの先頭
            b = A[a][0] # aの先頭
            if idx == b:
                if idx > a:
                    idx, a = a, idx
                match_q.add((idx, a))
    return


count = 0
while(len(match_q) != 0):
    count += 1
    old_q = match_q
    match_q = set([])
    for pair in old_q:
        check(pair)


if any(len(pair) != 0 for pair in A):
    print(-1)
else:
    print(count)

Submission status: Accepted

Solution code:
n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
now = []
for i in range(n):
  j = raw[i][cnt[i]]
  if raw[j][cnt[j]] == i and i < j:
    now.append([i,j])
ans = 0
while now:
  #print(now)
  last = now
  now = []
  for x in last:
    i,j = x[0],x[1]
    cnt[i] += 1
    cnt[j] += 1
    if cnt[i] < n-1:
      k = raw[i][cnt[i]]
      if raw[k][cnt[k]] == i:
        now.append([i,k])
    if cnt[j] < n-1:
      k = raw[j][cnt[j]]
      if raw[k][cnt[k]] == j:
        now.append([j,k])
  ans += 1
if all( cnt[i] == n-1 for i in range(n) ):
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
#7271131(wotsushi)解答
n = int(input())
a = []
for _ in range(n):
  a.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
now = []
for i in range(n):
  j = a[i][cnt[i]]
  if a[j][cnt[j]] == i and i < j:
    now.append([i,j])
ans = 0
while now:
  #print(now)
  last = now
  now = []
  for x in last:
    i = x[0]
    j = x[1]
    cnt[i] += 1
    cnt[j] += 1
    if cnt[i] < n-1:
      k = a[i][cnt[i]]
      if a[k][cnt[k]] == i:
        now.append([i,k])
    if cnt[j] < n-1:
      k = a[j][cnt[j]]
      if a[k][cnt[k]] == j:
        now.append([j,k])
  ans += 1
if all(cnt[i] == n-1 for i in range(n)):
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
import time
n=int(input())
al=[list(map(int,input().split())) for _ in range(n)]
m=n*(n-1)//2
tn=[n-1]*n
start=time.time()
for i in range(m+1):
    flg=True
    s=0
    ts=set()
    for j in range(n):
        if tn[j]>0 and j not in ts:
            t=al[j][0]-1
            if t not in ts:
                if al[t][0]==j+1:
                    al[t].pop(0)
                    tn[t]-=1
                    ts.add(t)
                    al[j].pop(0)
                    tn[j]-=1
                    flg=False
        ts.add(j)
        s+=tn[j]
    if s==0:
        print(i+1)
        exit()
    if flg:
        print(-1)
        exit()
    now=time.time()
    if (now-start)>1.6:
        print(m)
        exit()