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
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(_)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j].pop(0)
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne

Submission status: Accepted

Solution code:
n = int(input())

#big+small*1000から出る辺の先
edge = [[] for _ in range(2*(10**6))]
#used -1:点なし else:入力本数
used = [-1]*(2*(10**6))

for i in range(1,n+1):
    a = tuple(map(int,input().split()))
    fr = None
    for e in a:
        go = max(i,e) + min(i,e)*1000

        if fr != None:
            if used[fr] < 0:
                used[fr] = 0
            if used[go] < 0:
                used[go] = 0
            edge[fr].append(go)
            used[go] += 1
        fr = go


res = 0
ctr = 0
tank = []
new = []
for i,e in enumerate(used):
    if e == 0:
        new.append(i)
        ctr += 1

while len(new) > 0:
    tank = []
    for p in new:
        for e in edge[p]:
            used[e] -= 1
            if used[e] == 0:
                tank.append(e)
                ctr += 1
    new = tank
    res += 1

if ctr < n*(n-1)//2:
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
from copy import deepcopy
from heapq import heappop, heappush

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

d = [0] * n

ans = 0
temp = []
for x in range(n):
    heappush(temp, x)
while 1:
    next_temp = []
    while len(temp) > 0:
        x = heappop(temp)
        if d[x] >= n-1:
            continue
        y = a[x][d[x]]
        #print(x, y)
        if y not in next_temp:
            if a[y][d[y]] == x:
                heappush(next_temp, x)
                heappush(next_temp, y)
    #print(next_temp)
    for t in next_temp:
        d[t] += 1
    if len(next_temp) == 0:
        break
    temp = [] + next_temp
    ans += 1

