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 defaultdict


def input(): return sys.stdin.readline().strip()


def main():
    def dfs(start):
        mx = -1
        s = [(start, set([start]))]

        while s:
            last, visited = s.pop()
            to = graph[last]
            if not to:
                mx = max(len(visited), mx)

            for w in to:
                if w in visited:
                    return -1
                new_visited = visited | {w}
                s.append((w, new_visited))

        return mx

    N = int(input())
    graph = defaultdict(list)
    for i in range(1, N+1):
        Ai = list(map(int, input().split()))
        for j in range(N-2):
            f = tuple(sorted([i, Ai[j]]))
            t = tuple(sorted([i, Ai[j+1]]))
            graph[f].append(t)

    ans = 0
    for k in list(graph.keys()):
        tmp = dfs(k)
        if tmp < 0:
            print(-1)
            return
        else:
            ans = max(tmp, ans)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

allList = []
days = 0

while len(allList) < N:
    allList.append(list(map(int, input().split())))

sum = 100

while sum > 0:
    toBePopped = []
    for i in range(N):
        if allList[i] and i+1 == allList[allList[i][0]-1][0]:
            toBePopped.append(i)
            toBePopped.append(allList[i][0]-1)
    if len(toBePopped) == 0:
        days = -1
        break
    days += 1
    for i in set(toBePopped):
        allList[i].pop(0)

    sum = 0
    for i in range(N):
        sum += len(allList[i])

print(days)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

allList = []
days = 0

while len(allList) < N:
    allList.append(list(map(int, input().split())))

# print(allList)

sum = 0
for i in range(N):
    sum += len(allList[i])


while sum > 0:
    toBePopped = []
    for i in range(N):
        if allList[i] and i+1 == allList[allList[i][0]-1][0]:
            toBePopped.append(i)
            toBePopped.append(allList[i][0]-1)
    if len(toBePopped) == 0:
        days = -1
        break
    days += 1
    for i in set(toBePopped):
        allList[i].pop(0)

    sum = 0
    for i in range(N):
        sum += len(allList[i])

print(days)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_arr = []
for i in range(n):
    a_arr.append(list(map(int,input().split())))
