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

#+++++
		
def main():
	n = int(input())
	ggl=lambda : list(map(int, input().split()))
	aal=[ggl() for _ in range(n)]
	
	match_list=[al[0] for al in aal]
	finised_num=[0]*n
	
	ttn=0
	
	dd=0
	while ttn < n*(n-1):
		dd+=1
		pttn = ttn
		ml_next=[0]*n
		
		for i, nm in enumerate(match_list):
			if nm == -1:
				ml_next[i]=match_list[i]
			elif match_list[nm-1]==i+1:
				if finised_num[i] >= n-2:
					ml_next[i]=-1
				else:
					ml_next[i]=aal[i][finised_num[i]+1]
				finised_num[i]+=1
				ttn+=1
			else:
				ml_next[i]=match_list[i]
		match_list=ml_next
		if pttn==ttn:
			return -1
			
	return dd
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

n = int(input())

a = []
for i in range(n):
  v = deque(map(int, input().split(' ')))
  a.append(v)

f = True
day = 1
while(f):
  done = []
  nokori_games = 0
  
  for m in range(n):
    nokori_games += len(a[m])
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].popleft()
        a[teki - 1].popleft()
        done.append(m)
        done.append(teki - 1)
        nokori_games -= 1
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

#+++++
		
def main():
	n = int(input())
	ggl=lambda : list(map(int, input().split()))
	aal=[ggl() for _ in range(n)]
	
	match_list=[al[0] for i, al in enumerate(aal)]
	finised_num=[0 for i in range(n)]
	
	ttn=0
	
	dd=0
	while ttn < n*(n-1):
		dd+=1
		pttn = ttn
		ml_next=[0]*n
		for i, nm in enumerate(match_list):
			if nm == -1:
				ml_next[i]=match_list[i]
			elif match_list[nm-1]==i+1:
				if finised_num[i] >= n-2:
					ml_next[i]=-1
				else:
					ml_next[i]=aal[i][finised_num[i]+1]
				finised_num[i]+=1
				ttn+=1
			else:
				ml_next[i]=match_list[i]
		match_list=ml_next
		if pttn==ttn:
			return -1
	return dd
		
	
	
	
	
#+++++


if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def make(x,y):
    if x<y:
        return (x,y)
    else:
        return (y,x)


n = int(input())

s = set()
r = set()
edge = {}
redge = {}
for x in range(n):
    al = list(map(lambda x:int(x)-1, input().split()))
    s.add(make(x,al[0]))
    for i in range(len(al)-1):
        v = make(x,al[i])
        u = make(x,al[i+1])

        if v not in edge:
            edge[v] = []
        edge[v].append(u)
        if u not in redge:
            redge[u] = set()
        redge[u].add(v)
        r.add(u)

s = s - r

res = 0
while len(s)>0:
    res += 1
    s2 = set()
    for v in s:
        if v not in edge:
            continue
        for u in edge[v]:
            redge[u].remove(v)
            if len(redge[u])==0:
                s2.add(u)
    s = s2

for v in redge:
    if len(redge[v])>0:
        print(-1)
        exit()
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())

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

f = True
day = 1
while(f):
  done = []
  nokori_games = 0
  
  for m in range(n):
    nokori_games += len(a[m])
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.append(m)
        done.append(teki - 1)
        nokori_games -= 1
  if not nokori_games:
    print(day)
    sys.exit()
  else:
    if not len(done):
      print(-1)
      sys.exit()
  day += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())

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

f = True
day = 1
while(f):
  done = []
  nokori = False
  for m in range(n):
    if m in done:
      if not nokori and len(a[m]):
        nokori = True
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.append(m)
        done.append(teki - 1)
        if not nokori and len(a[m]):
          nokori = True
  if not nokori:
    for m in range(n):
      if len(a[m]):
        print(-1)
        sys.exit()
    print(day)
    sys.exit()
  day += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())

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

f = True
day = 1
while(f):
  done = []
  nokori = 0
  for m in range(n):
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.append(m)
        done.append(teki - 1)
      nokori += len(a[m])
  if not nokori:
    for m in range(n):
      if len(a[m]):
        print(-1)
        sys.exit()
    print(day)
    sys.exit()
  day += 1

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())

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

f = True
day = 1
while(f):
  done = []
  nokori = 0
  for m in range(n):
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.append(m)
        done.append(teki - 1)
    nokori += len(a[m])
  if not nokori:
    for m in range(n):
      if len(a[m]):
        print(-1)
        sys.exit()
    print(day)
    sys.exit()
  day += 1

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
def solve(matrix):
    N = len(matrix)
    #print  matrix
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    start = time.time()
    while remaining:
        prev = remaining
        day+=1
        #print "day %d" % day
        #print "matrix: %r" % matrix
        #print "remaining:%d" % remaining
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                #print "%d and %d" % (x, y)
                #print "matrix: %r" % matrix
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                #print 'match: %r' % match
        if time.time() - start > 1.6:
            print worst
            return
        if remaining  == prev:
            print -1
            return
    print day



