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 collections


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)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    ad = [0] * n
    q = collections.deque([[0, i] for i in range(n)])
    for i in range(10 ** 20):
        fq = collections.defaultdict(list)
        while True:
            if len(q) != 0:
                d, p = q.popleft()
                if d == i:
                    if p not in fq:
                        tp = a[p][ad[p]]
                        if tp not in fq:
                            if p == a[tp][ad[tp]]:
                                fq[tp]
                                fq[p]
                                ad[tp] += 1
                                ad[p] += 1
                                if ad[tp] < n - 1:
                                    q.append([d+1, tp])
                                if ad[p] < n - 1:
                                    q.append([d+1, p])
                else:
                    q.appendleft([d, p])
                    break
            else:
                if sum(ad) == n * (n - 1):
                    print(i + 1)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    slove()

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:
from collections import deque
def solve():
    n = int(input())
    a = []
    for i in range(n):
        ai = [int(j)-1 for j in input().split()]
        a.append(deque(ai))
    d = set()
    q = deque()
    for i in range(n):
        ai = a[i].popleft()
        if i < ai:
            q.append((i, ai))
        else:
            q.append((ai, i))
    ans = 0
    while q:
        ans += 1
        nxt_q = deque()
        while q:
            i, ai = q.pop()
            if (i, ai) in d:
                if a[i]:
                    ni = a[i].popleft()
                    if i < ni:
                        nxt_q.append((i, ni))
                    else:
                        nxt_q.append((ni, i))
                if a[ai]:
                    ni = a[ai].popleft()
                    if ai < ni:
                        nxt_q.append((ai, ni))
                    else:
                        nxt_q.append((ni, ai))
            else:
                d.add((i, ai))
        q = nxt_q
    if any(i for i in a):
        ans = -1
    print(ans)

solve()

Submission status: Accepted

Solution code:
n = int(input())
# 隣接リスト
graph = {i+1000*j:[] for i in range(n) for j in range(i+1,n)}
# 入次数を管理
st = {i+1000*j:0 for i in range(n) for j in range(i+1,n)}


# 入次数が0の頂点の集まり
szero = []

#ソートされたやつたち
ans = []

for i in range(n):
    ls = list(map(int,input().split()))
    f = -1
    for p in ls:
        v = min(i,p-1) + 1000*(max(i,p-1))
        if f != -1:
            graph[f].append(v)
            st[v] += 1
        f = v

for v in st.keys():
    if st[v] == 0:szero.append(v)
count = 0
next_szero = []
while True:
    count += 1
    for i in szero:
        ans.append(i)
        for v in graph[i]:
            st[v] -= 1
            if st[v] == 0:
                next_szero.append(v)
    if len(next_szero) == 0:break
    szero = next_szero
    next_szero = []

if len(ans) != n*(n-1)//2:
    print(-1)
else:
    print(count)

Submission status: Accepted

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

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

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1
# print(A)
# print(M)

# 以下、トポロジカルソート

S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        # print(x,IN)
        if IN[x] == 0:
            S.append(x)
    s += 1

# print(S)

if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))


# 以下、閉路検出(今は削除)

# V = [0] * id_
# S = [0]
# V[0] = 1

# import sys

# def visit(x):
#     if V[x] == 1:
#         print(-1)
#         sys.exit()
#     elif V[x] == 0:
#         V[x] = 1
#         for i in M[x]:
#             visit(i)
#         V[x] = 2

# for i in range(id_):
#     if V[i] == 0:
#         visit(i)
# print("heironasi")

# 閉路検出ここまで

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = [list(map(lambda x:int(x)-1,input().split())) for _ in range(N)]
    cur = [0 for _ in range(N)]
    yesterday = set(range(N))
    rest = N * (N-1)
    day = 0
    while len(yesterday) > 0 and rest > 0:
        today = set()
        totoday = set()
        for y in yesterday:
            o = A[y][cur[y]]
            if A[o][cur[o]] == y:
                today.add(o)
                today.add(y)
        for t in today:
            cur[t] += 1
            if cur[t] < N-1:
                totoday.add(t)
        rest -= len(today)
        yesterday = totoday
        day += 1
    if rest == 0:
        print(day)
    else:
        print(-1)
resolve()

Submission status: Accepted

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