cnt = [0]*n
day = 0
for k in range(n*(n-1)//2 + 1):
    day += 1
    jdg = [0]*n
    for i in range(n):
        if jdg[i] != 0 or cnt[i] == n -1 :
            continue
        tmp = a_arr[i][cnt[i]] - 1 
        if cnt[tmp] < n - 1 and a_arr[tmp][cnt[tmp]] == i + 1 and jdg[tmp] == 0:
            cnt[i] += 1
            cnt[tmp] += 1
            jdg[i] += 1
            jdg[tmp] += 1
    if day > (n-1)*n//2:
        print(-1)
        exit()
    if cnt == [n-1]*n:
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_arr = []
for i in range(n):
    a_arr.append(list(map(int,input().split())))
cnt = [0]*n
day = 0
while (cnt != [n-1]*n):
    day += 1
    jdg = [0]*n
    for i in range(n):
        if jdg[i] != 0 or cnt[i] == n -1 :
            continue
        tmp = a_arr[i][cnt[i]] - 1 
        if cnt[tmp] < n - 1 and a_arr[tmp][cnt[tmp]] == i + 1 and jdg[tmp] == 0:
            cnt[i] += 1
            cnt[tmp] += 1
            jdg[i] += 1
            jdg[tmp] += 1
    if day > (n-1)*n//2:
        print(-1)
        exit()
print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
int_sub = lambda x: int(x)-1
A = [list(map(int_sub,input().split())) for i in range(N)]
stack = [0 for _ in range(N)]
start = [0 for _ in range(N)]

query_nodes = {i for i in range(N)}

while len(query_nodes) != 0:
  skip_node = set()
  delete_node = set()
  end = True
  for i in query_nodes:
    #print(stack,skip_node,i,start,query_nodes)
    if i in skip_node:
      continue
    j = A[i][start[i]]
    if A[j][start[j]] == i and j not in skip_node:
      #print(stack,skip_node,i,start)
      skip_node |= {i,j}
      
      max_end = max(stack[i],stack[j])+1
      stack[i] = max_end
      stack[j] = max_end
      
      start[i] +=1
      start[j] +=1
      
      if start[i] == N-1:
        delete_node |= {i}
      if start[j] == N-1:
        delete_node |= {j}
      end = False
  else:
    query_nodes -= delete_node
  if end:
    print(-1)
    quit()
print(max(stack))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = [ inpl() for _ in range(N) ]

edges = defaultdict(list)
for i in range(N):
    cur_game = None
    for j in range(N-1):
        prev_game = cur_game
        cur_game = (i, A[i][j]-1)
        if cur_game[0] > cur_game[1]:
            cur_game = (cur_game[1], cur_game[0])
        edges[prev_game].append(cur_game)

visited = defaultdict(bool)
dfs_stack = [(0, None)]
depth = 0
ans = 0
history = []
while dfs_stack:
    depth, node = dfs_stack.pop()
    while len(history) > depth:
        visited[history.pop()] = False
    if visited[node]:
        print(-1)
        break
    else:
        visited[node] = True
        history.append(node)
    children = edges[node]
    if children:
        for c in children:
            dfs_stack.append((depth+1, c))
    else:
        if depth > ans:
            ans = depth
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
int_sub = lambda x: int(x)-1
A = [list(map(int_sub,input().split())) for i in range(N)]
stack = [0 for _ in range(N)]
start = [0 for _ in range(N)]

while sum(start) != int(N*(N-1)):
  skip_node = {i for i in range(N) if start[i] == N-1 }
  end = True
  for i in range(N):
    if i in skip_node:
      continue
    j = A[i][start[i]]
    if A[j][start[j]] == i and j not in skip_node:
      #print(stack,skip_node,i,start)
      skip_node |= {i,j}
      
      max_end = max(stack[i],stack[j])+1
      stack[i] = max_end
      stack[j] = max_end
      
      start[i] +=1
      start[j] +=1
      end = False
  if end:
    print(-1)
    quit()
print(max(stack))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():    
    nums = {}
    N = int(input())
    count = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            nums[(i, j)] = count
            count += 1
    
    graph = {i:deque() for i in range(count)}
    input_num = [0] * count
    
    for i in range(1, N+1):
        A = list(map(int, input().split()))
    
        for j in range(N-2):
            a, b = i, A[j]
            if a > b: a, b = b, a
            
            c, d = i, A[j+1]
            if c > d: c, d = d, c
        
            n = nums[(c, d)]        
            graph[nums[(a, b)]].append(n)
            input_num[n] += 1
        
    q = deque([(i, 1) for i in range(count) if not input_num[i]])
    size = len(q)
    dist = [0] * count
    
    while q:
        v, c = q.popleft()
        c += 1
        for u in graph[v]:
            input_num[u] -= 1
            dist[u] = max(dist[u], c)
            if not input_num[u]:
                q.append((u, c))
                size += 1
    
    if size != count: ans = -1
    else: ans = max(dist)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N = INT()
A = [LIST() for i in range(N)]
AA = [[] for i in range(N)]
for i in range(N):
    for j in range(N-1):
        element = A[i][j] 
        new_element = (min(i+1,element),max(i+1,element))
        AA[i].append(new_element)

def has_elements(a):
    answer = False
    for i in range(N):
        if len(a[i]) >0:
            answer = True
    return answer

def match(player_lists):
    match_list = []
    for i in range(N):
        for  j in range(N):
            if i != j and len(player_lists[i]) >0 and len(player_lists[j]) >0:
                if player_lists[i][0] == player_lists[j][0] and player_lists[i][0][0] not in match_list and player_lists[i][0][1] not in match_list:
                    match_list.append(player_lists[i][0][0])
                    match_list.append(player_lists[i][0][1])
                    player_lists[i].pop(0)
                    player_lists[j].pop(0)
    return player_lists, len(match_list)//2

ans = 0
flag = True
while has_elements(AA):
    AA, number = match(AA)
    if number == 0:
        flag = False
        break
    ans +=1

if flag:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = [ inpl() for _ in range(N) ]

edges = defaultdict(set)
for i in range(N):
    cur_game = None
    for j in range(N-1):
        prev_game = cur_game
        cur_game = (i, A[i][j]-1)
        if cur_game[0] > cur_game[1]:
            cur_game = (cur_game[1], cur_game[0])
        edges[prev_game].add(cur_game)

record = defaultdict(int)
visited = defaultdict(lambda: False)
def dfs_depth(node):
    global record, visited
    if record[node] > 0:
        return record[node]
    if edges[node]:
        visited[node] = True
        max_d = 0
        for c in edges[node]:
            if visited[c]:
                print(-1)
                exit()
            d = dfs_depth(c) + 1
            if d > max_d:
                max_d = d
        visited[node] = False
        record[node] = max_d
        return max_d
    else:
        return 0

print(dfs_depth(None))

Submission status: Time Limit Exceeded

Solution code:
import copy
import collections

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

day = 0
empty = [0] * N 
s = [i for i in range(N)]

#whileループ一回を一日と考える
while N==N:
    #print(A)
    q = []
    day +=1
    for i in s:
        #print(A)
        #print(i)
        #i行目が空なら空であることを示すemptyリストを1に
        if len(A[i]) == 0:
            empty[i] = None
        #iが既にqに入っていればパス
        elif i in q:
            pass
        #i行目の末尾の数字で示された相手方が一致していればキューに追加
        elif int(A[int(A[i][0])-1][0]) == i+1:
                #print(i, int(A[i][-1]))
                q.append(i)
                q.append(int(A[i][0])-1)
                s = copy.copy(q)
    #ループ後にqが空ならそれ以上進めないので判定
    if len(q) == 0:
        if not(0 in empty):
            print(day-1)
            exit()
        else:
            print(-1)
            exit()
    
    #そうでなければキューに追加されている行の末尾を削除する
    else:
        for d in q:
            #print(d)
            A[d].popleft()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n = int(input())
a = [deque([int(x)-1 for x in input().split()]) for _ in range(n)]
#print(a)

day = 0
while True:
    tmp = []
    for i in range(n):
        if len(a[i]) != 0 and (i not in tmp) and len(a[a[i][0]]) != 0 and (a[i][0] not in tmp) and a[a[i][0]][0] == i:
            p = a[i].popleft()
            tmp.append(p)
            tmp.append(a[p].popleft())
#    print(tmp)
#    print(a)
    day += 1
    if len(tmp) == 0:
        print('-1')
        exit()
    if max([len(b) for b in a]) == 0:
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [[int(x)-1 for x in input().split()] for _ in range(n)]
#print(a)

day = 0
while True:
    tmp = []
    for i in range(n):
        if len(a[i]) != 0 and (i not in tmp) and len(a[a[i][0]]) != 0 and (a[i][0] not in tmp) and a[a[i][0]][0] == i:
            p = a[i].pop(0)
            tmp.append(p)
            tmp.append(a[p].pop(0))
#    print(tmp)
#    print(a)
    day += 1
    if len(tmp) == 0:
        print('-1')
        exit()
    if max([len(b) for b in a]) == 0:
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
n = int(input().rstrip("\n"))

opposites = {}
for id in range(1, n+1):
  opposites[id] = [int(x) for x in input().rstrip("\n").split(" ")]
ids = list(range(1, n+1))
  
remains = n * (n-1) // 2

day = 0
while remains > 0:
  today_used = {}
  finished_ids = []
  for id in ids:
    if id in today_used:
      continue
    if not opposites[id]:
      continue
    opposite_id = opposites[id][0]
    if opposite_id in today_used:
      continue
    if opposites[opposite_id][0] == id:
      opposites[id].pop(0)
      if not opposites[id]:
        finished_ids.append(id)
      opposites[opposite_id].pop(0)
      if not opposites[opposite_id]:
        finished_ids.append(opposite_id)
      today_used[id] = 1
      today_used[opposite_id] = 1
      remains -= 1
  
  for id in finished_ids:
    ids.remove(id)
  if not today_used:
    break
  #print(day, today_used)
  day += 1

if remains == 0:
  print(day)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input().rstrip("\n"))

