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: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
fin = [False] * N
An = [''] * N
q = deque([])
deg = [0] * N
for n in range(N):
    An[n] = [int(x) for x in input().split()]

matched = [False] * N
for n in range(N):
    a = An[n][deg[n]] - 1
    b = An[a][deg[a]] - 1
    if b == n and matched[a] == matched[b] == False:
        set_ = tuple(sorted([a,b]))
        if set_ not in q:
            q.append(set_)
        matched[a] = True
        matched[b] = True

days = 0
while len(q):
    days += 1
    matched = [False] * N
    flag = False
    q_ = list(q)[:]
    q = deque([])
    for a, b in q_:
        if deg[a] < N - 2:
            deg[a] += 1
            c = An[a][deg[a]] - 1
            if matched[c] == False and An[c][deg[c]]-1 == a:
                set_ = tuple(sorted([a, c]))
                q.append(set_)
                matched[c] = True
        else:
            fin[a] = True
        if deg[b] < N - 2:
            deg[b] += 1
            d = An[b][deg[b]] - 1
            if matched[d] == False and An[d][deg[d]]-1 == b:
                set_ = tuple(sorted([b, d]))
                q.append(set_)
                matched[d] = True
        else:
            fin[b] = True

if False in fin:
    days = -1
print(days)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import queue
def sol():
    n=int(input())
    a=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*n]
    b=[[[] for _ in range(n)] for _ in range(n)]
    c=[[[] for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n-2):
            l1=sorted([a[i][j+1],i])
            l2=sorted([a[i][j],i])
            b[l1[0]][l1[1]].append(l2)
            c[l2[0]][l2[1]].append(l1)
    #print('****')
    #print(*a,sep='\n')
    #print('****')
    #print(*b,sep='\n')
    #print('****')
    #print(*c,sep='\n')
    #print('****')
    q=queue.Queue()
    for i in range(n-1):
        for j in range(i+1,n):
            if b[i][j]==[]:
                q.put([i,j])
    if q.empty():print(-1);exit()
    day=1
    q.put([-1,-1])
    cnt=0
    while not q.empty():
        l=q.get()
    #    print(l)
        if l==[-1,-1]:
            if q.empty():
                if cnt<n*(n-1)//2:
                    print(-1)
                else:
                    print(day)
            else:
                day+=1
                q.put([-1,-1])
        else:
            cnt+=1
            for x in c[l[0]][l[1]]:
                b[x[0]][x[1]].remove(l)
                if b[x[0]][x[1]]==[]:
                    q.put(x)
sol()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

n = int(input())
players = [[] for _ in range(n)]


for i in range(n):
    ais = list(map(int,input().split()))
    for ai in ais:
        players[i].append((min(i,ai-1),max(i,ai-1)))


ans = 0
count = 0
while True:
    day = set([])
    count = 0
    passcount=0
    for i in range(n):
        if not players[i]:
            passcount +=1
        elif players[i][0] not in day:
            day |= {players[i][0]}
        else:
            day -= {players[i][0]}
            players[players[i][0][0]].pop(0)
            players[players[i][0][1]].pop(0)
            count +=1
    if passcount==n:
        print(ans)
        exit()
    if count ==0:
        print(-1)
        exit()
    
    ans +=1

Submission status: Time Limit Exceeded

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

c=[0 for i in range(N)]
d=[[] for i in range(N)]
day=0
cnt=0
f=False

while cnt<(N-1)*N//2:
    f=False
    for i in range(N-1):
        if c[i]!=N-1:
            temp=A[i][c[i]]-1  #0base
            if d[i]!=day and d[temp]!=day and A[temp][c[temp]]-1==i:
                c[i]+=1
                d[i]=day
                c[temp]+=1
                d[temp]=day
                cnt+=1
                f=True

    if f==True:
        day+=1
    if f==False:
        print(-1)
        exit()
print(day)

Submission status: Time Limit Exceeded

Solution code:
def sol():
    import queue
    n=int(input())
    a=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*n]
    b=[[[] for _ in range(n)] for _ in range(n)]
    c=[[[] for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n-2):
            l1=sorted([a[i][j+1],i])
            l2=sorted([a[i][j],i])
            b[l1[0]][l1[1]].append(l2)
            c[l2[0]][l2[1]].append(l1)
    #print('****')
    #print(*a,sep='\n')
    #print('****')
    #print(*b,sep='\n')
    #print('****')
    #print(*c,sep='\n')
    #print('****')
    q=queue.Queue()
    for i in range(n-1):
        for j in range(i+1,n):
            if b[i][j]==[]:
                q.put([i,j])
    if q.empty():print(-1);exit()
    day=1
    q.put([-1,-1])
    cnt=0
    while not q.empty():
        l=q.get()
    #    print(l)
        if l==[-1,-1]:
            if q.empty():
                if cnt<n*(n-1)//2:
                    print(-1)
                else:
                    print(day)
            else:
                day+=1
                q.put([-1,-1])
        else:
            cnt+=1
            for x in c[l[0]][l[1]]:
                b[x[0]][x[1]].remove(l)
                if b[x[0]][x[1]]==[]:
                    q.put(x)
sol()

Submission status: Time Limit Exceeded

Solution code:
import queue
n=int(input())
a=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*n]
b=[[[] for _ in range(n)] for _ in range(n)]
c=[[[] for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n-2):
        l1=sorted([a[i][j+1],i])
        l2=sorted([a[i][j],i])
        b[l1[0]][l1[1]].append(l2)
        c[l2[0]][l2[1]].append(l1)
#print('****')
#print(*a,sep='\n')
#print('****')
#print(*b,sep='\n')
#print('****')
#print(*c,sep='\n')
#print('****')
q=queue.Queue()
for i in range(n-1):
    for j in range(i+1,n):
        if b[i][j]==[]:
            q.put([i,j])
if q.empty():print(-1);exit()
day=1
q.put([-1,-1])
cnt=0
while not q.empty():
    l=q.get()
#    print(l)
    if l==[-1,-1]:
        if q.empty():
            if cnt<n*(n-1)//2:
                print(-1)
            else:
                print(day)
        else:
            day+=1
            q.put([-1,-1])
    else:
        cnt+=1
        for x in c[l[0]][l[1]]:
            b[x[0]][x[1]].remove(l)
            if b[x[0]][x[1]]==[]:
                q.put(x)

Submission status: Time Limit Exceeded

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

ans = 0
empty = 0
def is_emp(_i):
    return idx[_i] >= N-1

while 1:
    find = set()
    for i in range(N - 1):
        if is_emp(i): continue

        tmp = A[i][idx[i]]
        if i in find or tmp in find: continue
        if A[tmp][idx[tmp]] == i:
            idx[i] += 1
            idx[tmp] += 1
            find.add(i)
            find.add(tmp)
            empty += is_emp(i)
            empty += is_emp(tmp)

    if not find:
        print(-1)
        exit()
    ans += 1
    if empty >= N:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [None] + [list(map(int, input().split())) for _ in range(n)]
k = 0
l = n * (n - 1)
while(l):
    v = [i for i in range(1, n + 1) if a[i] and a[a[i][-1]] and
         a[a[i][-1]][-1] == i]
    if not v:
        k = -1
        break
    for i in v:
        a[i].pop()
    k += 1
    l -= len(v)
print(k)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(list(map(int, input().split())))
days = 0
l = [0]*N
for _ in range(N*(N-1)//2):
	done = 0
	for i in range(N):
		if l[i] == 0:
			if len(A[i]):
				l[i] = A[i].pop(0)
			else:
				l[i] = 0
 
	if not sum(l): break
 
	for i in range(N):
		if l[l[i]-1] == i+1 and l[i] and l[l[i]-1]:
			l[l[i]-1] = 0
			l[i] = 0
			done = 1
	
	if done:
		days += 1
	else:
		print(-1)
		exit()
print(days)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(list(map(int, input().split())))
days = 0
l = [0]*N
nk = [N-1]*N

while True:
	done = 0
	rdy = 0
	for i in range(N):
		if l[i] == 0:
			if nk[i]:
				l[i] = A[i].pop(0)
				nk[i] -= 1
				rdy = 1
			else:
				l[i] = 0

	if not rdy: break

	for i in range(N):
		p2 = l[i]-1
		if l[p2] == i+1 and l[i] and l[p2]:
			l[p2] = 0
			l[i] = 0
			done = 1
	
	if done:
		days += 1
	else:
		print(-1)
		exit()
print(days)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
	A.append(list(map(int, input().split())))
days = 0
l = [0]*N
while True:
	done = 0
	for i in range(N):
		if l[i] == 0:
			if len(A[i]):
				l[i] = A[i].pop(0)
			else:
				l[i] = 0

	if not sum(l): break

	for i in range(N):
		if l[l[i]-1] == i+1 and l[i] and l[l[i]-1]:
			l[l[i]-1] = 0
			l[i] = 0
			done = 1
	
	if done:
		days += 1
	else:
		print(-1)
		exit()
print(days)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [None] + [list(map(int, input().split())) for _ in range(n)]
k = 0
l = n * (n - 1) // 2
while(l):
    v = [(i, a[i][-1]) for i in range(1, n) if a[i] and a[i][-1] > i
         and a[a[i][-1]] and a[a[i][-1]][-1] == i]
    if not v:
        k = -1
        break
    for i, j in v:
        a[i].pop()
        a[j].pop()
    k += 1
    l -= len(v)
print(k)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = {i for i in range(N)}
    while 1:
        days += 1
        gamed = [0]*N
        tmp = set()
        for i in nxt:
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
                tmp.add(i)
                tmp.add(j)
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break
        nxt = tmp
    print(days)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10**6)

n = int(input())
graph = [list() for _ in range(n**2)]

id_index = [[i+j*n for i in range(n)] for j in range(n)]
index_list = []

max_length = 0

def toId(p, o):
    if p > o:
        index = id_index[o][p]
        index_list.append(index)
        return index
    else: return id_index[p][o]

@lru_cache(maxsize=None)
def dfs(id, length):
    global max_length
    next_list = graph[id]

    if length > len(index_list):
        print(-1)
        sys.exit()

    if len(next_list) == 0:
        max_length = max(length, max_length)
        return
    
    for next in next_list:
        dfs(next, length+1)

for p in range(n):
    a = [toId(p, int(x)-1) for x in input().split()]
    for i in range(n-2):
        graph[a[i]].append(a[i+1])

for id in index_list:
    dfs(id, 1)

print(max_length)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [None] + [list(map(int, input().split())) for _ in range(n)]
k = 0
l = n * (n - 1) // 2
while(l):
    v = [(i, a[i][-1]) for i in range(1, n + 1) if a[i] and a[i][-1] < i
         and a[a[i][-1]] and a[a[i][-1]][-1] == i]
    if not v:
        k = -1
        break
    for i, j in v:
        a[i].pop()
        a[j].pop()
    k += 1
    l -= len(v)
print(k)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
c=0
f = True
for i in range(N):
  A.append(list(map(int, input().split())))
idx = [0 for i in range(N)]

a = 0
cc = 0
ccc = 0

btlf = [False for i in range(N)]
btll = [i for i in range(N)]
m = (N*(N-1))//2
for i in range(10000):
  btlf = [False for i in range(N)]
  ccc = 0
  #print(btll)
  for j in range(N):
    if btll[j]==-1:
      break
    else:
      k = btll[j]
      if idx[k] != N-1:
        a = A[k][idx[k]]
        if A[a-1][idx[a-1]]-1 == k and btlf[a-1] == False and btlf[k] == False:
          idx[a-1]+=1
          btlf[a-1] = True
          idx[k]+=1
          btlf[k] = True
          cc+=1
          ccc+=1
  if cc == m:
    print(i+1)
    f = False
    break
  if ccc == 0:
    break
  d = 0
  #print(btlf)
  for j in range(N):
    if btlf[j]:
      btll[d] = j
      d += 1
  for e in range(d, N):
    btll[d]=-1
    d += 1
if f:
  print(-1)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while 1:
        days += 1
        gamed = [0]*N
        for i in range(N):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]