def solve(n, xss):
    yss = [[-1] + list(reversed(xs)) for xs in xss]
    ans = 0
    candidates = range(n)
    while True:
        #print(" ".join(map(str, candidates)))
        ms = list(matches(yss, candidates))
        if len(ms) == 0:
            if all(len(ys)==1 for ys in yss):
                return ans
            else:
                return -1
        ans += 1
        candidates = []
        #print(" ".join(map(str, ms)))
        for x, y in ms:
            yss[x].pop()
            yss[y].pop()
            candidates.append(x)
            candidates.append(y)

def matches(yss, candidates):
    firsts = [yss[i][-1] for i in candidates]
    ans = set()
    for x, y in zip(candidates, firsts):
        if y!=-1 and yss[y][-1] ==x:
            ans.add((min(x, y), max(x, y)))
    return ans

print(solve(n, xss))

Submission status: Accepted

Solution code:
#prdさんのを写経
import sys
input=sys.stdin.readline

n=int(input())
a=[list(reversed(list(map(lambda x:int(x)-1, input().split())))) for _ in range(n)]
b={i:r for i,r in enumerate(a)}

end=0
for k in range(8000):
    used=set()
    dels=[]
    for i,q in b.items():
        if not q:
            continue
        if i in used:
            continue
        j=q[-1]
        if j in used:
            continue
        if a[j][-1]==i:
            a[j].pop()
            a[i].pop()
            used.add(i)
            used.add(j)
            if not a[i]:
                end+=1
                dels.append(i)
            if not a[j]:
                end+=1
                dels.append(j)
    if not used:
        print(-1)
        exit()
    if end==n:
        print(k+1)
        exit()
    for i in dels:
        del b[i]