opposites = {}
for id in range(1, n+1):
  opposites[id] = [int(x) for x in input().rstrip("\n").split(" ")]

  
remains = n * (n-1) // 2

day = 0
while remains > 0:
  today_used = {}
  
  for id in range(1, n+1):
    if id in today_used:
      continue
    if not opposites[id]:
      continue
    opposite_id = opposites[id][0]
    if opposite_id in today_used:
      continue
    if opposites[opposite_id][0] == id:
      opposites[id].pop(0)
      opposites[opposite_id].pop(0)
      today_used[id] = 1
      today_used[opposite_id] = 1
      remains -= 1
      
  if not today_used:
    break
  #print(day, today_used)
  day += 1

if remains == 0:
  print(day)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

ret = 1
while True:
    pair = []
    for k,v in a.items():
        if v and v[0] in a and a[v[0]][0] == k:
            pair.append(k)
    for p in pair:
        if len(a[p]) > 1:
            a[p] = a[p][1:]
        else:
            a.pop(p)
    if len(a) == 0:
        break
    if len(pair) == 0:
        ret = -1
        break
    ret = ret + 1

print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = deque()

def check(i):
    if len(A[i]) == 0:
        return
    j = A[i][0]
    if len(A[j]) == 0:
        return
    if A[j][0] == i:
        if i > j:
            i, j = j, i
        Q.append([i, j])