g = [[[] for _ in range(n)] for _ in range(n)]
h=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(1,n-1):
		maf = max(i,a[i][j-1])
		mif = min(i,a[i][j-1])
		mat = max(i,a[i][j])
		mit = min(i,a[i][j])
		g[mif][maf].append([mit,mat])
		h[mit][mat] += 1

st = deque([])
sj = deque([])
for i in range(n):
	for j in range(i+1,n):
		if h[i][j]==0:
			st.append([i,j])
			sj.append([i,j])
ans=[]
while(st):
	f = st.popleft()
	ans.append(f)
	for mi,ma in g[f[0]][f[1]]:
		h[mi][ma]-=1
		if h[mi][ma] == 0:
			st.append([mi,ma])

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

mac=0
for edge in sj:
	x=edge[0]
	y=edge[1]
	q=deque([[x,y,1]])
	while(q):
		tmp=q.popleft()
		f1=tmp[0]
		f2=tmp[1]
		c=tmp[2]
		mac=max(c,mac)
		for nn in g[f1][f2]:
			q.append([nn[0],nn[1],c+1])
print(mac)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[list(map(lambda x:int(x)-1,input().split())) for _ in range(n)]
g = [[[] for _ in range(n)] for _ in range(n)]
h=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(1,n-1):
		maf = max(i,a[i][j-1])
		mif = min(i,a[i][j-1])
		mat = max(i,a[i][j])
		mit = min(i,a[i][j])
		g[mif][maf].append([mit,mat])
		h[mit][mat] += 1