print(n*(n-1)//2)

Submission status: Accepted

Solution code:
import itertools
#0-indexed
N = int(input())
A = [[int(_) - 1 for _ in input().split()][::-1] for _ in range(N)]
ans = 0
cand = range(N)
left = 1
while True:
    cand_ = set()
    for i in cand:
        v = A[i]
        if not len(v):
            continue
        if A[v[-1]][-1] == i:
            f = 0
            cand_.add(i)
            cand_.add(v[-1])
    if not cand_:
        break
    cand = cand_
    left = 0
    for i in cand:
        A[i].pop()
        left |= len(A[i]) > 0
    ans += 1
if left:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue


# sys.stdin = open('input')
# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())


def main():
    n = map(int, raw_input().split())[0]
    da = [map(int, raw_input().split()) for i in range(n)]
    need = [0 for i in range(n+2)]
    t = [0 for i in range(n+2)]
    idx = [0 for i in range(n+2)]
    l = n*(n-1)/2
    ans = 0
    q = deque()
    for i in range(1, n+1):
        da[i-1].append(n+1)
        need[i] = da[i-1][idx[i]]
        if i == need[need[i]]:
            q.append(i);
    # print da
    while q:
        # print q
        fr = q.popleft()
        x, y = fr, need[fr]
        # print x,y,"sssssssss"
        # print need
        if not (x == need[y] and y == need[x]):
            continue
        ti = max(t[x], t[y]) + 1
        t[x] = t[y] = ti
        ans = max(ans, ti)
        l-=1
        idx[x] += 1
        idx[y] += 1
        need[x] = da[x-1][idx[x]]
        need[y] = da[y-1][idx[y]]
        if x == need[need[x]]:
            q.append(x)
        if y == need[need[y]]:
            q.append(y)
    # print l
    if l==0:
        print ans
    else:
        print -1






main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    # popするため逆順にしておく
    A=[list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]
    for i in range(n): A[i].reverse()
    stack=[]

    def check(i):
        if(not A[i]): return
        j=A[i][-1]
        if(A[j][-1]==i):
            stack.append((min(i,j),max(i,j)))

    # calculate
    for i in range(n): check(i)
    day=0
    while(stack):
        day+=1
        stack=list(set(stack)) # uniqueを取る
        prev,stack=stack,[]
        for i,j in prev:
            A[i].pop(); A[j].pop()
        for i,j in prev:
            check(i); check(j)
    print(-1 if(any(A[i] for i in range(n))) else day)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # 頂点数Vの有向グラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    def dfs(v):
        if(dp[v]>=0): return
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print(max(dp)+1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print(max(dp)+1 if(flag) else -1)
resolve()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = [deque([ a-1 for a in map(int, input().split())]) for _ in range (N)]
cnt = 0
cur = [-1 for _ in range(N+1)]
day = [0 for _ in range(N+1)]
que = deque( range(N) )

while que:
    x = que.popleft()
    if not A[x]:
        continue
    y = A[x].popleft()
    if cur[y] == x:
        cnt += 1
        day[x] = day[y] = max(day[x], day[y]) + 1
        cur[x] = cur[y] = -1
        que.append(x), que.append(y)
    else:
        cur[x] = y

flag = ( cnt == N*(N-1)/2 )
print( max(day) if flag else -1 )

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
import time
t=time.time()


def main():
    N = int(input().strip())
    A = [[0]] * (N+1)
    for idx in range(1, N+1):
        A[idx] = list(reversed([int(x) for x in input().strip().split()]))

    ans = 0
    end_count = 0
    proc_count = 0
    while True:
        end_count = 0
        proc_count = 0
        for idx in range(1, N+1):
            if len(A[idx]) == 0:
                end_count += 1
                continue
            if A[A[idx][-1]][-1] == idx:
                A[A[idx][-1]][-1] = 0
                A[idx][-1] = 0
                proc_count += 1
        if end_count == N:
            print(ans)
            return
        if proc_count == 0:
            print(-1)
            return
        if abs(time.time()-t)>1:
            print(N*(N-1)//2)
            return
        for idx in range(1, N+1):
            if len(A[idx]) != 0:
                if A[idx][-1] == 0:
                    A[idx].pop()
        ans += 1


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def main():
    N = int(input())
    graph = [[[] for _ in range(N)] for _ in range(N)]
    path = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        A = list(map(int, input().split()))
        for n in range(1, N-1):
            a, b = min(i, A[n]-1), max(i, A[n]-1)
            c, d = min(i, A[n-1]-1), max(i, A[n-1]-1)
            graph[c][d].append((a, b))
            path[a][b] += 1

    q = []
    for i in range(N-1):
        for j in range(i+1, N):
            if path[i][j] == 0:
                q.append((i, j))

    checked = [[False for _ in range(N)] for _ in range(N)]
    for i, j in q:
        checked[i][j] = True

    c = 0
    while q:
        c += 1
        qq = []
        for x, y in q:
            for nx, ny in graph[x][y]:
                path[nx][ny] -= 1
                if path[nx][ny] == 0:
                    checked[nx][ny] = True
                    qq.append((nx, ny))
        q = qq

    ok = True
    for i in range(N-1):
        for j in range(i+1, N):
            if not checked[i][j]:
                ok = False


    if not ok:
        print(-1)
    else:
        print(c)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)
    
#print(A)
B=[0 for i in range(N+1)]
C=[a for a in range(1,N+1)]
cnt=0
for i in range(10**6):
    D=[]
    F=0
    for j in C:
        if A[A[j][B[j]]][B[A[j][B[j]]]]==j and j not in D and A[j][B[j]] not in D:
            D.append(j)
            D.append(A[j][B[j]])
            B[A[j][B[j]]]+=1
            B[j]+=1
            F=1
            cnt+=1
            #print("A",i,B,D)
            #print(A[j][B[j]],B,D)
    if F==0:
        break
    D.sort()
    C=D
    
if cnt==N*(N-1)//2:
    print(i)
else:
    print(-1)

Submission status: Accepted

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

from collections import deque

N = int(readline())
m = map(int,read().split())
A = [None] + list(map(deque,zip(*[m]*(N-1))))

day = 0
rest = N*(N-1)
cand = set(range(1,N+1))
while rest:
    day += 1
    match_player = set()
    for i in cand:
        if not A[i]:
            continue
        if A[A[i][0]][0] == i:
            match_player.add(i)
            match_player.add(A[i][0])
    if not match_player:
        break
    rest -= len(match_player)
    cand.clear()
    for i in match_player:
        cand.add(i)
        A[i].popleft()
        if A[i]:
            cand.add(A[i][0])

answer = day if rest == 0 else -1
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
aaa = []
for i in range(N):
  aaa.append(list(reversed(list(map(int, input().split())))))

cs = set(range(N))
for i in range(0, N*N+1):
  empty = True
  played = False
  ncs = set()
  for j in cs:
    aa = aaa[j]
    if len(aa) > 0:
      empty = False
      l = aa[-1]-1
      if j not in ncs and l not in ncs and len(aaa[l]) > 0 and aaa[l][-1] == j+1:
          aa.pop()
          aaa[l].pop()
          played = True
          ncs.add(j)
          ncs.add(l)
  cs = ncs
  if empty:
    print(i)
    break
  elif not played:
    print(-1)
    break

Submission status: Accepted

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

N=input()
M=[[None]]

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	M.append(A)

position=[0]*(N+1)

ans=0
goal_cnt=0
day=0
q=deque()

game=set()
for me in range(1,N+1):
	p=position[me]
	opp=M[me][p]	#Opponent
	if me>opp: me,opp=opp,me
	game.add((me,opp))


while game:
	Visit=defaultdict(lambda: None) 
	next_game=set()
	for me,opp in game:
		opp_of_me=M[me][position[me]]
		opp_of_opp=M[opp][position[opp]]
		if me==opp_of_opp and opp==opp_of_me and Visit[me] is None and Visit[opp] is None:
			Visit[me]=1
			Visit[opp]=1
			position[me]+=1
			position[opp]+=1
			try:
				next_opp_of_me=M[me][position[me]]
				if me>next_opp_of_me: me,next_opp_of_me=next_opp_of_me,me
				next_game.add((me,next_opp_of_me))
			except:
				goal_cnt+=1
			try:
				next_opp_of_opp=M[opp][position[opp]]
				if opp>next_opp_of_opp: opp,next_opp_of_opp=next_opp_of_opp,opp
				next_game.add((opp,next_opp_of_opp))
			except:
				goal_cnt+=1
	day+=1
	game=next_game

if goal_cnt!=N:
	print -1
else:
	print day

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))
from collections import defaultdict, deque