def get_unique(q):
    r = deque()
    seen = defaultdict(int)
    for a in q:
        if seen[a[0]] == 0:
            seen[a[0]] = 1
            r.append(a)
    return r


for i in range(N):
    check(i)

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = get_unique(Q)
    Q = deque()
    for q in Q2:
        A[q[0]].popleft()
        A[q[1]].popleft()
    for q in Q2:
        check(q[0])
        check(q[1])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = deque()

def check(i):
    if len(A[i]) == 0:
        return
    j = A[i][0]
    if len(A[j]) == 0:
        return
    if A[j][0] == i:
        if i > j:
            i, j = j, i
        Q.append([i, j])

def get_unique(q):
    r = deque()
    seen = defaultdict(int)
    for a in q:
        key = str(a[0]) + "-" + str(a[1])
        if seen[key] == 0:
            seen[key] = 1
            r.append(a)
    return r


for i in range(N):
    check(i)

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = get_unique(Q)
    Q = deque()
    for q in Q2:
        A[q[0]].popleft()
        A[q[1]].popleft()
    for q in Q2:
        check(q[0])
        check(q[1])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())

def trans(x):
    return int(x)-1

A = deque()
for _ in range(N):
    A.append(deque(map(trans,input().split())))

Q = deque()

def check(i):
    if len(A[i]) == 0:
        return
    j = A[i][0]
    if len(A[j]) == 0:
        return
    if A[j][0] == i:
        if i > j:
            i, j = j, i
        Q.append([i, j])

def get_unique(q):
    r = deque()
    seen = []
    for a in q:
        if a not in seen:
            seen.append(a)
            r.append(a)
    return r


for i in range(N):
    check(i)

ans = 0
while len(Q) > 0:
    ans += 1
    Q2 = get_unique(Q)
    Q = deque()
    for q in Q2:
        A[q[0]].popleft()
        A[q[1]].popleft()
    for q in Q2:
        check(q[0])
        check(q[1])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
a = [[]]
for _ in range(n):
    tmp = [int(x) for x in input().split()]
    a.append(tmp[::-1])

