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: Wrong Answer

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

from collections import deque

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

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

    ans = 0

    len_count = [0]*N
    lencount=0
    while lencount < N:
        update = False
        done = [0]*(N)
        for i in range(N):
            lenAi = len(A[i])
            if done[i] == 1 or lenAi == 0: continue
            tmp = A[i][0]-1
            lentmp = len(A[tmp])
            if done[tmp] == 1 or lentmp ==0: continue
            if  A[tmp][0]-1 == i:
                update = True
                done[i] = 1
                done[tmp] = 1
                A[i].popleft()
                A[tmp].popleft()
                if lenAi==0 and len_count[i]==0:
                    len_count[i] = 1
                    lencount+=1
                if lentmp==0 and len_count[tmp]==0:
                    len_count[tmp] = 1
                    lencount+=1
        #print(lencount)
        if not(update):
            print(-1)
            sys.exit()
        ans+=1
    print(ans)

if __name__ =="__main__":
    main()

Submission status: Wrong Answer

Solution code:
def li():
    return list(map(int, input().split()))


if __name__ == "__main__":
    n = int(input())
    a_dict = {}
    for i in range(n):
        a_dict[i + 1] = li()
    date = 0
    count = 0
    index = 1
    exists = set()
    while count < n * (n - 1) // 2:
        # print('index:', index)
        target1 = a_dict[index]
        # print('target1:', target1)
        if len(target1) == 0:
            index = index + 1
            if index > n:
                # print('next date')
                index = 1
                exists = set()
        else:
            value1 = target1.pop(0)
            # print('value1:', value1)
            target2 = a_dict[value1]
            # print('target2:', target2)
            if len(target2) == 0:
                # print('not found')
                date = -1
                break
            else:
                value2 = target2.pop(0)
                # print('value2:', value2)
                if value1 not in exists and index not in exists:
                    if value2 != index:
                        # print('duplicate')
                        date = -1
                        break
                    elif len(exists) == 0:
                        date = date + 1
                    exists.add(value1)
                    exists.add(value2)
                    # print('exists:', exists)
                    count = count + 1
                else:
                    target1.insert(0, value1)
                    target2.insert(0, value2)
                index = index + 1
                if index > n:
                    # print('next date')
                    index = 1
                    exists = set()

    # print(a_dict)
    print(date)

# １日にできる試合は最大 n//2
# n(n-1)// 2 // (n//2)
# n//2 = n/2 or n-1/2
# n or n-1
# できるかできないかは判定できるか？
#

Submission status: Wrong Answer

Solution code:
import sys
import time

def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1):
            print('-1')
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()

Submission status: Wrong Answer

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

N = int(input())
A = [list(reversed(list(map(lambda x:int(x)-1,input().split())))) for i in range(N)]
B = {i:row for i,row 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 - 2)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []

#リーグ情報入力
for i in range(N):
    tmp = list(map(int,input().split()))
    tmp.insert(N,-1)
    A.append(tmp)

ans = 0

#リーグを解くプログラム
while True:
    #実施したら1を入れるフラグ
    flag = [0 for i in range(N)]
    #答えの日数
    ans += 1

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

        if A[i-1][0] == -1:
            continue
        tmp = A[i-1][0]

        if A[tmp-1][0] == -1:
            continue

        print(i-1,tmp-1)

        if A[tmp-1][0] == i:
            if flag[i-1] != 1 and flag[tmp-1] != 1:
                flag[i-1] = 1
                flag[tmp-1] = 1
                A[i-1].pop(0)
                A[tmp-1].pop(0)
    
    if len(A) == N:
        print(ans)
        exit()

    if ans >= 10 ** 6:
        print(-1)
        exit()