st = deque([])
for i in range(n):
	for j in range(i+1,n):
		if h[i][j]==0:
			st.append([i,j])
ans=[]
while(st):
	f = st.popleft()
	ans.append(f)
	for mi,ma in g[f[0]][f[1]]:
		h[mi][ma]-=1
		if h[mi][ma] == 0:
			st.append([mi,ma])

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

mac=0
for edge in ans:
	x=edge[0]
	y=edge[1]
	q=deque([[x,y,1]])
	while(q):
		tmp=q.popleft()
		f1=tmp[0]
		f2=tmp[1]
		c=tmp[2]
		mac=max(c,mac)
		for nn in g[f1][f2]:
			q.append([nn[0],nn[1],c+1])
print(mac)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
c=0
f = True
for i in range(N):
  A.append(list(map(int, input().split())))
idx = [0 for i in range(N)]

a = 0

cc = 0

ccc = 0

btlf = [False for i in range(N)]#その周回ですでにバトルしたかどうかのフラグです
btll = range(N)#「前の周回で」バトルした奴らのリストです。便宜上最初は全部。
m = (N*(N-1))//2
for i in range(m):#周回
  btlf = [False for i in range(N)]#リセット
  ccc = 0
  #for j in range(N):
    #print(idx)
  for j in btll:
    if idx[j] != N-1:
      a = A[j][idx[j]]
      if A[a-1][idx[a-1]]-1==j and btlf[a-1] == False and btlf[j] == False:
        idx[a-1]+=1
        btlf[a-1] = True
        idx[j]+=1
        btlf[j] = True
        cc+=1
        ccc+=1
  if cc == m:#idx == [N-1 for i in range(N)]:
    print(i+1)
    f = False
    break
  if ccc == 0:#対戦が一度もなければ打ち切ります
    break
  btll = []
  for j in range(N):
    if btlf[j]:
      btll.append(j)