p = [i for i in range(1, n+1)]
c = defaultdict(int)
done = 0
for d in range(1, n*(n-1)//2+1):
    np = []
    for pp in p:
        if len(a[pp]) == 0:
            continue
        x = a[pp].pop()
        l = min(x, pp)
        r = max(x, pp)
        c[l, r] += 1
        if c[l, r] == 2:
            np.append(l)
            np.append(r)
            done += 1
    if done == (n*(n-1)//2):
        print(d)
        exit()
    if len(np) == 0:
        print(-1)
        exit()
    p = np

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A=[]
for j in range(N): 
    A.append([int(i) for i in input().split()])
    
for list in A:
    list.reverse()

day = 0
empty = [0] * N 

#whileループ一回を一日と考える
while N==N:
    #print(A)
    q = []
    day +=1
    for i in range(N):
        #print(A)
        #print(i)
        #i行目が空なら空であることを示すemptyリストを1に
        if len(A[i]) == 0:
            empty[i] = None
        #iが既にqに入っていればパス
        elif i in q:
            pass
        #i行目の末尾の数字で示された相手方が一致していればキューに追加
        elif int(A[int(A[i][-1])-1][-1]) == i+1:
                #print(i, int(A[i][-1]))
                q.append(i)
                q.append(int(A[i][-1])-1)
    #ループ後にqが空ならそれ以上進めないので判定
    if len(q) == 0:
        if not(0 in empty):
            print(day-1)
            exit()
        else:
            print(-1)
            exit()
    #そうでなければキューに追加されている行の末尾を削除する
    else:
        for d in q:
            #print(d)
            A[d].pop(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A=[]
for j in range(N): 
    A.append([int(i) for i in input().split()])
    
for list in A:
    list.reverse()

day = 0
empty = [0] * N 

#whileループ一回を一日と考える
while N==N:
    #print(A)
    q = []
    day +=1
    for i in range(N):
        #print(A)
        #print(i)
        #i行目が空なら空であることを示すemptyリストを1に
        if len(A[i]) == 0:
            empty[i] = 1
        #iが既にqに入っていればパス
        elif i in q:
            pass
        #i行目の末尾の数字で示された相手方が一致していればキューに追加
        elif int(A[int(A[i][-1])-1][-1]) == i+1:
                #print(i, int(A[i][-1]))
                q.append(i)
                q.append(int(A[i][-1])-1)
    #ループ後にqが空ならそれ以上進めないので判定
    if len(q) == 0:
        if sum(empty) == N:
            print(day-1)
            exit()
        else:
            print(-1)
            exit()
    #そうでなければキューに追加されている行の末尾を削除する
    else:
        for d in q:
            #print(d)
            A[d].pop(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
ad = [[] for _ in range(N*N)]
num = [0] * (N*N)

for i in range(N):
    a = [int(e)-1 for e in input().split()]
    for k in range(N-2):
        j = a[k]
        nj = a[k+1]
        v = N*max(i,j) + min(i,j)
        nv = N*max(i,nj) + min(i,nj)
        ad[v].append(nv)
        num[nv] += 1

S = deque()
L = []

for v in range(N*N):
    if num[v] == 0:
        S.append((v,1))

while S:
    v, d = S.popleft()
    L.append(d)
    for nv in ad[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append((nv, d+1))

if len(L) != N*N:
    print(-1)
    exit()

ans = max(L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import deque

N = int(input())
ad = [[] for _ in range(N**2)]
num = [0] * (N**2)
for i in range(N):
    a = [int(e)-1 for e in input().split()]
    for k in range(N-2):
        j = a[k]
        nj = a[k+1]
        ti, tj = min(i, j), max(i, j)
        nti, ntj = min(i, nj), max(i, nj)
        v = N*ti + tj
        nv = N*nti + ntj
        ad[v].append(nv)
        num[nv] += 1

L = []
S = deque()

for v in range(N**2):
    i, j = divmod(v, N)
    if i >= j:
        continue
    if num[v] == 0:
        S.append(v)

while S:
    v = S.popleft()
    L.append(v)
    for nv in ad[v]:
        num[nv] -= 1
        if num[nv] == 0:
            S.append(nv)

if len(L) != N*(N-1)//2:
    print(-1)
    exit()

cand_list = []

def dfs(v):
    res = 1
    for nv in ad[v]:
        res = max(res, dfs(nv) + 1)
    return res

ans = dfs(L[0])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
orders = [] #試合順

for i in range(N):
    orders.append([int(j) for j in input().split()])

next_index = []
for i in range(N):
    next_index.append([0, False])
days = 0
is_possible = True
finished = 0

while finished < N:
    #1day process
    for i in range(1, N+1):
        if next_index[i-1][0] >= N-1:
            continue
        #相手の相手が自分であり、1日の処理をまだしていない場合、対戦処理
        opponent = orders[i-1][next_index[i-1][0]]
        oppo_oppo = orders[opponent-1][next_index[opponent-1][0]]
        if oppo_oppo == i:
            if not (next_index[i-1][1] or next_index[opponent-1][1]):
                ni_i_0 = next_index[i-1][0]
                ni_o_0 = next_index[opponent-1][0]
                ni_i_0 += 1
                ni_o_0 += 1
                next_index.pop(i-1)
                next_index.insert(i-1,[ni_i_0, True])
                next_index.pop(opponent-1)
                next_index.insert(opponent-1, [ni_o_0, True])
                #カンストしたか
                if ni_i_0 >= N-1:
                    finished += 1
                if ni_o_0 >= N-1:
                    finished += 1
    days += 1
    #TrueをFalseに
    for i in range(N):
        ni_i_0 = next_index[i][0]
        next_index.pop(i)
        next_index.insert(i, [ni_i_0, False])

    if days > N * (N-1) // 2:
        is_possible = False
        break

if is_possible:
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
d={}
for i in range(N):
	d[i+1] = list(map(int,input().split()))[::-1]


cnt=0
while True:
	e_num=0
	f=True
	p=[]
	for i in d:
		if d[i]==[]:
			e_num+=1
		else:
		 	j=d[i][-1]
		 	if d[j]!=[] and d[j][-1]==i and (i not in p) and (j not in p): 
		 		d[i].pop()
		 		d[j].pop()
		 		p.append(i)
		 		p.append(j)
		 		f=False
		 		
	if e_num==N:
		print(cnt)
		break
	
	if f:
		print(-1)
		break
	
	cnt+=1

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]

    graph_data = defaultdict(set)
    parent_node = defaultdict(int)

    for i in range(num):
        now_node = i + 1
        pre_tuple = (0, 0)
        for j in range(num - 1):
            next_node = data[i][j]
            now_tuple = (min(now_node, next_node), max(now_node, next_node))
            if j == 0:
                parent_node[now_tuple] += 0
            else:
                graph_data[pre_tuple].add(now_tuple)
                parent_node[now_tuple] += 1
            pre_tuple = now_tuple


    q = deque()
    count_node, ans = 0, 0

    for node, count in parent_node.items():
        if count == 0:
            q.append((node, 1))
            count_node += 1

    while len(q) > 0:
        now_node, length = q.popleft()
        for next_node in graph_data[now_node]:
            parent_node[next_node] -= 1
            if parent_node[next_node] == 0:
                q.append((next_node, length + 1))
                count_node += 1

    if count_node < (num * (num - 1)) // 2:
        print(-1)
    else:
        print(length)







if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
  A.append(list(map(lambda x: int(x) - 1, input().split())))
B = [0]*N
C = [-1]*N
d = 0
f = -1
cnt = 0
max = N * (N-1) // 2
while cnt < max:
  for i in range(N):
    if B[i] >= N - 1 or C[i] == d: continue
    vs = A[i][B[i]]
    if C[vs] == d: continue

    if A[vs][B[vs]] == i:
      B[vs] += 1
      B[i] += 1
      C[vs] = d
      C[i] = d
      cnt += 1
      f = d
  if f != d:
    print (-1)
    break
  d += 1
else:
  print (d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = [deque(int(e)-1 for e in input().split()) for _ in range(N)]

#ad = [[0] * N for _ in range(N)]
game = 0

for d in range(1,N*(N-1)//2+1):
    #print("---------{}日目---------".format(d))
    matched = [0] * N
    for i in range(N):
        if matched[i]:
            continue
        if not A[i]:
            continue
        # 相手の候補
        j = A[i][0]
        if not A[j]:
            continue
        # お互いに最優先で今日中に試合をしていないなら試合をする
        if A[j][0] == i and not matched[j]:
            #print("{}と{}が試合".format(i+1,j+1))
            A[i].popleft()
            A[j].popleft()
            matched[i] = 1
            matched[j] = 1
            #ad[i][j] = 1
            #ad[j][i] = 1
            game += 1
    if game == N*(N-1)//2:
        print(d)
        exit()

print(-1)

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    ans = 0

    while any(len(a[i]) != 0 for i in range(n)):
        ans += 1
        li = [True]*n
        for i in range(n):
            if li[i] and len(a[i]) != 0:
                if li[a[i][0]-1] and a[a[i][0]-1][0]-1 == i:
                    li[i] = False
                    li[a[i][0]-1] = False
                    a[a[i][0]-1].pop(0)
                    a[i].pop(0)
        if all(li[i] for i in range(n)):
            print(-1)
            exit()

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = [deque(int(e)-1 for e in input().split()) for _ in range(N)]

#ad = [[0] * N for _ in range(N)]
game = 0

for d in range(1,N**2+1):
    #print("---------{}日目---------".format(d))
    matched = [0] * N
    for i in range(N):
        if matched[i]:
            continue
        if not A[i]:
            continue
        # 相手の候補
        j = A[i][0]
        if not A[j]:
            continue
        # お互いに最優先で今日中に試合をしていないなら試合をする
        if A[j][0] == i and not matched[j]:
            #print("{}と{}が試合".format(i+1,j+1))
            A[i].popleft()
            A[j].popleft()
            matched[i] = 1
            matched[j] = 1
            #ad[i][j] = 1
            #ad[j][i] = 1
            game += 1
    if game == N*(N-1)//2:
        print(d)
        exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = []
for i in range(N):
  A.append(list(map(lambda x: int(x) - 1, input().split())))
B = [0]*N
C = [-1]*N
d = 0
f = -1
cnt = 0
max = N * (N-1) // 2
while cnt < max:
  for i in range(N):
    if B[i] >= N - 1 or C[i] == d: continue
    vs = A[i][B[i]]
    if C[vs] == d : continue

    if A[vs][B[vs]] == i:
      B[vs] += 1
      B[i] += 1
      C[vs] = d
      C[i] = d
      cnt += 1
      f = d
  else:
    if f != d:
      print (-1)
      break
  d += 1
else:
  print (d)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = []
for i in range(N):
  A.append(list(map(lambda x: int(x) - 1, input().split())))
B = [0 for i in range(N)]
C = [-1 for i in range(N+1)]
d = 0
cnt = 0
max = N * (N-1) // 2
while cnt < max:
  for i in range(N):
    if B[i] >= N - 1: continue
    vs = A[i][B[i]]
    if  C[i] == d or C[vs] == d : continue

    if A[vs][B[vs]] == i:
      B[vs] += 1
      B[i] += 1
      C[vs] = d
      C[i] = d
      C[N] = d
      cnt += 1
      f = True
  else:
    if C[N] != d:
      print (-1)
      break
  d += 1
else:
  print (d)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = []
for i in range(N):
  A.append(list(map(lambda x: int(x) - 1, input().split())))
B = [0 for i in range(N)]
C = [-1 for i in range(N)]
d = 0
cnt = 0
max = N * (N-1) // 2
while cnt < max:
#  f = False
  for i in range(N):
    if B[i] >= N - 1: continue
    vs = A[i][B[i]]
    if  C[i] == d or C[vs] == d : continue

    if A[vs][B[vs]] == i:
      B[vs] += 1
      B[i] += 1
      C[vs] = d
      C[i] = d
      cnt += 1
      f = True
#  if not f: 
#    print (-1)
#    break
  d += 1
else:
  print (d)