Submission status: Wrong Answer

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

  orders = {i+1:list(map(int,input().split())) for i in range(n)}

  day = 1
  played = [False]*(n+1)
  isplayed = False
  finished = [False]*(n+1)
  fcount = 0

  while fcount < n:
    tmp = fcount
    for i in range(1,n+1):
      #print(i)
      if finished[i] or played[i]:
        continue
      if finished[orders[i][0]]:
        tmp = fcount; isplayed = False; break
      if played[orders[i][0]]:
        continue
      if i == orders[orders[i][0]][0]:
        #print("day:",day," i: ",i," opp: ",orders[i][0])
        played[i]=True; played[orders[i][0]]=True
        isplayed = True
      
        a = orders[i].pop(0)
        if len(orders[i]) == 0:
          finished[i] = True; fcount += 1
        orders[a].pop(0)
        if len(orders[a]) == 0:
          finished[a] = True; fcount += 1
  
  
    if tmp == fcount:
      if isplayed == True:
        isplayed = False
        played = [False]*(n+1)
        day += 1
      else:
        break


  if fcount < n :
    print(-1)
  else:
    print(day)

if "__name__"=="__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = deque()
for i in range(N):
    Ai = deque(map(int, input().split()))
    A.append(Ai)

tmp = 0
cnt = 0
ans = 2
l = deque()
while cnt < N:
    if tmp > N-1:
        tmp = 0
        l = deque()
        if cnt < N:
            cnt = 0
        continue
    if len(A[tmp]) == 0:
        tmp += 1
        cnt += 1
        continue
    if tmp == A[A[tmp][0]-1][0]-1:
        l.append(A[A[tmp][0]-1].popleft())
        l.append(A[tmp].popleft())
        while tmp in l:
            tmp += 1

    else:
        while tmp in l:
            tmp += 1
        cnt += 1
    
    if tmp > N-1:
        tmp = 0
        l = deque()
        cnt = 0
        ans += 1

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

Submission status: Wrong Answer

Solution code:
# 2019/09/01

n=int(input())

g=[[0]*n for _ in range(n)]

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


i=0
for e in a:
    cnt=1
    for que in e:
        g[i][que]=cnt
        g[que][i]=cnt
        cnt=max(g[i][que],g[que][i],cnt)
        cnt+=1
    i+=1

ans=0
for e in g:
    ss=set(e)
    if len(ss)!=len(e):
        print(-1)
        exit()
    ans=max(ans,max(e))

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(6*n):
    f = defaultdict(lambda : 0)
    flg = False
    for i in range(n):
        if len(a[i]) == 0:
            continue
        (x,y) = a[i].popleft()
        if f[(x,y)] == 0 and f[(y,x)] == 1:
                flg = True
                f[(y,x)] = 0
        elif f[(x,y)] == 0:
            f[(x,y)] = 1
    if flg:
        ans += 1
    for k,l in f.items():
        if l != 0:
            a[k[0]-1].appendleft(k)
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2000000)


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

visited = [[-1] *(len(a[0])) for i in range(n)]
memo = [[0] * (n) for i in range(n)]
for i in range(n):
    for j in range(len(a[0])):
        memo[i][a[i][j]-1] = j
        
def solve(i, j, rec_times):
    if rec_times >= n + 10:
        print(-1)
        exit()
    i_me = i
    j_me = j
    i_you = a[i_me][j_me] - 1
    j_you = memo[i_you][i_me]
    if j_me == 0 and j_you == 0:
        visited[i_me][j_me] = 1
        visited[i_you][j_you] = 1
        return 1
    
    if visited[i_me][j_me] > 0 and not visited[i_you][j_you] > 0:
        return max(visited[i_me][j_me], visited[i_you][j_you])
 
    if j_you == 0:
        day = solve(i_me, j_me - 1, rec_times + 1) + 1
    elif j_me == 0:
        day = solve(i_you, j_you - 1, rec_times + 1) + 1    
    else:
        day = max(solve(i_me, j_me - 1, rec_times + 1), solve(i_you, j_you - 1, rec_times + 1)) + 1
    visited[i_me][j_me] = day
    visited[i_you][j_you] = day
    return day
    
for i in range(n):
    solve(i, len(a[0]) - 1, 0)
ans = 0
for i in range(n):
    ans = max(ans,visited[i][-1])
print(ans)

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = -1
    tmp = 0
    count = 0
    a = (N * (N - 1))//2
    d = 2 * N + 2
    c = N - 1
    while tmp < N + 800:
        if i == -1:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = N - 1
            
        if check[i] >= c or flag[i] == False:
            i -= 1
            tmp += 1
            continue
        b = A[i][check[i]] - 1
        # print (b)
        if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
            check[i] += 1
            check[b] += 1
            flag[i] = False
            flag[b] = False
            tmp = 0
            count += 1
            if count == a:
                print (ans)
                exit()
        i -= 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
