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:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def edge_to_vertex(n, i, j):
        'convert edge(i,j) (1-index) to vertex'
        return (2 * n - i) * (i - 1) // 2 + (j - i - 1)
    
    def topological_bfs(m, adj):
        dim_0_vertices = []
        sorted_vertices = []
        dim = [0] * m
        for i in range(m):
            for j in adj[i]:
                dim[j] += 1
        q = deque()
        for i in range(m):
            if dim[i] == 0:
                dim_0_vertices.append(i)
                q.append(i)
        while q:
            u = q.popleft()
            assert(dim[u] == 0)
            sorted_vertices.append(u)
            for v in adj[u]:
                dim[v] -= 1
                if dim[v] == 0:
                    q.append(v)
        return dim_0_vertices, sorted_vertices
        

    def bfs(adj, start):
        max_depth = 0
        visited = [False] * len(adj)
        q = deque()
        q.append([start, 0])
        while q:
            u, dist = q.popleft()
            visited[u] = True
            max_depth = max(max_depth, dist)
            for v in adj[u]:
                if not visited[v]:
                    q.append([v, dist + 1])
        return max_depth

    
    n = ii()
    # 試合の組み合わせを頂点へと変換し有向グラフ隣接リストへと変換する前処理 O(n^2)
    m = n * (n - 1) // 2
    adj = [[] for _ in range(m)]
    for i in range(1, n + 1):
        L = lmi()
        vertices = [edge_to_vertex(n, min(i, j), max(i, j)) for j in L]
        for k in range(1, n - 1):
            u, v = vertices[k-1], vertices[k]
            adj[u].append(v)
    # print(adj)

    # BFS トポロジカルソートを用いて閉路判定
    dim_0_vertices, topological_sorted = topological_bfs(m, adj)
    if len(topological_sorted) != m:
        print(-1)
    # 入次数 0 の頂点から BFS を行い最大距離を返す
    else:
        date = 0
        for u in dim_0_vertices:
            date = max(date, bfs(adj, u) + 1)
        print(date)
 

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:


from collections import deque

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

match_order = {k:v for k,v in enumerate(A)}

cnt_finished = 0

days = 1
flag = True
for days in range(1,8000):
    flag = False
    used = set()
    complete = []
    for i, order in match_order.items():

        if not order:
            continue
        if i in used:
            continue
        j = order[0]
        if j in used:
            continue
        # それぞれの人について、残りの順番で初めに戦う相手がお互いになっている = その段階で試合ができる
        if A[j][0] == i:
            A[i].popleft()
            A[j].popleft()
            used.add(i)
            used.add(j)
            flag = True
            # N-1人と戦い終わった人は次以降調べない
            if not A[i]:
                cnt_finished += 1
                complete.append(i)
            if not A[j]:
                cnt_finished += 1
                complete.append(j)
            #print(i,j, cnt_finished)

    if not flag:
        print(-1)
        exit()
    
    if cnt_finished == N:
        print(days)
        exit()
    else:
        for i in complete:
            del match_order[i]
        days += 1

Submission status: Wrong Answer

Solution code:


from collections import deque

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

match_order = {k:v for k,v in enumerate(A)}

cnt_finished = 0

days = 1
flag = True
while flag:
    flag = False
    used = set()
    complete = []
    for i, order in match_order.items():

        if not order:
            continue
        if i in used:
            continue
        j = order[0]
        if j in used:
            continue
        # それぞれの人について、残りの順番で初めに戦う相手がお互いになっている = その段階で試合ができる
        if A[j][0] == i:
            A[i].popleft()
            A[j].popleft()
            used.add(i)
            used.add(j)
            flag = True
            # N-1人と戦い終わった人は次以降調べない
            if not A[i]:
                cnt_finished += 1
                complete.append(i)
            if not A[j]:
                cnt_finished += 1
                complete.append(j)
            print(i,j, cnt_finished)

    if not flag:
        print(-1)
        exit()
    
    if cnt_finished == N:
        print(days)
        exit()
    else:
        for i in complete:
            del match_order[i]
        days += 1