if f:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
c=0
f = True
for i in range(N):
  A.append(list(map(int, input().split())))
idx = [0 for i in range(N)]

a = 0

cc = 0

ccc = 0

btlf = [False for i in range(N)]#その周回ですでにバトルしたかどうかのフラグです
btll = range(N)#「前の周回で」バトルした奴らのリストです。便宜上最初は全部。
m = (N*(N-1))//2
n = 100000
for i in range(min(m,n)):#周回
  btlf = [False for i in range(N)]#リセット
  ccc = 0
  #for j in range(N):
    #print(idx)
  for j in btll:
    if idx[j] != N-1:
      a = A[j][idx[j]]
      if A[a-1][idx[a-1]]-1==j and btlf[a-1] == False and btlf[j] == False:
        idx[a-1]+=1
        btlf[a-1] = True
        idx[j]+=1
        btlf[j] = True
        cc+=1
        ccc+=1
  if cc == m:#idx == [N-1 for i in range(N)]:
    print(i+1)
    f = False
    break
  if ccc == 0:#対戦が一度もなければ打ち切ります
    break
  btll = []
  for j in range(N):
    if btlf[j]:
      btll.append(j)
if f:
  print(-1)

Submission status: Time Limit Exceeded

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


ans = 0
empty = 0
def is_emp(_i):
    return idx[_i] >= N-1