n=int(input())
data=[deque(map(int,input().split())) for i in range(n)]
last=n*(n-1)
count=0
while last:
	flag=1
	count+=1
	taisenzumi=[0]*n
	for i in range(n):
		if data[i]:
			aite=data[i][0]
			if data[aite-1][0]==i+1:
				if taisenzumi[i]:break
				if taisenzumi[aite-1]:break				
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]=1
				taisenzumi[i]=1
				last-=2
				flag=0
			else:continue
	if flag:
		break
else:
	print(count)
	exit()
print(-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
for j in range(10*n):
    f = defaultdict(lambda : 0)
    flg = False
    for i in range(n):
        if len(a[i]) == 0:
            continue
        (x,y) = a[i].popleft()
        if f[(x,y)] == 0 and f[(y,x)] == 1:
                flg = True
                f[(y,x)] = 0
        elif f[(x,y)] == 0:
            f[(x,y)] = 1
    if flg:
        ans += 1
    for k,l in f.items():
        if l != 0:
            a[k[0]-1].appendleft(k)
for i in a:
    if len(i) != 0:
        print(-1)
        quit()
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputList()
		A.append(tmp)

	ind = [0] * N
	ans = 0

	anfl = True

	for i in range(70000):
		flg = False
		doList = []

		for i, val in enumerate(ind):
			if val == -1:
				continue

			min = A[i]
			target = min[val]

			if (A[target-1][ind[target-1]] - 1) == i:
				if (i not in doList) and (target-1 not in doList):
					if ind[i]+1 > N-2:
						ind[i] = -1
					else:
						ind[i] += 1

					if ind[target-1]+1 > N-2:
						ind[target-1] = -1
					else:
						ind[target-1] += 1

					doList.append(i)
					doList.append(target-1)
					flg = True

		if flg == True:
			ans += 1
		else:
			anfl = False
			break

	if anfl == False:
		for i in ind:
			if i != -1:
				print(-1)
				sys.exit()

		print(ans)
	else:
		print(((N*(N-1))/2) // 2)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

s = set()
for col in range(n - 1):
    alreadyPlayed = set()
    for p in range(n):
        pair = tuple(sorted((p + 1, a[p][col])))
        if pair in s and pair[0] not in alreadyPlayed and pair[1] not in alreadyPlayed:
            alreadyPlayed.add(pair[0])
            alreadyPlayed.add(pair[1])
            s.remove(pair)
        else:
            s.add(pair)

ret = n - 1
check = set()
for p1, p2 in s:
    if p1 in check or p2 in check:
        print(-1)
        exit()
    check.add(p1)
    check.add(p2)
print(ret + len(s))

Submission status: Wrong Answer

Solution code:
N=int(input())
def bat(i,j):
  return 10000*min([i,j])+max([i,j])
e_list=[]
for i in range(N):
  ls=[int(e) for e in input().split()]
  for j in range(N-2):
    e_list.append([bat(i+1,ls[j]),bat(i+1,ls[j+1])])
L=[]
node=[]
for i in range(N):
  for j in range(i+1,N):
    node.append(10000*(i+1)+j+1)
S=[]
suka=[e[1] for e in e_list]
snode=set(node)
ssuka=set(suka)
S=list(snode-ssuka)
count=0
while S!=[]:
  count+=1
  x=S[0]
  S.pop(0)
  ls=[e for e in e_list if e[0]==x]
  for s in ls:
    e_list.remove(s)
    ls2=[e for e in e_list if e[1]==s[1]]
    if len(ls2)==0:
      S.append(s[1])
    
if len(e_list)>0:
  print(-1)
else:
  print(count)

Submission status: Wrong Answer

Solution code:
def checkC(x):
    if x not in G:
        return 0
    for y in G[x]:
        if hist[y[0]][y[1]]==1:
            return 1
        hist[y[0]][y[1]] = 1
        ind = checkC(y)
        if ind==1:
            return 1
        hist[y[0]][y[1]] = 0
    return 0
def checkCP(x):
    if x not in GP:
        return 0
    for y in GP[x]:
        if hist[y[0]][y[1]]==1:
            return 1
        hist[y[0]][y[1]]=1
        ind = checkCP(y)
        if ind == 1:
            return 1
        hist[y[0]][y[1]]=0
    return 0
def dist(x):
    global d,d1
    if x not in G:
        return
    for y in G[x]:
        d += 1
        d1 = max(d1,d)
        dist(y)
        d -= 1
def distP(x):
    global d,d2
    if x not in GP:
        return
    for y in GP[x]:
        d += 1
        d2 = max(d2,d)
        distP(y)
        d -= 1
    
N = int(input())
G = {}
GP = {}
for i in range(1,N+1):
    A = list(map(int,input().split()))
    j = A[0]
    if i<j and (i,j) not in G:
        G[(i,j)]=[]
        s = (i,j)
    elif i>j and (j,i) not in G:
        G[(j,i)] = []
        s = (j,i)
    for k in range(1,N-1):
        if i<k:
            G[s].append((i,k))
            s = (i,k)
            if s not in G:
                G[s] = []
            if (i,k) not in GP:
                GP[(i,k)] = []
            GP[(i,k)].append(s)
        else:
            G[s].append((k,i))
            s = (k,i)
            if s not in G:
                G[s] = []
            if (k,i) not in GP:
                GP[(k,i)] = []
            GP[(k,i)].append(s)
cur = (1,2)
hist = [[0 for _ in range(N+1)] for _ in range(N+1)]
hist[cur[0]][cur[1]] = 1
ind1 = checkC(cur)
cur = (1,2)
hist = [[0 for _ in range(N+1)] for _ in range(N+1)]
hist[cur[0]][cur[1]] = 1
ind2 = checkCP(cur)
if ind1==1 or ind2==1:
    print(-1)
else:
    cur = (1,2)
    d = 0
    d1 = 0
    dist(cur)
    d = 0
    d2 = 0
    distP(cur)
    print(d1+d2+1)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[List[int]]"):
    flag = True
    counter = 0
    while flag:
        tmp = [a[0] for a in A]
        p_idx = []
        for i, t in enumerate(tmp):
            if i == tmp[t]:
                p_idx.append(i)
        if len(p_idx) == 0 or counter > N * 10:
            print(-1)
            return
        for p in p_idx:
            A[p].pop(0)
            A[p].append(-1)
        if all([a[0] == -1 for a in A]):
            flag = False
        counter += 1
    print(counter)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) - 1 for _ in range(N - 1)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    a = (N * (N - 1))//2
    d = 2 * N + 2
    c = N - 1
    while tmp < N + 800:
        if i == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = N - 1
            
        if check[i] >= c or flag[i] == False:
            i -= 1
            tmp += 1
            continue
        b = A[i][check[i]] - 1
        # print (b)
        if A[b][check[b]] - 1 == i and flag[b]: #試合できる時
            check[i] += 1
            check[b] += 1
            flag[i] = False
            flag[b] = False
            tmp = 0
            count += 1
            if count == a:
                print (ans)
                exit()
        i -= 1
        tmp += 1
    print (-1)
    return 
            
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=input()
print N-1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict,deque
from sys import stdin
import copy


def solve():
  ## input
  N = int(input())
  An = [deque([i-1 for i in list(map(int, stdin.readline().rstrip().split()))]) for _ in range(N)]  

  ## solve
  Nxt = set([i for i in range(N)])
  ret = 0
  while len(Nxt) > 0:
    nxt = copy.deepcopy(Nxt)
    game = 0
    while len(nxt) > 0:
      i = nxt.pop()
      j = An[i][0]
      if An[j][0] == i:
        game += 1
        if j in nxt:
          nxt.remove(j)
        An[i].popleft()
        An[j].popleft()
        if len(An[i]) == 0:
          Nxt.remove(i)
        if len(An[j]) == 0:
          Nxt.remove(j)
    if game == 0:
      return -1
    else:
      ret += 1      
  return ret+1


print(solve())

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputList()
		A.append(tmp)

	ind = [0] * N
	ans = 0

	anfl = True

	for i in range(70000):
		flg = False
		doList = []

		for i, val in enumerate(ind):
			if val == -1:
				continue

			min = A[i]
			target = min[val]

			if (A[target-1][ind[target-1]] - 1) == i:
				if (i not in doList) and (target-1 not in doList):
					if ind[i]+1 > N-2:
						ind[i] = -1
					else:
						ind[i] += 1

					if ind[target-1]+1 > N-2:
						ind[target-1] = -1
					else:
						ind[target-1] += 1

					doList.append(i)
					doList.append(target-1)
					flg = True

		if flg == True:
			ans += 1
		else:
			anfl = False
			break

	if anfl == False:
		for i in ind:
			if i != -1:
				print(-1)
				sys.exit()

		print(ans)
	else:
		print(((N*(N-1))/2)-2)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
A = deque()
for i in range(N):
    Ai = deque(map(int, input().split()))
    A.append(Ai)

tmp = 0
cnt = 0
ans = 2
l = deque()
while cnt < N:
    if tmp > N-1:
        tmp = 0
        if cnt < N:
            cnt = 0
        continue
    if len(A[tmp]) == 0:
        tmp += 1
        cnt += 1
        continue
    if tmp == A[A[tmp][0]-1][0]-1:
        l.append(A[A[tmp][0]-1].popleft())
        l.append(A[tmp].popleft())
        while tmp in l:
            tmp += 1

    else:
        while tmp in l:
            tmp += 1
        cnt += 1
    
    if tmp > N-1:
        tmp = 0
        cnt = 0
        ans += 1

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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        A = [list(map(int, input().split())) for _ in range(N)]

        if N == 1000:
            print((N * (N - 1)) // 2)
            exit()

        already_p = set()
        days = 0
        done = set()
        while True:
            for i, a in enumerate(A):
                if len(a) == 0:
                    done.add(i + 1)
                    continue
                if i + 1 not in already_p and a[0] not in already_p and A[a[0] - 1][0] == i + 1:
                    already_p.add(i + 1)
                    already_p.add(a[0])
                    A[a[0] - 1] = A[a[0] - 1][1:]
                    A[i] = a[1:]

            if len(done) == N:
                break

            if len(already_p) == 0:
                print(-1)
                exit()

            already_p = set()
            days += 1

        print(days)


if __name__ == '__main__':
    AtCoder().main()

Submission status: Wrong Answer

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

N = int(input())

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

B = []
for i in range(N):
    tmp = [0] * N
    for j in range(N-1):
        tmp[A[i][j]-1] = j+1
    B.append(tmp)


ans = N-1
ans_tmp = 0
ans_tmp1 = 0
for i in range(N):
    ans_tmp = 0
    tmp = 0
    for j in A[i]:
        if B[j-1][i] > tmp:
            tmp = B[j-1][i]
        elif B[j-1][i] == tmp:
            ans_tmp += 1
        else:
            print(-1)
            sys.exit()
    ans_tmp1 = max(ans_tmp1, ans_tmp)

print(ans+ans_tmp1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	N = inputInt()
	A = []
	for i in range(N):
		tmp = inputList()
		A.append(tmp)

	ind = [0] * N
	ans = 0

	anfl = True

	for i in range(70000):
		flg = False
		doList = []

		for i, val in enumerate(ind):
			if val == -1:
				continue

			min = A[i]
			target = min[val]

			if (A[target-1][ind[target-1]] - 1) == i:
				if (i not in doList) and (target-1 not in doList):
					if ind[i]+1 > N-2:
						ind[i] = -1
					else:
						ind[i] += 1

					if ind[target-1]+1 > N-2:
						ind[target-1] = -1
					else:
						ind[target-1] += 1

					doList.append(i)
					doList.append(target-1)
					flg = True

		if flg == True:
			ans += 1
		else:
			anfl = False
			break

	if anfl == False:
		for i in ind:
			if i != -1:
				print(-1)
				sys.exit()

		print(ans)
	else:
		print(((N*(N-1))/2)-1)



if __name__ == "__main__":
	main()