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
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')


def sol():
    # トポロジカルソート
    # i 対 jを頂点に持つグラフを考える
    # 簡単のため，i,iから出発する

    def index(i, j):
        return min(i, j) * N + max(i, j)

    N = int(input())


    deg = [0] * (N**2)
    edge = [[] for _ in range(N**2)]
    for i in range(N):
        A = list(map(int, input().split()))
        edge[index(i, i)].append(index(i, A[0] - 1))
        deg[index(i, A[0] - 1)] += 1
        for j in range(N - 2):
            edge[index(i, A[j] - 1)].append(index(i, A[j + 1] - 1))
            deg[index(i, A[j + 1] - 1)] += 1

    S = deque([index(i, i) for i in range(N)])
    L = deque([])

    while S:
        now = S.pop()
        x, y = divmod(now, N)
        if x != y:
            L.append(now)

        for i, to in enumerate(edge[now]):
            if to == -1:
                continue

            edge[now][i] = -1  # 辺を削除
            deg[to] -= 1
            if deg[to] == 0:
                S.append(to)

    for e in edge:
        for to in e:
            if to != -1:
                print('-1')
                return

    ans = 0
    now = 0
    while now < len(L):
        V = set()
        while now < len(L):
            x, y = divmod(L[now], N)
            if x in V or y in V:
                break
            V.add(x)
            V.add(y)
            now += 1
        else:
            now += 1
        ans += 1

    print(ans)

sol()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

def naiseki(a,b):
    if (a[0]*b[0]+a[1]*b[1])/((np.sqrt(b[0]**2+b[1]**2)*np.sqrt(a[0]**2+a[1]**2)))>0.5:
        return True
    else:
        return False
    
ans=0


for i in range(n):
    x=xy[i][0]
    y=xy[i][1]
    for j in range(n):
        if i!=j and naiseki(xy[i],xy[j]):
            x+=xy[j][0]
            y+=xy[j][0]
    ans=max(ans,np.sqrt(x**2+y**2))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = {}
for i in range(N):
  a = [int(i) for i in input().split()]
  dic[i+1] = a[::-1]
count = 0
cp = 0
while True:
  nokori = 0
  flag = True
  log = [-1]*N
  cp = 0
  for k in dic.keys():
    if cp>N//2+1:
      break
    k = int(k)
    cp += 1
    if dic[k]==[]:
      nokori += 1
      continue
    p2 = dic[k][-1]
#    print(k,p2)
    if log[p2-1]==1:
      continue
    if dic[p2]==[]:
      print(-1)
      break
    if dic[p2][-1]==k and log[k-1]==-1 and log[p2-1]==-1:
      a = dic[k].pop()
      b = dic[p2].pop()
#      print('%', a,b)
      log[k-1] = 1
      log[p2-1] = 1
      flag = False
      
  if nokori == N:
    print(count)
    break
  count += 1
  if flag:
    print(-1)
    break

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 >= 1010:
        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:
import heapq

words = lambda t : list(map(lambda x : t(x)-1, input().split()))
n = int(input())

a = []
for i in range(n):
    a.append(words(int))

heap = []
for i in range(n):
    heapq.heappush(heap, (1,i))
cur_day = [1] * n
cur_ind = [0] * n

looping = False
looping_det = (0,0)
suc = True
while len(heap) > 0:
    (d, p) = heapq.heappop(heap)
    if d < cur_day[p]:
        continue
    ind = cur_ind[p]
    oth = a[p][ind]
    if a[oth][cur_ind[oth]] == p:
        looping = False
        play_day = max(cur_day[oth], d)
        cur_day[oth] = play_day+1
        cur_day[p] = play_day+1
        cur_ind[p] += 1
        cur_ind[oth] += 1
        if cur_ind[p] < n-1:
            heapq.heappush(heap, (play_day+1, p))
        if cur_ind[oth] < n-1:
            heapq.heappush(heap, (play_day+1, oth))
    else:
        if looping == True and (d,p) == looping_det:
            suc = False
            break
        if looping != True:
            looping = True
            looping_det = (d+1, p)
        heapq.heappush(heap, (d+1, p))