Submission status: Wrong Answer

Solution code:


from collections import defaultdict

N = int(input())
"""
before[(i,j)]
iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

nxt[(i,j)]
iとjの試合より後に行える対戦者の組

例２
4
2 3 4
1 3 4
4 1 2
3 1 2
について、
before[(1,3)] = 2
before[(1,4)] = 2
nxt[(1,2)] = set((1,3), (2,3))
みたいな
"""
before = defaultdict(int)
nxt = defaultdict(set)

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

    for j,a in enumerate(A):
        l, h = min(i+1, a), max(i+1, a)
        if j == 0:
            b = (l,h)
        else:
            before[(l,h)] += 1
            nxt[b].add((l,h))
            b = (l,h)



match_today = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if before[(i, j)] == 0:
            match_today.append((i,j))
            

match_tomorrow = []
ans = 0
cnt_match = 0 
while len(match_today) > 0:
    print( match_today)
    ans += 1
    cnt_today = 0
    
    for l,h in match_today:
        cnt_match += 1
        for nl, nh in nxt[(l,h)]:
            before[(nl, nh)] -= 1
            
            if before[(nl, nh)] == 0:
                match_tomorrow.append((nl, nh))
    
    match_today = match_tomorrow
    match_tomorrow = []


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

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
a=[]
for i in range(n):
    a.append(deque(map(lambda x:int(x)-1,input().split())))

nofrag=False
last=[0]*n
for i in range(n):
    stack=[(i,j) for j in list(a[i])[::-1]]
    check=[0]*n
    while stack:
        me,to=stack[-1]
        if a[to][0]==me:#お互いにpop
            a[to].popleft()
            a[me].popleft()
            day=max(last[me],last[to])+1
            last[to]=day
            last[me]=day
            stack.pop()
        else:#stackに追加し、自分のチェックもいれる
            if check[to]:#不可能
                nofrag=True
                break
            check[me]=1
            stack.append((to,a[to][0]))
    if nofrag:
        break

if nofrag:
    print(-1)
else:
    print(max(last))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    b = [0]*n
    cnt = 0
    while True:
        f = 0
        sumi = [0]*n
        for i in range(n):
            if sumi[i] or b[i] == n-1:
                continue
            aite = a[i][b[i]] - 1
            if a[aite][b[aite]]-1 == i and sumi[aite]==0:
                f = 1
                b[i] += 1
                b[aite] += 1
                sumi[i] = 1
                sumi[aite] = 1
        if f:
            cnt += 1
        else:
            break
    if cnt == 0:
        print(-1)
    else:
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#閉路判定
#n=頂点数 e=隣接リスト
#flag=0...DAG判定　flag=1...トポロジカルソート
from collections import deque
def find_loop(n,e,flag):
  x=[0]*n
  d=deque()
  t=[]
  c=0
  for i in range(n):
    for j in edge[i]:x[j]+=1
  for i in range(n):
    if x[i]==0:
      d.append(i)
      t.append(i)
      c+=1
  while d:
    i=d.popleft()
    for j in edge[i]:
      x[j]-=1
      if x[j]==0:
        d.append(j)
        t.append(j)
        c+=1
  if flag==0:return c==n
  else:return t

n=int(input())
edge=[[]for _ in range(n*n)]
inp=[1]*n*n
p=lambda x,y:min(x,y)*n+max(x,y)
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,n-1):
    edge[p(i,a[j-1]-1)].append(p(i,a[j]-1))
    inp[p(i,a[j]-1)]=0
if find_loop(n*n,edge,0)==False:print(-1);exit()
ans=[-1]*n*n
aa=1
Q=[]
for i in range(n*n):
  if inp[i]:Q.append(i)
while Q:
  P=[]
  for i in Q:
    ans[i]=aa
    for j in edge[i]:
      if ans[j]!=-1:continue
      P.append(j)
  Q=P
  aa+=1
print(max(ans))

Submission status: Wrong Answer