N = raw_input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in raw_input().split()])
solve(matrix)

Submission status: Time Limit Exceeded

Solution code:
import sys
def solve(matrix):
    N = len(matrix)
    #print  matrix
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    while remaining:
        prev = remaining
        day+=1
        #print "day %d" % day
        #print "matrix: %r" % matrix
        #print "remaining:%d" % remaining
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                #print "%d and %d" % (x, y)
                #print "matrix: %r" % matrix
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                #print 'match: %r' % match
        if remaining  == prev:
            print -1
            return
    print day



N = raw_input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in raw_input().split()])
solve(matrix)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N=int(input())
M=(N*(N-1))//2
D=dict()
tmp=0
X=[(0,0) for i in range(M)]
G=[[] for i in range(M)]
H=[[] for i in range(M)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if i<j:
            D[(i,j)]=tmp
            X[tmp]=(i,j)
            tmp+=1
A=[[int(j) for j in input().split()] for i in range(N)]
for i in range(N):
    for j in range(N-2):
        p1=D[(i+1,A[i][j])] if i+1<A[i][j] else D[(A[i][j],i+1)]
        p2=D[(i+1,A[i][j+1])] if i+1<A[i][j+1] else D[(A[i][j+1],i+1)]
        G[p1].append(p2)
        H[p2].append(p1)
K=[0 for i in range(M)]
for i in range(M):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(M) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
#print(D)
#print(res)
if len(res)<M:
    print(-1)
    exit()
ans=[0 for i in range(M)]
ans[res[-1]]=1
for i in res[:-1][::-1]:
    if len(G[i])==0:
        ans[i]=1
    else:
        for j in G[i]:
            ans[i]=max(ans[i],ans[j]+1)
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def topological_sort(N: int, edges: list) -> list:
    """ トポロジカルソート(頂点数、辺集合(DAG, 0-indexed)) """

    # ここからトポロジカルソート準備
    incnts = [0] * N
    outnodes = [[] for i in range(N)]
    for i in range(len(edges)):
        # 流入するノード数
        incnts[edges[i][1]] += 1
        # 流出先ノードのリスト
        outnodes[edges[i][0]].append(edges[i][1])
    # 流入ノード数が0であるノードのセットS
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)
            # 流入ノード0のノードは始点に出来るので、最長距離を1にしておく
            dist[i] = 1

    # ここからトポロジカルソート
    L = []
    # 暫定セットが空になるまでループ
    while S:
        # 暫定セットから結果リストへ1つ入れる
        L.append(S.pop())
        # 確定させたノードから流出するノードでループ
        for node in outnodes[L[-1]]:
            # 流入ノード数を1減らす
            incnts[node] -= 1
            # 流入ノードが0なら暫定セットへ
            if incnts[node] == 0:
                S.add(node)
    # 閉路があって正しくソート出来なかった場合
    if len(L) != N:
        return []
    # ソートされた頂点のリストを返却
    return L

N = INT()

# 各試合を一意な値とするためのマッピング
mapping = list2d(N, N, -1)
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        mapping[i][j] = cnt
        cnt += 1

A = []
for i in range(N):
    tmp = []
    for a in LIST():
        a -= 1
        a, b = min(a, i), max(a, i)
        # 各試合に一意な値を振って頂点とする
        tmp.append(mapping[a][b])
    A.append(tmp)

# 試合数で作ったグラフの辺集合と隣接リスト
MAXV = N*(N-1)//2
edges = []
nodes = [[] for i in range(MAXV)]
for i in range(N):
    for j in range(1, N-1):
        edges.append((A[i][j-1], A[i][j]))
        nodes[A[i][j-1]].append(A[i][j])

# トポロジカルソート(この時、始点となる頂点は初期値の距離1にして、閉路の検出も行う)
dist = [-1] * MAXV
res = topological_sort(MAXV, edges)
if not len(res):
    print(-1)
    exit()

# 依存性に従って、最長パスを更新していく
for u in res:
    for v in nodes[u]:
        dist[v] = max(dist[v], dist[u]+1)

print(max(dist))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  for i in range(N):
    if b[i]==i+1:
      cnt+=0
    elif i==b[b[i]-1]-1:
      c[i]+=1
  #print('c='+str(c))
  cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()
  for i in range(N):
    b[i]=a[i][c[i]]
  #print('b='+str(b))