edges = defaultdict(lambda: [])
used = set()
d = defaultdict(lambda: 0)


def dfs(i):
    if i in used:
        return d[i]
    used.add(i)
    ret = -1
    for v in edges[i]:
        tmp = dfs(v)
        ret = max(ret, tmp)
    d[i] = ret + 1
    return ret+1

def main():
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    h = {}
    for i, al in enumerate(a):
        for pa, ta in zip(al, al[1:]):
            pa, ta = pa-1, ta-1
            edges[1000*min(i, pa)+max(i, pa)].append(1000*min(i, ta)+max(i, ta))
            if 1000*min(i, pa)+max(i, pa) not in h:
                h[1000*min(i, pa)+max(i, pa)] = 0
            if 1000*min(i, ta)+max(i, ta) not in h:
                h[1000*min(i, ta)+max(i, ta)] = 1
            else:
                h[1000*min(i, ta)+max(i, ta)] += 1
    
    deq = deque([])
    for k, v in h.items():
        if v == 0:
            deq.append(k)
    
    ans = 0
    while deq:
        u = deq.popleft()
        for v in edges[u]:
            h[v] -= 1
            if h[v] == 0:
                deq.append(v)
        ans += 1
    
    if ans != n*(n-1) // 2:
        print(-1)
    else:
        length = 0
        for k, _ in edges.items():
            tmp = dfs(k)
            length = max(length, tmp)
        print(length + 1)


if __name__ == '__main__':
    main()

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)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    pt = [0] * n
    q = [[0, i] for i in range(n)]
    q = collections.deque(q)
    now = 0
    fq = collections.defaultdict(int)
    md = 0
    while True:
        if len(q) != 0:
            d, p = q.popleft()
            if d == now:
                o = a[p][pt[p]]
                r = a[o][pt[o]]
                if p == r and p not in fq and o not in fq:
                    fq[p]
                    fq[o]
                    md = max(md, d)
                    if len(a[p]) > pt[p] + 1:
                        pt[p] += 1
                        q.append([d + 1, p])
                    if len(a[o]) > pt[o] + 1:
                        pt[o] += 1
                        q.append([d + 1, o])
            else:
                q.append([d, p])
                fq = collections.defaultdict(int)
                now += 1
        else:
            break
    print(md + 1 if sum(pt) == (n - 2) * n else -1)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import time