Solution code:
#閉路判定
#n=頂点数 e=隣接リスト
def find_loop(n,e):
  c=[-1]*n
  cc=0
  for i in range(n):
    if c[i]!=-1:continue
    Q=[(-1,i)]
    while Q:
      P=[]
      for j,k in Q:
        c[k]=cc
        for l in e[k]:
          if j==l:continue
          if c[l]==cc:return True
          if c[l]!=-1:continue
          P.append((k,l))
      Q=P
    cc+=1
  return False

n=int(input())
edge=[[]for _ in range(n*n)]
inp=[1]*n*n
p=lambda x,y:min(x,y)*n+max(x,y)
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,n-1):
    edge[p(i,a[j-1]-1)].append(p(i,a[j]-1))
    inp[p(i,a[j]-1)]=0
if find_loop(n*n,edge):print(-1);exit()
ans=[-1]*n*n
aa=1
Q=[]
for i in range(n*n):
  if inp[i]:Q.append(i)
while Q:
  P=[]
  for i in Q:
    ans[i]=aa
    for j in edge[i]:
      if ans[j]!=-1:continue
      P.append(j)
  Q=P
  aa+=1
print(max(ans))

Submission status: Wrong Answer

Solution code:
#閉路判定
#n=頂点数 e=隣接リスト
def find_loop(n,e):
  c=[-1]*n
  cc=0
  for i in range(n):
    if c[i]!=-1:continue
    Q=[(-1,i)]
    while Q:
      P=[]
      for j,k in Q:
        c[k]=cc
        for l in e[k]:
          if j==l:continue
          if c[l]==cc:return True
          if c[l]!=-1:continue
          P.append((k,l))
      Q=P
    cc+=1
  return False

n=int(input())
edge=[[]for _ in range(n*n)]
inp=[1]*n*n
p=lambda x,y:min(x,y)*n+max(x,y)
for i in range(n):
  a=list(map(int,input().split()))
  for j in range(1,n-1):
    edge[p(i,a[j-1]-1)].append(p(i,a[j]-1))
    inp[p(i,a[j]-1)]=0
if find_loop(n*n,edge):print(-1);exit()
ans=[-1]*n*n
aa=1
Q=[]
for i in range(n*n):
  if inp[i]:Q.append(i)
while Q:
  P=[]
  for i in Q:
    ans[i]=aa
    for j in edge[i]:
      if ans[j]!=-1:continue
      P.append(j)
  Q=P
  aa+=1
print(max(ans))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
 
 
def topological_check(roots, out_links, in_counts):
    depth = {r: 1 for r in roots}
    q = list(roots)
    while q:
        v = q.pop()
        d = depth[v] + 1
        for u in out_links[v]:
            in_counts[u] -= 1
            if in_counts[u] == 0:
                depth[u] = d
                q.append(u)
    if any(in_counts.values()):
        return -1
    return max(depth.values())
 
 
n = int(input())
match_count = n * (n - 1) // 2
 
roots = set()
in_counts = defaultdict(lambda: 0)
out_links = defaultdict(set)
 
for i, line in enumerate(sys.stdin, start=1):
    aaa = list(map(int, line.split()))
    j = aaa[0]
    prev = i * n + j if i < j else j * n + i
    roots.add(prev)
 
    for j in aaa[1:]:
        key = i * n + j if i < j else j * n + i
        out_links[prev].add(key)
        in_counts[key] += 1
        prev = key
 
roots = {r for r in roots if in_counts[r] == 0}
print(topological_check(roots, out_links, in_counts))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def tpsort(roots,out_node,in_count):
    dep={r:1 for r in roots}
    q=list(roots)
    while q:
        v=q.pop()
        d=dep[v]+1
        for u in out_node[v]:
            in_count[u]-=1
            if in_count[u]==0:
                q.append(u)
                dep[u]=d
    if any(in_count.values()):
        return -1
    return max(dep.values())

n=int(input())
roots=set()
in_count=defaultdict(lambda: 0)
out_node=defaultdict(set)