ans = 0
if suc:
    for i in range(n):
        ans = max(ans, cur_day[i])
    print(ans-1)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = [[] for _ in range(n)]
for i in range(n):
    l[i] = list(map(int,input().split()))
i=0
al = [[] for j in range(3)]
u = [0]*n
d = 0
while True:
    for p in range(n):
        if u[p] == n-1:
            pass
        else:
            v = l[p][u[p]] - 1
            if p == l[v][u[v]]-1:
                u[p]+=1
                u[v]+=1
        for w in range(n):
            if u[w] != n-1:
                break
            else:
                print(max(u)+1)
                exit()
    d+=1
    if d>5000:
        print(-1)
        break

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:
        cnt=max(min(g[i][que],g[que][i]),cnt)
        
        g[i][que]=cnt
        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:
from collections import deque
def f(n):
    return int(n)-1

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

day = 1
matched = [0]*N
n = 0
quit = 1

while n<(N*(N-1))//2 and quit==0:
    day += 1
    matched = [0]*N
    quit = 1
    for n in range(N):
        if A[n]!=deque([]):
            m = A[n][0]
            if A[m]!=deque([]) and A[m][0]==n and matched[m]==0 and matched[n]==0:
                n += 1
                matched[n] = 1
                matched[m] = 1
                A[n].popleft()
                A[m].popleft()
                quit = 0
if n==(N*(N-1))//2:
    print(day)
else:
    print(-1)

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))



if __name__ == "__main__":
	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 - 1)

Submission status: Wrong Answer

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

def index(i, j):
    return min(i, j) * N + max(i, j)

N = int(input())

def sol():
    # トポロジカルソート
    # i 対 jを頂点に持つグラフを考える
    # 簡単のため，i,iから出発する

    deg = [0] * (N**2)
    edge = [[] for _ in range(N**2)]
    for i in range(N):
        A = list(map(int, input().split()))
        edge[index(i, i)].append(index(i, A[0] - 1))
        deg[index(i, A[0] - 1)] += 1
        for j in range(N - 2):
            edge[index(i, A[j] - 1)].append(index(i, A[j + 1] - 1))
            deg[index(i, A[j + 1] - 1)] += 1

    S = deque([index(i, i) for i in range(N)])
    L = deque([])

    while S:
        now = S.pop()
        x, y = divmod(now, N)
        if x != y:
            L.append(now)

        for i, to in enumerate(edge[now]):
            if to == -1:
                continue

            edge[now][i] = -1  # 辺を削除
            deg[to] -= 1
            if deg[to] == 0:
                S.append(to)

    for e in edge:
        for to in e:
            if to != -1:
                print('-1')
                return

    ans = 0
    now = 0
    while now < len(L):
        V = set()
        while now < len(L):
            x, y = divmod(L[now], N)
            if x in V or y in V:
                break
            V.add(x)
            V.add(y)
            now += 1
        else:
            now += 1
        ans += 1

    print(ans)

sol()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input()) # < 1000
D = {}
A = [0] * N
s = set()
path = defaultdict(set)
for A in range(1, N+1):
    l = [int(x) for x in input().split()]
    prev = (0, 0)
    for b in l:
        a = A
        if a > b:
            a, b = b, a
        s.add((a, b))
        path[prev].add((a, b))
        prev = a, b
TMP = 1
DONE = 2
def solve():
    L = []
    status = {}
    def visit(n):
        if status[n] == TMP:
            raise Exception()
        elif status[n] is None:
            status[n] = TMP
            for m in path[n]:
                visit(m)
            status[n] = DONE
            L.append(n)
    
    for p in s:
        status[p] = None
        D[p] = 0
    try:
        for p in s:
            visit(p)
    except:
        return -1
    D[(0, 0)] = 0
    q = [(0, 0)]
    while q:
        u = q.pop()
        for v in path[u]:
            if D[v] < D[u]+1:
                D[v] = D[u]+1
                q.append(v)
    return D[L[0]]