print('-1')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def topological_sort(N: int, edges: list) -> list:
    """ トポロジカルソート(頂点数、辺集合(DAG, 0-indexed)) """

    # ここからトポロジカルソート準備
    incnts = [0] * N
    outnodes = [[] for i in range(N)]
    for i in range(len(edges)):
        # 流入するノード数
        incnts[edges[i][1]] += 1
        # 流出先ノードのリスト
        outnodes[edges[i][0]].append(edges[i][1])
    # 流入ノード数が0であるノードのセットS
    S = set()
    for i in range(N):
        if incnts[i] == 0:
            S.add(i)
            # 流入ノード0のノードは始点に出来るので、最長距離を1にしておく
            dist[i] = 1

    # ここからトポロジカルソート
    L = []
    # 暫定セットが空になるまでループ
    while S:
        # 暫定セットから結果リストへ1つ入れる
        L.append(S.pop())
        # 確定させたノードから流出するノードでループ
        for node in outnodes[L[-1]]:
            # 流入ノード数を1減らす
            incnts[node] -= 1
            # 流入ノードが0なら暫定セットへ
            if incnts[node] == 0:
                S.add(node)
    # 閉路があって正しくソート出来なかった場合
    if len(L) != N:
        return []
    # ソートされた頂点のリストを返却
    return L

N = INT()
A = []
for i in range(N):
    tmp = []
    for a in LIST():
        a -= 1
        a, b = min(a, i), max(a, i)
        # 各試合に一意な値を振って頂点とする
        tmp.append(a*N+b)
    A.append(tmp)

# 試合数で作ったグラフの辺集合と隣接リスト
edges = []
nodes = [[] for i in range(N**2)]
for i in range(N):
    for j in range(1, N-1):
        edges.append((A[i][j-1], A[i][j]))
        nodes[A[i][j-1]].append(A[i][j])

# トポロジカルソート(この時、始点となる頂点に初期値の距離1と、閉路の検出も行う)
dist = [-1] * N**2
res = topological_sort(N**2, edges)
if not len(res):
    print(-1)
    exit()

# 依存性に従って、最長パスを更新していく
for u in res:
    for v in nodes[u]:
        dist[v] = max(dist[v], dist[u]+1)

print(max(dist))

Submission status: Time Limit Exceeded

Solution code:
f = 0
def ts(E):
    L = []
    n = len(E)
    done = [0] * n
    checking = [0] * n
    def visit(j):
        global f
        checking[j] = 1
        if done[j] == 0:
            done[j] = 1
            for k in E[j]:
                if f: return 1
                if checking[k]:
                    f = 1
                    return 1
                visit(k)
                D[j] = max(D[j], D[k] + 1)
            L.append(j)
        checking[j] = 0
        return f
    for i in range(n):
        if visit(i):
            return []
    return L[::-1]

def ca(i, j):
    return max(i, j) * (max(i, j)-1) // 2 + min(i, j)

N = int(input())
M = N * (N-1) // 2
X = [[] for i in range(M)]
for i in range(N):
    A = [int(a)-1 for a in input().split()]
    for j in range(N-2):
        X[ca(i, A[j])].append(ca(i, A[j+1]))
D = [0] * M
L = ts(X)
print(max(D) + 1 if L else -1)

Submission status: Time Limit Exceeded

Solution code:
import queue


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = queue.Queue()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.put_nowait(s)
    
    n_days = 0
    n_states_left = max_state
    while today_states.qsize() > 0:
        n_days += 1
        n_today_states = today_states.qsize()
        if n_today_states == 0:
            break
        for _ in range(n_today_states):
            s = today_states.get_nowait()
            n_states_left -= 1
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    today_states.put_nowait(ns)
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = queue.Queue()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.put(s)
    
    n_days = 0
    n_states_left = max_state
    while today_states.qsize() > 0:
        n_days += 1
        n_today_states = today_states.qsize()
        if n_today_states == 0:
            break
        for _ in range(n_today_states):
            s = today_states.get()
            n_states_left -= 1
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    today_states.put(ns)
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    prev_states = [set() for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            prev_states[ns].add(ps)
            next_states[ps].add(ns)
    
    today_states = queue.Queue()
    for s in range(max_state):
        if len(prev_states[s]) == 0:
            today_states.put(s)
    
    n_days = 0
    n_states_left = max_state
    while today_states.qsize() > 0:
        n_days += 1
        n_today_states = today_states.qsize()
        if n_today_states == 0:
            break
        for _ in range(n_today_states):
            s = today_states.get()
            n_states_left -= 1
            for ns in next_states[s]:
                prev_states[ns].remove(s)
                if len(prev_states[ns]) == 0:
                    today_states.put(ns)
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    prev_states = [[] for i in range(max_state)]
    next_states = [[] for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            prev_states[ns].append(ps)
            next_states[ps].append(ns)
    
    today_states = queue.Queue()
    for s in range(max_state):
        if len(prev_states[s]) == 0:
            today_states.put(s)
    
    n_days = 0
    n_states_left = max_state
    while today_states.qsize() > 0:
        n_days += 1
        n_today_states = today_states.qsize()
        if n_today_states == 0:
            break
        for _ in range(n_today_states):
            s = today_states.get()
            n_states_left -= 1
            for ns in next_states[s]:
                prev_states[ns].remove(s)
                if len(prev_states[ns]) == 0:
                    today_states.put(ns)
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])