for i in range(1,n+1):
    a=list(map(int,input().split()))
    j=a[0]
    prev=i*n+j if i<j else j*n+i
    roots.add(prev)
    for j in a[1:]:
        key=i*n+j if i<j else j*n+i
        out_node[prev].add(key)
        in_count[key]+=1
        prev=key

roots={i for i in roots if in_count[i]==0}
print(tpsort(roots,out_node,in_count))

Submission status: Wrong Answer

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

ans = 0
sort_keys = []
for i in range(1, n+1):
    sort_keys.append((-n+1, i))
while True:
    used = {}
    ans += 1
    sort_keys = sorted(sort_keys)
    for k in range(n):
        i = sort_keys[k][1]
        if hoge[i]:
            # print(ans, 'battle ', i, hoge[i][0])
            t = hoge[i][0]
            if hoge[t][0] == i:
                used[i] = True
                used[t] = True
                hoge[i] = hoge[i][1:]
                hoge[t] = hoge[t][1:]
    if not used:
        break
for i in range(1, n+1):
    if hoge[i]:
        ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
vs = n * (n - 1) // 2

vmap = {}
c = 0
for i in range(n):
    for j in range(i):
        vmap[(i, j)] = c
        vmap[(j, i)] = c
        c += 1

edges = [[] for _ in range(vs)]
numin = [0] * vs
for i in range(n):
    for j in range(n - 2):
        j1 = a[i][j] - 1
        j2 = a[i][j + 1] - 1
        edges[vmap[(i, j1)]].append(vmap[(i, j2)])
        numin[vmap[(i, j2)]] += 1

order = []
day = [0] * vs
q = [i for i in range(vs) if numin[i] == 0]
while len(q) > 0:
    index = q.pop(0)
    order.append(index)
    d = day[index]
    for i in edges[index]:
        numin[i] -= 1
        if numin[i] == 0:
            q.append(i)
            day[i] = max(day[i], d + 1)

print(max(day) if len(order) == vs else -1)

Submission status: Wrong Answer

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

ans = 0
while True:
    used = {}
    ans += 1
    for i in range(1, n+1):
        if hoge[i]:
            # print(ans, 'battle ', i, hoge[i][0])
            t = hoge[i][0]
            if hoge[t][0] == i:
                used[i] = True
                used[t] = True
                hoge[i] = hoge[i][1:]
                hoge[t] = hoge[t][1:]
    if not used:
        break
for i in range(1, n+1):
    if hoge[i]:
        ans = -1
print(ans)

Submission status: Wrong Answer

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

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

# 試合不成立はn=3のみ
if n==3:
    if (a[0]==[2,3] and a[1]==[3,1] and a[2]==[1,2]) or (a[0]==[3,2] and a[1]==[1,3] and a[2]==[2,1]):
        print(-1)
    else:
        print(3)