print(solve())

Submission status: Wrong Answer

Solution code:
import sys

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

A.insert(0,[])

day = 0
pop_set = set()

while True:
  day += 1
  empty_judge = True
  pop_set.clear()
  
  for i in range (1,N):
    if A[i]:
      vs = A[i][0]
      if A[vs][0] == i:
        pop_set.add(i)
        pop_set.add(vs)
  if pop_set == set():
    print(-1)
    sys.exit()
  for j in range(len(pop_set)):
    A[list(pop_set)[j]].pop(0)
    
  for k in range(N):
    if A[k]:
      break
    print(day)
    sys.exit()

Submission status: Wrong Answer

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

def main():
	n = int(input().strip())
	dqlist = [0] * (n+1)
	for i in range(n):
		v = list(map(int, input().strip().split()))
		dqlist[i+1] = deque(v)
	day = 0
	zeroc = 0
	for _ in range(10000):
		picked = [0] * (n+1)
		changed = False
		for i in range(1, n+1):
			if picked[i] == 1:
				continue
			if len(dqlist[i]) == 0:
				continue
			if dqlist[dqlist[i][0]][0] == i:
				if picked[dqlist[i][0]] == 1:
					continue
				# OK
				changed = True
				c = dqlist[i].popleft()
				dqlist[c].popleft()
				picked[i] = 1
				picked[c] = 1
				if len(dqlist[i]) == 0:
					zeroc += 1
				if len(dqlist[c]) == 0:
					zeroc += 1
		if changed == False:
			if zeroc == n:
				print(day)
				return
			else:
				print(-1)
				return
		day += 1

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#E問題
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
"""
flag = 0
M = (N*(N+1))//2
for j in range(N-1):
    SUM = 0
    for i in range(N):
        SUM+=A[i][j]
    if SUM == M:
        flag += 1
    else:
        pass
        
if flag >= 2:
    print(-1)
else:
    print(N)

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(50000):
		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)



if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    # A = [list(map(int,input().split())) for _ in range(N)]
    A = []
    next_pos = []
    Apee = A.append
    neapp = next_pos.append
    in_sp = input().split
    for _ in range(N):
        npos, *l = list(map(int,in_sp()))
        neapp(npos)
        Apee(l)
    # next_pos = [A[i].pop(0) for i in range(N)]
    ans = 0
    # check = [0 for _ in range(N)]
    check = [0] * N
    while True:
        end = True
        already = set()
        al_add = already.add
        for i in range(N):
            now = next_pos[i] - 1
            if now == -1:
                continue
            if now in already:
                continue
            if i in already:
                continue

            if i == next_pos[now] - 1:
                if end:
                    end = False
                if A[i]:
                    next_pos[i] = A[i].pop(0)
                else:
                    next_pos[i] = 0
                if A[now]:
                    next_pos[now] = A[now].pop(0)
                else:
                    next_pos[now] = 0
                al_add(i)
                al_add(now)
        ans += 1
        if end:
            ans = -1
            break
        if next_pos == check:
            break
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq

words = lambda t : list(map(lambda x : t(x)-1, input().split()))
n = int(input())

a = []
for i in range(n):
    a.append(words(int))

heap = []
for i in range(n):
    heapq.heappush(heap, (1,i))
cur_day = [1] * n
cur_ind = [0] * n

looping = False
looping_det = (0,0)
while len(heap) > 0:
    (d, p) = heapq.heappop(heap)
    if d < cur_day[p]:
        continue
    ind = cur_ind[p]
    oth = a[p][ind]
    if a[oth][cur_ind[oth]] == p:
        looping = False
        play_day = max(cur_day[oth], d)
        cur_day[oth] = play_day+1
        cur_day[p] = play_day+1
        cur_ind[p] += 1
        cur_ind[oth] += 1
        if cur_ind[p] < n-1:
            heapq.heappush(heap, (play_day+1, p))
        if cur_ind[oth] < n-1:
            heapq.heappush(heap, (play_day+1, oth))
    else:
        if looping == True and (d,p) == looping_det:
            print(-1)
            exit()
        if looping != True:
            looping = True
            looping_det = (d+1, p)
        heapq.heappush(heap, (d+1, p))
ans = 0
for i in range(n):
    ans = max(ans, cur_day[i])
print(ans-1)

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)



if __name__ == "__main__":
	main()

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(3*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
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)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[list(map(int, input().split())) for i in range(N)]
a=0
for _ in range(N*(N-1)//2):
    l=[]
    for i in range(N):
        if A[i]!=None:
            if A[A[i][0]-1][0]==i+1:
                l.append(i)
    if l==[]:
        print(-1)
        break
    else:
        for i in l:
            del A[i][0]
            if A[i]==[]:
                A[i]=None
        a+=1
else:
    print(a)

Submission status: Wrong Answer

Solution code:
n=int(input())
r={}
for i in range(n):
  temp=list(map(int,input().split()))
  r[i+1]=temp
#print(r)

count=1

while 1:
  i=1
  flag=0
  while i<n+1:
    if r[i]!=[]:
      if r[r[i][0]][0]==i:
        flag=1
        r[r[i][0]].remove(i)
        r[i].remove(r[i][0])
        #print(count,r)      
    i+=1
  if flag==1:
    count+=1
  exit1=0
  for item in r:
    if r[item]!=[]:
      exit1=1
  if exit1==0:
    print(count)
    exit()
  
  if flag==0:
    print(-1)
    exit()

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
a=0
while last:
	flag=1
	count+=a
	a=0
	taisenzumi=[0]*n
	for i in range(n):
		if data[i]:
			aite=data[i][0]
			if data[aite-1][0]==i+1:				
				data[i].popleft()
				data[aite-1].popleft()
				taisenzumi[aite-1]+=1
				taisenzumi[i]+=1
				a=max(a,taisenzumi[aite-1],taisenzumi[i])
				last-=2
				flag=0
			else:continue
	if flag:
		break
	# print(a)
else:
	print(count+a)
	exit()
print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import collections
import copy
def input(): return sys.stdin.readline().strip()
N = int(input())
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
chk = 0
for j in range(N*(N-1)//2):
    if j >= 4000:
        chk = 1
        break
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
if chk == 0:
    print(ans)
else:
    print(4950)

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)]

        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
            if days > (N * (N // 10)) // 2:
                print((N * (N - 1)) // 2)
                exit()

        print(days)


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

Submission status: Wrong Answer

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

def index(i, j):
    return min(i, j) * N + max(i, j)

N = int(input())

def sol():
    # トポロジカルソート
    # i 対 jを頂点に持つグラフを考える
    # 簡単のため，i,iから出発する

    deg = [0] * (N**2)
    edge = [[] for _ in range(N**2)]
    for i in range(N):
        A = list(map(int, input().split()))
        edge[index(i, i)].append(index(i, A[0] - 1))
        deg[index(i, A[0] - 1)] += 1
        for j in range(N - 2):
            edge[index(i, A[j] - 1)].append(index(i, A[j + 1] - 1))
            deg[index(i, A[j + 1] - 1)] += 1

    S = deque([index(i, i) for i in range(N)])
    L = deque([])

    while S:
        now = S.pop()
        x, y = divmod(now, N)
        if x != y:
            L.append(now)

        for i, to in enumerate(edge[now]):
            if to == -1:
                continue

            edge[now][i] = -1  # 辺を削除
            deg[to] -= 1
            if deg[to] == 0:
                S.append(to)

    for e in edge:
        for to in e:
            if to != -1:
                print('-1')
                return

    ans = 0
    now = 0
    while now < len(L):
        V = set()
        while now < len(L):
            x, y = divmod(L[now], N)
            if x in V or y in V:
                break
            V.add(x)
            V.add(y)
            now += 1
        ans += 1

    print(ans)

sol()

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:
        cnt=max(g[i][que],g[que][i],cnt)
        g[i][que]=cnt
        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)