while 1:
    find_flg = 0
    for i in range(N - 1):
        if is_emp(i): continue

        tmp = A[i][idx[i]]
        if find[i] or find[tmp]: continue
        if A[tmp][idx[tmp]] == i:
            idx[i] += 1
            idx[tmp] += 1
            find[i]+=1
            find[tmp]+=1
            empty += is_emp(i)
            empty += is_emp(tmp)
            find_flg =True

    if not find_flg:
        print(-1)
        exit()
    ans += 1
    if empty >= N:
        break

    for i in range(N):
        find[i]=0
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
empty = 0
def is_emp(_i):
    return idx[_i] >= N-1

while 1:
    find = set()
    for i in range(N - 1):
        if is_emp(i): continue

        tmp = A[i][idx[i]]
        if i in find or tmp in find: continue
        if A[tmp][idx[tmp]] == i:
            idx[i] += 1
            idx[tmp] += 1
            find.add(i)
            find.add(tmp)
            empty += is_emp(i)
            empty += is_emp(tmp)

    if not find:
        print(-1)
        exit()
    ans += 1
    if empty >= N:
        break
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
empty = 0
while 1:
    find = set()
    for i in range(N - 1):
        if not A[i]: continue

        tmp = A[i][0]
        if i in find or tmp in find: continue
        if A[tmp][0] == i:
            A[i].pop(0)
            A[tmp].pop(0)
            find.add(i)
            find.add(tmp)
            empty += int(not A[i])
            empty += int(not A[tmp])

    if not find:
        print(-1)
        exit()
    ans += 1
    if empty >= N:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, *A = map(int, open(0).read().split())
V = N * (N - 1) // 2

serial = [[0 for _ in range(N)] for _ in range(N)]
k = 0
for i in range(N):
    for j in range(i + 1, N):
        serial[i][j] = serial[j][i] = k
        k += 1

G = [[] for _ in range(V)]
deg = [0] * V
for s, a in zip(serial, zip(*[iter(A)] * (N - 1))):
    for j in range(N - 2):
        G[s[a[j] - 1]].append(s[a[j + 1] - 1])
        deg[s[a[j + 1] - 1]] += 1

Q = deque((k, 1) for k, v in enumerate(deg) if v == 0)

ans = 0
cnt = len(Q)
while Q:
    v, ans = Q.popleft()
    for t in G[v]:
        deg[t] -= 1
        if deg[t] == 0:
            Q.append((t, ans + 1))
            cnt += 1

if cnt != V:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def bellman_ford(v, G):
    ret = {g: 10 ** 10 for g in G}
    ret[v] = 0

    for _ in range(len(G) - 1):
        for u, g in G.items():
            for w, l in g:
                if not ret[u] == 10 ** 10 and ret[w] > ret[u] + l:
                    ret[w] = ret[u] + l
    for u, g in G.items():
        for w, l in g:
            if not ret[u] == 10 ** 10 and ret[w] > ret[u] + l:
                print("-1")
                exit()
    return ret


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

G = {}
for i in range(N - 1):
    for j in range(i + 1, N):
        G[(i + 1, j + 1)] = []