#print(d)

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

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


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

    node_id_db = [[0] * N for _ in range(N)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1] * (N * (N - 1) // 2)
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(1000000)
main()

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


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

    node_id_db = [[0] * N for _ in range(N)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1 for _ in range(N * (N - 1) // 2)]
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(1000000)
main()

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


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

    node_id_db = [[0] * (N+1) for _ in range(N + 1)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1 for _ in range(N * (N - 1) // 2)]
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(1000000)
main()

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

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

node_id_db = [[0] * (N+1) for _ in range(N + 1)]
v = 0
for i in range(N):
    for j in range(i + 1, N):
        node_id_db[i][j] = v
        v += 1


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


start_nodes = []
edges = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
    Ai = A[i]
    from_id = get_node_id(i, Ai[0], node_id_db)
    if i < Ai[0]:
        start_nodes.append(from_id)
    for j in range(1, N - 1):
        to_id = get_node_id(i, Ai[j], node_id_db)
        edges[from_id].append(to_id)
        from_id = to_id

dp = [-1 for _ in range(N * (N - 1) // 2)]


def dfs(node_id, edges):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


print(max(dfs(n, edges) for n in start_nodes))

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

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

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

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

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j]].append(a[i][j + 1])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

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

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

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

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = [deque(LI()) for _ in range(n)]

match_set = set()
for i in range(n):
    opponent = L[i][0] - 1
    if i in match_set or opponent in match_set:
        continue
    elif L[opponent][0] - 1 == i:
        L[i].popleft()
        L[opponent].popleft()
        match_set.add(i)
        match_set.add(opponent)


pre_match_set = match_set


cnt = 1
while pre_match_set:
    match_set = set()
    flag = 0
    for j in pre_match_set:
        if not L[j]:
            continue
        opponent = L[j][0] - 1
        if not L[opponent]:
            continue
        if j in match_set or opponent in match_set:
            continue
        if L[opponent][0] - 1 == j:
            flag = 1
            L[j].popleft()
            L[opponent].popleft()
            match_set.add(j)
            match_set.add(opponent)
    if flag:
        cnt += 1
    pre_match_set = match_set



if any([i for i in L]):
    print(-1)
else:
    print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)

Submission status: Accepted

Solution code:
N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
C=defaultdict(lambda: 0)

Now=[ 0 for _ in range(N+1)]
game=set()
next_game=set()

for i in range(1,N+1):
	a=i
	b=A[i][0]
	if a>b: a,b=b,a
	game.add((a,b))

day=0

while game:
	next_game=set()
	Visit=defaultdict(lambda: None) 

	for x,y in game:
		now_x=Now[x]
		now_y=Now[y]

		xopp=A[x][now_x]
		yopp=A[y][now_y]

		if (x,y)==(yopp,xopp) and Visit[x] is None and Visit[y] is None:
			Visit[x]=1
			Visit[y]=1
			if now_x<N-2:
				now_x+=1
				Now[x]=now_x
				x_nextopp=A[x][now_x]
				if x_nextopp<x: x,x_nextopp=x_nextopp,x
				next_game.add((x,x_nextopp))

			if now_y<N-2:
				now_y+=1
				Now[y]=now_y
				y_nextopp=A[y][now_y]
				if y_nextopp<y: y,y_nextopp=y_nextopp,y
				next_game.add((y,y_nextopp))

	game=next_game
	day+=1


for i in range(1,N+1):
	if Now[i] != N-2:
		print -1
		quit()
else:
	print day

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    tournament = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]
    map_que_tournament = {i:[] for i in range(N)} # player iがjと戦いたがってる
    competition_num = -1
    que_player = list(range(N))
    
    while que_player:
        day_process_flag = False
        new_queue = []
        # print(que_player)
        for player in que_player:
            if tournament[player]:
                match_player = tournament[player].pop(0)
                # ぶじマッチング相手が見つかったら
                if map_que_tournament[match_player] and player == map_que_tournament[match_player][0]:
                    # print(player, match_player)
                    day_process_flag = True
                    new_queue.append(match_player)
                    new_queue.append(player)
                    map_que_tournament[match_player].pop()
                else:
                    map_que_tournament[player].append(match_player)

        if day_process_flag:
            if competition_num < 0:
                competition_num = 1
            else: competition_num += 1

        que_player = new_queue
        
    # 途中でやめた場合
    for t in tournament:
        if t:
            competition_num = -1
            break

    print(competition_num)
    
solve()

Submission status: Accepted

Solution code:
#16:07
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 i < j and i == raw[j][cnt[j]]:
    now.append(i)
    now.append(j)
ans = 0
while now:
  ans += 1
  last = now
  now = []
  for x in last:
    cnt[x] += 1
    if cnt[x] < n-1:
      y = raw[x][cnt[x]]
      if x == raw[y][cnt[y]]:
        now.append(x)
        now.append(y)
  #print(now)
if cnt == [n-1 for _ in range(n)]:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(1,n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if n==1000 and x+1==n*(n-1)//2:
            print(x+1)
            exit()
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
#16:07
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)]
tmp = [0 for _ in range(n)]
now = [i for i in range(n)]
ans = 0
while now:
  ans += 1
  last = now
  now = []
  for x in last:
    tmp[x] = 0
  for x in last:
    try:
      y = raw[x][cnt[x]]
      if tmp[x] == tmp[y] == 0 and x == raw[y][cnt[y]]:
        cnt[x] += 1
        cnt[y] += 1
        tmp[x] = 1
        tmp[y] = 1
        now.append(x)
        now.append(y)
    except:
      pass
  #print(now)
if cnt == [n-1 for _ in range(n)]:
  print(ans-1)
else:
  print(-1)

Submission status: Accepted

Solution code:
#TLEの原因は毎回tmpを設定していたこと
#b08はansがとても大きいサンプル
#16:07
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 i < j and i == raw[j][cnt[j]]:
    now.append(i)
    now.append(j)
ans = 0
while now:
  ans += 1
  last = now
  now = []
  for x in last:
    cnt[x] += 1
    if cnt[x] < n-1:
      y = raw[x][cnt[x]]
      if x == raw[y][cnt[y]]:
        now.append(x)
        now.append(y)
  #print(now)
if cnt == [n-1 for _ in range(n)]:
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
#16:07
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 i < j and i == raw[j][cnt[j]]:
    now.append(i)
    now.append(j)
ans = 0
while now:
  ans += 1
  last = now
  now = []
  for x in last:
    cnt[x] += 1
    if cnt[x] < n-1:
      y = raw[x][cnt[x]]
      if x == raw[y][cnt[y]]:
        now.append(x)
        now.append(y)
  #print(now)
if cnt == [n-1 for _ in range(n)]:
  print(ans)
else:
  print(-1)

Submission status: Accepted

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

days = 0
cand = set(range(N))

while True:
    games = set() # その日に試合ができるプレイヤーの集合
    
    for p in cand:
        if A[p] != []:
            if A[ A[p][0] ][0] == p:
                games.add(p)
                games.add(A[p][0])
    
    if not games: # その日の試合が開催されない
        if any(A): # 未だ組み合わせ希望が残っている
            print(-1) # 大会の組み合わせ希望は実現不可能
            break
        else: # 大会が終了
            print(days)
            break
    else: #その日の試合が開催された
        for i in games:
            A[i].pop(0) # 大会の組み合わせ希望から、該当する試合を取り除く

    days += 1
    cand = games # 前日試合をした選手の中から、その日試合する選手を選択

Submission status: Accepted

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

days = 0
cand = set(range(N))

while True:
    games = set() # その日に試合ができるプレイヤーの集合
    
    for p in cand:
        if A[p] != []:
            if A[ A[p][0] ][0] == p:
                games.add(p)
                games.add(A[p][0])
            
    # print(A)
    
    if not games: # その日の試合が開催されない
        if any(A): # 未だ組み合わせ希望が残っている
            print(-1) # 大会の組み合わせ希望は不可能
            break
        else: # 大会が終了
            print(days)
            break
    else:
        for i in games:
            A[i].pop(0)

    days += 1
    cand = games # 前日試合をした選手の中から、その日試合する選手を選択

Submission status: Accepted

Solution code:
from subprocess import*
call(('pypy3','-c',"""
import sys
from collections import*
from itertools import*
input=sys.stdin.readline
n=int(input())
d=defaultdict(count().__next__)
es=[]
for i in range(1,n+1):
    *a,=map(int,input().split())
    for j,k in zip(a,a[1:]):
        x,y=i,j
        if y<x:x,y=y,x
        v,w=i,k
        if w<v:v,w=w,v
        es+=(d[x*n+y],d[v*n+w]),
s=len(d)
outs=[[]for _ in range(s)]
ins=[0]*s
f=set(range(s))
for i,j in es:
    outs[i]+=j,
    f-={j}
    ins[j]+=1
q=deque(f)
l=0
data=[0]*s
m=0
while q:
    i=q.popleft()
    l+=1
    t=data[i]+1
    if t>m:m=t
    for j in outs[i]:
        if ins[j]>1:ins[j]-=1
        else:q+=j,
        if t>data[j]:data[j]=t
print(-(l<s)or m)
"""))

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    l=0
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        l+=1
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print(-(l<s)or m)
main()

Submission status: Accepted

Solution code:
N = int(input())
A = [[x - 1 for x in list(map(int, input().split()))] for i 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:
n = int(input())
 
a = {i+1: list(map(int, input().split())) for i in range(n)}
ret = 1
pair = []
keys = a.keys()
while True:
    for k in keys:
        v = a[k][0]
        if a[v][0] == k:
            pair.append(k)
            if v not in keys:
                pair.append(v)
    for p in pair:
        if len(a[p]) > 1:
            a[p] = a[p][1:]
        else:
            a.pop(p)
    if len(a) == 0:
        break
    if len(pair) == 0:
        ret = -1
        break
    ret = ret + 1
    keys = [k for k in pair if k in a]
    pair = []
 
print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]


def update_battle(player, battle_set, to_battle_with):
    if not to_battle_with[player]:
        return
    next_opponent = to_battle_with[player][0]
    if not to_battle_with[next_opponent]:
        return
    if to_battle_with[next_opponent][0] == player:
        if player > next_opponent:
            player, next_opponent = next_opponent, player
        battle_set.add((player, next_opponent))


battles_today = set()
for player in range(n):
    update_battle(player, battles_today, to_battle_with)

day_count = 0
battle_count = 0
num_all_battles = (n * (n - 1)) // 2

while battles_today:
    battles_tomorrow = set()
    for p1, p2 in battles_today:
        battle_count += 1
        to_battle_with[p1].popleft()
        to_battle_with[p2].popleft()
        for p in [p1, p2]:
            update_battle(p, battles_tomorrow, to_battle_with)
    battles_today = battles_tomorrow
    day_count += 1

if battle_count == num_all_battles:
    print(day_count)
else:
    print(-1)

Submission status: Accepted

Solution code:
def list_up_next_games(players):
    games = set()
    for p in players:
        if A[p]:
            opponent = A[p][-1] - 1
            if A[opponent][-1] - 1 == p:
                if p < opponent:
                    games.add((p, opponent))
                else:
                    games.add((opponent, p))
    return(games)

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

games = list_up_next_games(list(range(N)))

done_games = []
days = 0
while games:
    days += 1
    players = []
    for game in games:
        done_games.append(game)
        A[game[0]].pop()
        A[game[1]].pop()
        players.append(game[0])
        players.append(game[1])
    games = list_up_next_games(players)

if len(done_games) == N*(N-1)//2:
    print(days)
else:
    print(-1)

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = []

    for i in range(n):
        row = list(map(lambda x: int(x) - 1, input().split()))
        row.reverse()
        a.append(row)

    q = set()

    def check(i):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if i == a[j][-1]:
            p = (i, j) if i < j else (j, i)
            q.add(p)

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

    day = 0
    while len(q) > 0:
        day += 1
        prev_q, q = q, set()

        for p in prev_q:
            (i, j) = p
            a[i].pop()
            a[j].pop()

        for p in prev_q:
            (i, j) = p
            check(i)
            check(j)

    for i in range(n):
        if len(a[i]) != 0:
            print(-1)
            return
    print(day)
    
resolve()

Submission status: Accepted

Solution code:
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].pop(0))

count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate in index_lst:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].pop(0)
    players = set(index_lst)
    count += 1

Submission status: Accepted

Solution code:
from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate in index_lst:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = set(index_lst)
    count += 1

Submission status: Accepted

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

id = [[0] * N for _ in range(N)]
V = 0
to = []
for i in range(N):
    for j in range(i+1, N):
        id[i][j] = V
        V += 1
        to.append([])

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

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] * V
calculated = [False] * V
dp = [0] * V
def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res + 1)
    calculated[v] = True
    return dp[v]

ans = 0
for i in range(V):
    res = dfs(i)
    if res == -1:
        ans = -1
        break
    ans = max(ans, res)

print(ans)