from collections import deque
Q=deque()

H=[0]*(N-1)**2

for i in range((N-1)**2):
    if E[i]==[] and len(EREV[i])>0:
        Q.append(i)
        H[i]=1

while Q:
    x=Q.pop()

    for fr in EREV[x]:
        if H[fr]<H[x]+1:
            H[fr]=H[x]+1
            if H[fr]>N*N:
                print(-1)
                sys.exit()
            Q.append(fr)
        

if max(H)==0:
    print(-1)
else:
    print(max(H))

Submission status: Time Limit Exceeded

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

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])

from collections import deque
Q=deque()

H=[0]*(N-1)**2

for i in range((N-1)**2):
    if E[i]==[] and len(EREV[i])>0:
        Q.append(i)
        H[i]=1

while Q:
    x=Q.pop()

    for fr in EREV[x]:
        H[fr]=max(H[x]+1,H[fr])
        if H[fr]>N*N:
            print(-1)
            sys.exit()
        Q.append(fr)
        

if max(H)==0:
    print(-1)
else:
    print(max(H))

Submission status: Time Limit Exceeded

Solution code:
import queue


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    prev_states = [[] for i in range(max_state)]
    next_states = [[] for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            prev_states[ns].append(ps)
            next_states[ps].append(ns)
    
    n_days = 0
    active_states = set(range(max_state))
    q = queue.Queue()
    while len(active_states) > 0:
        n_days += 1
        for s in active_states:
            if len(prev_states[s]) == 0:
                q.put(s)
        if q.empty():
            return -1
        while not q.empty():
            s = q.get()
            for ns in next_states[s]:
                prev_states[ns].remove(s)
            active_states.remove(s)
    return n_days


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[set() for i in range(N*N)]
EREV=[set() for i in range(N*N)]

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].add(A[i][j])
        EREV[A[i][j]].add(A[i][j-1])

from collections import deque
Q=deque()

H=[0]*N*N

for i in range(N*N):
    if E[i]==set() and len(EREV[i])>0:
        Q.append(i)
        H[i]=1

while Q:
    x=Q.pop()

    for fr in EREV[x]:
        H[fr]=max(H[x]+1,H[fr])
        if H[fr]>N*N:
            print(-1)
            sys.exit()
        Q.append(fr)
        

if max(H)==0:
    print(-1)
else:
    print(max(H))

Submission status: Time Limit Exceeded

Solution code:
import queue


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    prev_states = [[] for i in range(max_state)]
    next_states = [[] for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            prev_states[ns].append(ps)
            next_states[ps].append(ns)
    
    n_days = 0
    visited = [False for i in range(max_state)]
    q = queue.Queue()
    while not all(visited):
        n_days += 1
        for s in range(max_state):
            if not visited[s] and len(prev_states[s]) == 0:
                q.put(s)
        if q.empty():
            return -1
        while not q.empty():
            s = q.get()
            for ns in next_states[s]:
                prev_states[ns].remove(s)
            visited[s] = True
    return n_days


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
match_players = {i: deque([int(x)-1 for x in input().split()]) for i in range(n)}

res = -1
daycnt = 0
isdones = [False] * n
while True:
  daycnt += 1
  played_idxs = []
  is_matched = False
  for i in range(n):
    if i in played_idxs:
      continue
    if isdones[i]:
      continue
    target_idx = match_players[i][0]
    if target_idx in played_idxs:
      continue
    if match_players[target_idx][0] != i:
      continue
    is_matched = True
    played_idxs.append(target_idx)
    played_idxs.append(i)
    match_players[i].popleft()
    if len(match_players[i]) == 0:
      isdones[i] = True
    match_players[target_idx].popleft()
    if len(match_players[target_idx]) == 0:
      isdones[target_idx] = True
  if all(isdones):
    res = daycnt
    break
  if is_matched is False:
    res = -1
    break

print(res)

Submission status: Time Limit Exceeded

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

from queue import PriorityQueue
pq = PriorityQueue()
pq.put((0, a))
while not pq.empty():
  p, a = pq.get()
  if sum([len(ai) for ai in a]) == 0:
    print(p)
    break
  flag = False
  m = []
  for i, ai in enumerate(a):
    if not (ai and a[ai[0]]):
      continue
    if i == a[ai[0]][0]:
      m.extend([i, ai[0]])
  if m:
    pq.put((
      p+1, tuple([
        aj[1:] if j in m else aj
        for j, aj in enumerate(a)
      ])
    ))
  else:
    print(-1)
    break