for i in range(N):
    for j in range(N - 2):
        src = (min(i + 1, A[i][j]), max(i + 1, A[i][j]))
        dst = (min(i + 1, A[i][j + 1]), max(i + 1, A[i][j + 1]))
        G[src].append((dst, -1))

ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        ans = max(ans, -min(bellman_ford((i + 1, j + 1), G).values()) + 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
es = defaultdict(set)
h = defaultdict(int)
for i, a in enumerate(A):
    for j, k in zip(a, a[1:]):
        a, b = (i, j) if i < j else (j, i)
        c, d = (i, k) if i < k else (k, i)
        if not (c, d) in es[(a, b)]:
            es[(a, b)].add((c, d))
            h[(c, d)] += 1
dq = deque()
for i in range(N-1):
    for j in range(i+1, N):
        if h[(i, j)] == 0:
            dq.append(((i, j), 1))
cnt, day = 0, defaultdict(int)
while len(dq) > 0:
    cnt += 1
    p, d = dq.popleft()
    if d < day[p]:
        continue
    for q in es[p]:
        h[q] -= 1
        if h[q] == 0:
            dq.append((q, d+1))
            day[q] = max(day[q], d+1)
ans = max(day.values()) if cnt == N*(N-1)//2 else -1
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while 1:
        gamed = 0
        for i in range(N-1):
            if (gamed >> i) % 2 or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if (gamed >> j) % 2 or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed += 1<<i
                gamed += 1<<j
                games -= 1
        days += 1
        if not gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

x=[[[] for j in range(n)] for i in range(n)]
y=[[True for j in range(n)] for i in range(n)]

for i in range(n):
	t=[sorted([i,t-1]) for t in a[i]]
	for j in range(1,len(t)):
		k=t[j]
		y[k[0]][k[1]]=False
	#print(t)
	for j in range(n-2):
		x[t[j][0]][t[j][1]].append(t[j+1])
#print(x)
#print(y)


from collections import deque
dis=[[0 for _ in range(n)] for _ in range(n)]
que=deque([])

for i in range(n-1):
	for j in range(i+1,n):
		if y[i][j]:
			que.append((i,j,1))
if len(que)==0:
	print(-1)
	import sys
	sys.exit()
while que:
	tx,ty,td=que.pop()
	dis[tx][ty]=max(dis[tx][ty],td)
	for ttx,tty in x[tx][ty]:
		que.append((ttx,tty,td+1))
	if td==(n*(n-1)//2+2):
		break
res=0
for t in dis:
	res=max(max(t),res)
print(res if res<=n*(n-1)//2 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
es = defaultdict(set)
h = defaultdict(int)
for i, a in enumerate(A):
    for j, k in zip(a, a[1:]):
        a, b = (i, j) if i < j else (j, i)
        c, d = (i, k) if i < k else (k, i)
        if not (c, d) in es[(a, b)]:
            es[(a, b)].add((c, d))
            h[(c, d)] += 1
dq = deque()
for i in range(N-1):
    for j in range(i+1, N):
        if h[(i, j)] == 0:
            dq.append(((i, j), 1))
cnt, day = 0, defaultdict(int)
while len(dq) > 0:
    cnt += 1
    p, d = dq.popleft()
    for q in es[p]:
        h[q] -= 1
        if h[q] == 0:
            dq.append((q, d+1))
            day[q] = max(day[q], d+1)
ans = max(day.values()) if cnt == N*(N-1)//2 else -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, *A = map(int, open(0).read().split())
G = {(i + 1, j + 1): [] for i in range(N) for j in range(i + 1, N)}
deg = {(i + 1, j + 1): 0 for i in range(N) for j in range(i + 1, N)}
for i, a in enumerate(zip(*[iter(A)] * (N - 1)), 1):
    P = ((i, p) if i < p else (p, i) for p in a)
    pre = next(P)
    for cur in P:
        G[pre].append(cur)
        deg[cur] += 1
        pre = cur

Q = deque((k, 1) for k, v in deg.items() if v == 0)

ans = 0
cnt = len(Q)
while Q:
    v, ans = Q.popleft()
    for t in G[v]:
        deg[t] -= 1
        if deg[t] == 0:
            Q.append((t, ans + 1))
            cnt += 1

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

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while 1:
        gamed = [0]*N
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    gamed = [0 for _ in range(N)]
    while 1:
        for i in range(N):
            gamed[i] = 0
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if j < i or gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, *A = map(int, open(0).read().split())
V = N * (N - 1) // 2
G = {(i + 1, j + 1): [] for i in range(N) for j in range(i + 1, N)}
deg = {(i + 1, j + 1): 0 for i in range(N) for j in range(i + 1, N)}
for i, a in enumerate(zip(*[iter(A)] * (N - 1)), 1):
    P = [(i, p) if i < p else (p, i) for p in a]
    for j in range(N - 2):
        G[P[j]].append(P[j + 1])
        deg[P[j + 1]] += 1

Q = deque((k, 1) for k, v in deg.items() if v == 0)

ans = 0
cnt = len(Q)
while Q:
    v, ans = Q.popleft()
    for t in G[v]:
        deg[t] -= 1
        if deg[t] == 0:
            Q.append((t, ans + 1))
            cnt += 1

if cnt != V:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    gamed = [0 for _ in range(N)]
    while 1:
        for i in range(N):
            gamed[i] = 0
            
        for i in range(N-1):
            if gamed[i] or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if gamed[j] or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = gamed[j] = 1
                games -= 1
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 50000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)