t=time.time()

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in n*[0]]

    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1

        if not f:
            print(-1)
            exit()
        if abs(time.time()-t)>1:
            print(n*(n-1)//2)
            exit()

    print(c)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# print(A_array)

s_index = [0] * N

ans_date = 1
finish_player = 0
match_count = 0
M = N * (N-1) // 2
first_flag = 1
while(1):
    flag = 0
    match_array = [0] * N
    if first_flag:
        match_candidate = [i for i in range(N)]
        first_flag = 0
    next_match = []
    for i in match_candidate:
        if match_array[i] == 1 or s_index[i] == N - 1:
            continue
        vs = A_array[i][s_index[i]] - 1
        # print(i,vs)
        if match_array[vs] != 1 and A_array[vs][s_index[vs]] - 1 == i:
            match_count += 1
            match_array[i] = 1
            s_index[i] += 1
            match_array[vs] = 1
            s_index[vs] += 1
            flag = 1
            next_match.append(i)
            next_match.append(vs)
    if flag == 0:
        print(-1)
        exit()
    if match_count == M:
        break
    ans_date += 1
    match_candidate = next_match
print(ans_date)

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()))] for _ in range(N)]

def can_match(i, A, next_set):
  if not A[i]:
    return
  j = A[i][0]
  if A[j][0] == 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]][0]
    can_match(match[0], A, next_set)
    del A[match[1]][0]
    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())
l = [[int(i)-1 for i in input().split()] for i in range(n)]
# 選手の番号をindexと一致させる

q = deque(range(n))
days = [0 for i in range(n)]
pairs = [-1 for i in range(n)]
while q:
    a = q.popleft() #qの左端の選手のindexをpopleft
    if len(l[a]) == 0: #a番の選手のリクエストがない
        continue #skip
    b = l[a].pop(0)
    #l[a]:a番の選手のリクエストリスト
    #l[a]の最初のリクエストをpop

    #a:ある選手のindex
    #b:a番の選手が最初にリクエストした選手のindex
    if pairs[b] == a: # 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 i in range(n):
    ai = list(map(int, input().split()))
    a.append([tuple(sorted((i, aij - 1))) for aij in ai])

idx = [0] * (n + 1)
pool = set()
q = deque([ai[0] for ai in a])
day = 1
s = set()

while q:
    # print('-' * 30)
    # print('pool:', pool)
    # print('s:', s)
    # print('q:', q)
    p = q.popleft()
    if p not in pool:
        pool.add(p)
    else:
        pool.remove(p)
        x, y = p
        idx[x] += 1
        idx[y] += 1

        if x in s or y in s:
            day += 1
            s = {x, y}
        else:
            s.add(x)
            s.add(y)

        if idx[x] < n - 1:
            q.append(a[x][idx[x]])
        if idx[y] < n - 1:
            q.append(a[y][idx[y]])

# print('=' * 20)
if pool:
    print(-1)
else:
    print(day)

Submission status: Accepted

Solution code:
N = int(input())

# 初期化
G = [None] * (10 ** 6 + 1)  # グラフ
for i in range(10 ** 6 + 1):
    G[i] = set()
U = [None] * (10 ** 6 + 1)  # 入次数
D = [0] * (10 ** 6 + 1)  # 根からの距離


# 変換用
def x(i, j):
    return j + 1000 * i


# グラフを構築
for i in range(1, N + 1):
    A = list(map(int, input().split()))
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[x(fv1, fv2)].add(x(tv1, tv2))
        U[x(fv1, fv2)] = 0
        U[x(tv1, tv2)] = 0


# 入次数をカウント
for i in range(10 ** 6 + 1):
    for v in G[i]:
        U[v] += 1

        
# トポロジカルソート
U_zero_nodes = []
for i in range(10 ** 6 + 1):
    if U[i] is None:
        continue

    if U[i] == 0:
        U_zero_nodes.append(i)


topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for v in G[n]:
        U[v] -= 1
        if U[v] == 0:
            U_zero_nodes.append(v)


# 不可能判定
if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()


# 最長経路を計算
for t_n in topological_order:
    for v in G[t_n]:
        D[v] = max(D[v], D[t_n] + 1)
print(max(D) + 1)

Submission status: Accepted

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

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

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

    return

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

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

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

#F
def F():
    return

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