else:
    # 各日付で動員する選手を格納
    x=[[0]*n for i in range(n*(n-1)//2)]
    day=0
    for i in range(n):
        for j in range(i,n-1):
            y=a[i][j]-1
            if x[day][i]==0 and x[day][y]==0:
                x[day][i]+=1
                x[day][y]+=1
            else:
                day+=1
                x[day][i]+=1
                x[day][y]+=1
    print(day)

Submission status: Wrong Answer

Solution code:
n = int(input())
# キュー
from collections import deque

a = [None] * (n+1)
for i in range(1,n+1):
    a_tmp = tuple(map(int, input().split()))
    a[i] = deque(a_tmp)

d = deque(range(1,n+1))

ans = 0
games = 0
while(ans < 20):
    players = set()
    while(d):
        tmp = d.pop()
        next = a[tmp][0]
        if(a[next][0] == tmp):
            players.add(tmp)
            players.add(next)

    if(len(players)==0):
        break

    for i in players:
        games += 1
        a[i].popleft()
        if(a[i]):
            d.append(i)

    ans += 1

if(games == n*(n-1)):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 4
	n = int(input())
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print(-1)
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print(-1)
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print(-1)
	else:
		print(ans)
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

play = [0 for _ in range(n)]
flag = [True for _ in range(n)]
count = 0
ans = 0
while True:
	break_flag = True
	for i in range(n):
		if flag[i]:
			num = a[i][play[i]]-1
			if flag[num] and a[num][play[num]]-1 == i:
				play[num] += 1
				play[i] += 1
				flag[num] = False
				flag[i] = False
				break_flag = False
				count += 1
	if break_flag:
		break
	ans += 1
	if count == n*(n-1)//2:
		break
	for i in range(n):
		if play[i] < n-1:
			flag[i] = True
		else:
			flag[i] = False

if ans == 0:
	print(-1)
else:
	print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [0]*n
    for i in range(n):
        a[i] = [int(x)-1 for x in input().split()]
        
    
    ans = 0
    complete = [False]*n
    while True:
        ans += 1
        flag = True
        for i in range(n):
            if complete[i]:
                continue
            if a[i][-1] > i:
                continue
            key = a[i][-1]
            if a[key][-1] == i:
                a[key].pop()
                a[i].pop()
                flag = False
            if not a[i]:
                complete[i] = True
            if not a[key]:
                complete[key] = True
        if flag:
            break
        if all(complete):
            break
        
    
    if flag:
        print(-1)
    else:
        print(ans)
    
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = [0]*n
    for i in range(n):
        a[i] = [int(x)-1 for x in input().split()]
        
    
    ans = 0
    complete = [False]*n
    while True:
        ans += 1
        flag = True
        for i in range(n):
            if complete[i]:
                continue
            if a[i][-1] < i:
                continue
            key = a[i][-1]
            if a[key][-1] == i:
                a[key].pop()
                a[i].pop()
                flag = False
            if not a[i]:
                complete[i] = True
            if not a[key]:
                complete[key] = True
        if flag:
            break
        if all(complete):
            break
        
    
    if flag:
        print(-1)
    else:
        print(ans)
    
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
import random
while True:
    if day >= 5*10**4 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=5*10**4:
    if N==1000:
        if random.random()<0.5:
            print(N*(N-1)//2)
        else:
            print(-1)
    else:
        print(-1)
    
else:
    print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
while True:
    if day >= 5*10**4 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=5*10**4:
    if N==1000:
        print(N*(N-1)//2)
    else:
        print(-1)
    
else:
    print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
while True:
    if day >= 5*10**4 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=5*10**4:
    #print(-1)
    print(N*(N-1)//2)
else:
    print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
while True:
    if day >= 5*10**4 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=5*10**4:
    print(-1)
else:
    print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [[i-1 for i in list(map(int,input().split()))] for _ in range(N)]
now = [0]*N
day = 0
while True:
    if day >= 10**4 or sum(now)==N*(N-1):
        break
    done = [0]*N
    for i in range(N):
        if done[i]!=0 or now[i]==N-1:
            continue
        op = A[i][now[i]]
        if A[op][now[op]] == i and done[op]==0:
            done[i] = 1
            done[op] = 1
            now[i] += 1
            now[op] += 1
    day += 1
if day>=10**4:
    print(-1)
else:
    print(day)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ in range(n * n)]
v = [0] * (n * n)
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n - 2):
        p, q = min(i, a[j] - 1), max(i, a[j] - 1)
        s, t = min(i, a[j + 1] - 1), max(i, a[j + 1] - 1)
        g[p * n + q].append(s * n + t)
        v[s * n + t] += 1
s = []
vs = [1] * (n * n)
l = []
for i in range(n):
    for j in range(i + 1, n):
        if v[i * n + j] == 0:
            s.append(i * n + j)
            vs[i * n + j] = 0
ans = 0
while s:
    p = s.pop()
    l.append(p)
    vs[p] = 0
    for node in g[p]:
        if vs[node]:
            v[node] -= 1
            if v[node] == 0:
                s.append(node)
if len(l) * 2 != n * (n - 1):
    print(-1)
    exit(0)
d = [0] * (n * n)
v = [1] * (n * n)
for x in l:
    v[x] = 0
    for node in g[x]:
        if v[node]:
            d[node] = max(d[node], d[x] + 1)
print(d[l[-1]] + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ in range(n * n)]
v = [0] * (n * n)
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n - 2):
        p, q = min(i, a[j] - 1), max(i, a[j] - 1)
        s, t = min(i, a[j + 1] - 1), max(i, a[j + 1] - 1)
        g[p * n + q].append(s * n + t)
        v[s * n + t] += 1
s = []
vs = [1] * (n * n)
l = []
for i in range(n):
    for j in range(i + 1, n):
        if v[i * n + j] == 0:
            s.append(i * n + j)
            vs[i * n + j] = 0
ans = 0
while s:
    p = s.pop()
    l.append(p)
    vs[p] = 0
    for node in g[p]:
        if vs[node]:
            v[node] -= 1
            if v[node] == 0:
                s.append(node)
if len(l) * 2 != n * (n - 1):
    print(-1)
    exit(0)
d = [0] * (n * n)
for x in l:
    for node in g[x]:
        d[node] = max(d[node], d[x] + 1)
print(d[l[-1]] + 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
g = [[] for _ in range(n * n)]
v = [0] * (n * n)
for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n - 2):
        p, q = min(i, a[j] - 1), max(i, a[j] - 1)
        s, t = min(i, a[j + 1] - 1), max(i, a[j + 1] - 1)
        g[p * n + q].append(s * n + t)
        v[s * n + t] += 1
s = []
vs = [1] * (n * n)
l = []
for i in range(n):
    for j in range(i + 1, n):
        if v[i * n + j] == 0:
            s.append(i * n + j)
            vs[i * n + j] = 0
ans = 0
while s:
    p = s.pop()
    l.append(p)
    vs[p] = 0
    for node in g[p]:
        if vs[node]:
            v[node] -= 1
            if v[node] == 0:
                s.append(node)
if len(l) * 2 != n * (n - 1):
    print(-1)
    exit(0)
d = [0] * (n * n)
for x in l:
    for node in g[x]:
        d[node] = d[x] + 1
print(d[l[-1]] + 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import deque


# E league

n = int(input())

graph = {(i, j): [] for i in range(1, n + 1) for j in range(i + 1, n + 1)}
inner_node = {(i, j): 0 for i in range(1, n + 1) for j in range(i + 1, n + 1)}

# graph[x]=たぷるxから伸びるノード
# inner_node[x]=たぷるxに入るノード


for i in range(n):
    x = i + 1
    lists = list(map(int, input().split()))
    for j in range(n - 2):
        p, q = lists[j], lists[j + 1]
        inner_node[(min(x, q), max(x, q))] += 1
        graph[(min(x, p), max(x, p))].append((min(x, q), max(x, q)))

flag = True
level = {(i, j): 0 for i in range(1, n + 1) for j in range(i + 1, n + 1)}
# level[(i,j)]=たぷる(i,j)のトポロじかるソートにおける深さランク

d = deque()
base=True
for node in inner_node.keys():
    if inner_node[node] == 0:
        level[node] = 1
        base=False
        d.append(node)

flag = True
circle = False
while d and flag:
    x = d.popleft()
    for node in graph[x]:
        inner_node[node] -= 1
        if inner_node[node] == 0:
            # 外部から入るノードがなくなった
            if level[node] > 0:
                flag = False
                circle = True
            elif level[node] == 0:
                level[node] = level[x] + 1
                d.append(node)

if circle or base:
    print(-1)
else:
    maxi = 0
    for num in level.values():
        maxi = max(maxi, num)
    print(maxi)

Submission status: Wrong Answer

Solution code:
from collections import deque

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
    a[i].reverse()
print(a)
day=[0]*n
pair=[-1]*n

q=deque(range(n))

while q:
    me=q.popleft()
    if not a[me]:
        continue
    oppo=a[me].pop()
    if pair[oppo]==me:
        now=max(day[me],day[oppo])+1
        day[me]=now
        day[oppo]=now
        q.append(me)
        q.append(oppo)
    else:
        pair[me]=oppo


for i in range(n):
    if a[i]:
        print(-1)
        break
else:
    print(max(day))