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:
n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))

day = 0
player_cnt = [0 for i in range(n)]
end_list = [[] for i in range(n)]
while a != end_list:
    player_flg = [0 for i in range(n)]
    for i in range(n):
        if not a[i]:
            continue
        if a[a[i][0] - 1][0] == i + 1 and player_flg[i] == 0 and player_flg[a[i][0] - 1] == 0:
            tmp_num = a[i].pop(0)
            player_flg[i] += 1
            player_cnt[i] += 1
            a[tmp_num - 1].pop(0)
            player_flg[tmp_num - 1] += 1
            player_cnt[tmp_num - 1] += 1
    day += 1
    if player_flg == [0 for i in range(n)]:
        day = -1
        break
print(day)

Submission status: Time Limit Exceeded

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

day = 0
player_cnt = [0 for i in range(n)]
end_list = [[] for i in range(n)]
while a != end_list:
    player_flg = [0 for i in range(n)]
    for i in range(n):
        if not a[i]:
            continue
        if a[a[i][0] - 1][0] == i + 1 and player_flg[i] == 0 and player_flg[a[i][0] - 1] == 0:
            tmp_num = a[i].pop(0)
            player_flg[i] += 1
            player_cnt[i] += 1
            a[tmp_num - 1].pop(0)
            player_flg[tmp_num - 1] += 1
            player_cnt[tmp_num - 1] += 1
    day += 1
    if day > 500000:
        day = -1
        break
print(day)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import copy
def f(n):
    return int(n)-1

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

day = 0
zeros = deque([0]*N)
matched = copy(zeros)
k = 0

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def f(n):
    return int(n)-1

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

day = 0
zeros = [0]*N
matched = deque(zeros)
k = 0

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def f(n):
    return int(n)-1

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

day = 0
matched = deque([0]*N)
k = 0

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

Submission status: Time Limit Exceeded

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

n = int(input())

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]

day_count = 0
remained_battles = (n * (n - 1)) // 2

while remained_battles:
    battled_today = set()

    no_battle_today = True
    for player in range(n):
        if not to_battle_with[player]:
            continue

        next_opponent = to_battle_with[player][0]
        if player in battled_today or next_opponent in battled_today:
            continue

        if not to_battle_with[next_opponent]:
            continue

        if to_battle_with[next_opponent][0] == player:
            battled_today.add(next_opponent)
            battled_today.add(player)
            to_battle_with[player].popleft()
            to_battle_with[next_opponent].popleft()
            remained_battles -= 1
            no_battle_today = False
    if no_battle_today:
        print(-1)
        break
    day_count += 1

if not no_battle_today:
    print(day_count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]

day_count = 0
remained_battles = (n * (n - 1)) // 2

while remained_battles:
    battled_today = set()

    no_battle_today = True
    for player in range(n):
        if not to_battle_with[player]:
            continue

        next_opponent = to_battle_with[player][0]
        if player in battled_today or next_opponent in battled_today:
            continue

        if not to_battle_with[next_opponent]:
            continue

        if to_battle_with[next_opponent][0] == player:
            battled_today.add(next_opponent)
            battled_today.add(player)
            to_battle_with[player].popleft()
            to_battle_with[next_opponent].popleft()
            remained_battles -= 1
            no_battle_today = False
    if no_battle_today:
        print(-1)
        break
    day_count += 1

if not no_battle_today:
    print(day_count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def f(n):
    return int(n)-1

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

day = 0
matched = [0]*N
k = 0

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())

to_battle_with = [deque(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(n - 1):
        to_battle_with[i][j] -= 1

day_count = 0
remained_battles = (n * (n - 1)) // 2

while remained_battles:
    battled_today = set()

    no_battle_today = True
    for player in range(n):
        if not to_battle_with[player]:
            continue

        next_opponent = to_battle_with[player][0]
        if player in battled_today or next_opponent in battled_today:
            continue

        if not to_battle_with[next_opponent]:
            continue

        if to_battle_with[next_opponent][0] == player:
            battled_today.add(next_opponent)
            battled_today.add(player)
            to_battle_with[player].popleft()
            to_battle_with[next_opponent].popleft()
            remained_battles -= 1
            no_battle_today = False
    if no_battle_today:
        print(-1)
        break
    day_count += 1

if not no_battle_today:
    print(day_count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

for i in range(n):
    for j in range(n - 1):
        to_battle_with[i][j] -= 1

day_count = 0
remained_battles = (n * (n - 1)) // 2

while remained_battles:
    battled_today = set()

    no_battle_today = True
    for player in range(n):
        if not to_battle_with[player]:
            continue

        next_opponent = to_battle_with[player][0]
        if player in battled_today or next_opponent in battled_today:
            continue

        if not to_battle_with[next_opponent]:
            continue

        if to_battle_with[next_opponent][0] == player:
            battled_today.add(next_opponent)
            battled_today.add(player)
            to_battle_with[player].pop(0)
            to_battle_with[next_opponent].pop(0)
            remained_battles -= 1
            no_battle_today = False
    if no_battle_today:
        print(-1)
        break
    day_count += 1

if not no_battle_today:
    print(day_count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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


def func(i, matches):
    if len(A[i]) == 0:
        return

    # index
    opponent = A[i][0]

    if A[opponent - 1][0] == i + 1:
        if i + 1 < opponent:
            matches.add((i + 1 , opponent))
        else:
            matches.add((opponent, i + 1))

    return


# initialize
matches = set()
for i in range(N):
    func(i, matches)

cnt = 0
while matches:
    for i, j in matches:
        A[i - 1].popleft()
        A[j - 1].popleft()

    cnt += 1

    matches = set()

    for i in range(N):
        func(i, matches)


for d in A:
    if len(d) != 0:
        print(-1)
        exit()

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def list_up_next_games(players):
    games = set()
    for p in players:
        if A[p]:
            opponent = A[p][-1] - 1
            if A[opponent][-1] - 1 == p:
                if p < opponent:
                    games.add((p, opponent))
                else:
                    games.add((opponent, p))
    return(set(games))


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

remain_games = []
for i in range(N):
    for j in range(i+1,N):
        remain_games.append((i,j))

games = list_up_next_games(list(range(N)))

days = 0
while games:
    days += 1
    players = []
    for game in games:
        remain_games.remove(game)
        A[game[0]].pop()
        A[game[1]].pop()
        players.append(game[0])
        players.append(game[1])
    games = list_up_next_games(players)
if remain_games:
    print(-1)
else:
    print(days)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
to = [[] for _ in range(MAXV)] # 頂点間の辺の情報
id = [[[] for _ in range(MAXN)] for _ in range(MAXN)] # 試合のid=DAGの頂点番号
def toId(i,j): # 選手idから試合idを返す関数
    if i > j: # i,jが逆になっても試合idは同じ
        i,j = j,i
    return id[i][j]

visited = [False]*MAXV
calculated = [False]*MAXV
dp = [1]*MAXV # Vからスタートしたときの最長経路。頂点の個数ベースで経路の長さを数えるので、初期値は1

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1 # 計算が終わっていない頂点を2度訪れるのはループがあるということ
        return dp[v]
    visited[v] = True
    for u in to[v]: # 全ての辺をなめる
        res = dfs(u)
        if res == -1: return -1 # ループがあれば-1を返す
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]

def main():
    n = int(input())
    a = [[int(i) for i in readline().split()] for _ in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1 # 選手idを0始まりに変換
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1 # 0から順に各試合にidを割り振る
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toId(i,a[i][j]) # 選手idを試合id(頂点番号)に置き換える
        for j in range(n-2): # 頂点間の依存関係はn-2個
            to[a[i][j+1]].append(a[i][j])
    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print('-1') # ループがあれば-1を返す（問題文の指示）
            return
        ans = max(ans, res)
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0
count = 0
while count < (n * (n - 1) // 2):
    check = [False] * n
    for i in range(n):
        if not a[i] or check[i] or check[a[i][-1] - 1]:
            continue
        if a[a[i][-1] - 1][-1] == i + 1:
            check[i] = True
            check[a[i][-1] - 1] = True
            a[a[i][-1] - 1].pop()
            a[i].pop()
            count += 1
    ans += 1
    if True not in check:
        ans = -1
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
input = sys.stdin.readline
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a
    

def f():
    IDX = [0] * N
    day = 0
    end = 0
    while 1:
        NEXT_IDX = IDX[:]
        flag = True
        for player, i in enumerate(IDX):
            #print(player, i)
            if i > N-2:
                continue
            #print(player, i)
            enemy = A[player][i]

            if  A[enemy-1][IDX[enemy-1]] == player+1:
                NEXT_IDX[player] += 1
                flag = False
                #print(player, NEXT_IDX)
                if NEXT_IDX[player] == N-1:
                    end += 1
        if flag:
            #print(end, NEXT_IDX)
            return(-1)
        
        day += 1
        if end == N:
            return day
        IDX = NEXT_IDX[:]
print(f())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a

vertex = {}
num = 0
for i, a in enumerate(A):
    i = i+1
    for j in a:
        _i, _j = min(i, j), max(i, j)
        key = "{}-{}".format(_i, _j) 
        if key in vertex:
            pass
        else:
            vertex[key] = num
            num += 1

#print(vertex)
 
from collections import deque
GRAY, BLACK = 0, 1
def topological(graph):
    order, enter, state = deque(), set(graph), {}
 
    def dfs(node):
        state[node] = GRAY
        for k in graph.get(node, ()):
            sk = state.get(k, None)
            if sk == GRAY: raise ValueError("cycle")
            if sk == BLACK: continue
            enter.discard(k)
            dfs(k)
        order.appendleft(node)
        state[node] = BLACK
 
    while enter: dfs(enter.pop())
    return order
 
graph = {v: [] for k, v in vertex.items()}
for i, a in enumerate(A):
    i = i+1
    pre = None
    for j in a:
        _i, _j = min(i, j), max(i, j)
        key = "{}-{}".format(_i, _j) 
        if pre == None:
            pre = vertex[key]
        else:
            cur = vertex[key]
            graph[pre].append(cur)
            pre = cur

#print(graph)
try:
    t = topological(graph)
    dp = [None] * len(t)
    for n in t:
        if dp[n] == None:
            dp[n] = 1
        for to in graph[n]:
            if dp[to] == None:
                dp[to] = dp[n] + 1
            else:
                dp[to] = max(dp[to], dp[n] + 1)
            
    #print(dp)
    print(max(dp))
except:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a[:]

vertex = {}
num = 0
for i, a in enumerate(A):
    i = i+1
    for j in a:
        _i, _j = min(i, j), max(i, j)
        key = "{}-{}".format(_i, _j) 
        if key in vertex:
            pass
        else:
            vertex[key] = num
            num += 1

#print(vertex)

from collections import deque
GRAY, BLACK = 0, 1
def topological(graph):
    order, enter, state = deque(), set(graph), {}

    def dfs(node):
        state[node] = GRAY
        for k in graph.get(node, ()):
            sk = state.get(k, None)
            if sk == GRAY: raise ValueError("cycle")
            if sk == BLACK: continue
            enter.discard(k)
            dfs(k)
        order.appendleft(node)
        state[node] = BLACK

    while enter: dfs(enter.pop())
    return order

graph = {v: [] for k, v in vertex.items()}
for i, a in enumerate(A):
    i = i+1
    pre = None
    for j in a:
        _i, _j = min(i, j), max(i, j)
        key = "{}-{}".format(_i, _j) 
        if pre == None:
            pre = vertex[key]
        else:
            cur = vertex[key]
            graph[pre].append(cur)
            pre = cur

#print(graph)
try:
    t = topological(graph)
    dp = [None] * len(t)
    ans = 1
    for n in t:
        if dp[n] == None:
            dp[n] = 1
        for to in graph[n]:
            if dp[to] == None:
                dp[to] = dp[n] + 1
            else:
                dp[to] = max(dp[to], dp[n] + 1)
            ans = max(ans, dp[to])
            
    #print(dp)
    print(ans)
except:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [None] * N
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a[:]

vertex = {}
num = 0
for i, a in enumerate(A):
    i = i+1
    for j in a:
        _i, _j = min(i, j), max(i, j)
        key = "{}-{}".format(_i, _j) 
        if key in vertex:
            pass
        else:
            vertex[key] = num
            num += 1

#print(vertex)

from collections import deque
GRAY, BLACK = 0, 1
def topological(graph):
    order, enter, state = deque(), set(graph), {}

    def dfs(node):
        state[node] = GRAY
        for k in graph.get(node, ()):
            sk = state.get(k, None)
            if sk == GRAY: raise ValueError("cycle")
            if sk == BLACK: continue
            enter.discard(k)
            dfs(k)
        order.appendleft(node)
        state[node] = BLACK

    while enter: dfs(enter.pop())
    return order

graph = {v: [] for k, v in vertex.items()}
for i, a in enumerate(A):
    i = i+1
    pre = None
    for j in a:
        _i, _j = min(i, j), max(i, j)
        key = "{}-{}".format(_i, _j) 
        if pre == None:
            pre = vertex[key]
        else:
            cur = vertex[key]
            graph[pre].append(cur)
            pre = cur

#print(graph)
try:
    t = topological(graph)
    dp = [None] * len(t)
    for n in t:
        if dp[n] == None:
            dp[n] = 1
        for to in graph[n]:
            if dp[to] == None:
                dp[to] = dp[n] + 1
            else:
                dp[to] = max(dp[to], dp[n] + 1)
            
    #print(dp)
    print(max(dp))
except:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())
 
count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate == 0:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = index_lst
    count += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate == 0:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = index_lst
    count += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
while True:
    index_lst = []
    for i in range(len(current)):
        candidate = current[i]
        if i+1 > candidate:
            continue
        if current[candidate-1] == i+1:
            index_lst += [i+1, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    count += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
while True:
    index_lst = []
    for i in range(len(current)):
        candidate = current[i]
        if candidate == 0:
            continue
        if current[candidate-1] == i+1:
            index_lst += [i+1, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    count += 1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
 
current_loop = []
current = []
for i in range(n):
    a = lst[i].pop(0)
    current_loop.append((a, i+1))
    current.append(a)

count = 0
while True:
    index_lst = []
    for pair in current_loop:
        a, b = pair
        if current[a-1] == b:
            index_lst += [a, b]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            a = lst[i-1].pop(0)
            current[i-1] = a
            current_loop.append((a, i))
    count += 1

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    #%% import
    from itertools import product
    from collections import defaultdict,deque

    #%% input
    n=int(input())
    # list-likeでhashableなのはstrとtuple
    Nodes=[(i,j) for i,j in product(range(n),range(n)) if i<j]
    N=len(Nodes) # N=n*(n-1)//2

    #%% adjacency list
    outs=defaultdict(list)
    indeg=defaultdict(int)
    for i in range(n):
        edge=list(map(lambda x:int(x)-1,input().split()))
        for j in range(len(edge)-1):
            # (min(i,edge[j]),max(i,edge[j])) to (min(i,edge[j+1]),max(i,edge[j+1]))
            v0 = (min(i,edge[j]),max(i,edge[j]))
            v1 = (min(i,edge[j+1]),max(i,edge[j+1]))
            outs[v0].append(v1)
            indeg[v1]+=1

    #%% topological sort
    Q=deque(v for v in Nodes if indeg[v]==0)
    res=[]
    #%%
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in outs[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)

    #%% judge whether G is DAG
    if len(res)<N:
        print("-1")
        return

    #%% LPP(Longest Path Problem)
    LP=defaultdict(lambda :1)
    for v0 in res:
        for v1 in outs[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print(max(LP.values()))
resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].pop(0))
    
count = 0
while True:
    index_lst = []
    for i in range(len(current)):
        candidate = current[i]
        if candidate == 0:
            continue
        if i+1 in index_lst:
            continue
        if current[candidate-1] == i+1:
            index_lst += [i+1, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].pop(0)
    count += 1

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = []
current = []
for i in range(n):
    next_lst = list(map(int, input().split()))
    current.append(next_lst[0])
    lst.append(next_lst[1:])

count = 0
while True:
    index_lst = []
    for i in range(len(current)):
        candidate = current[i]
        if candidate == 0:
            continue
        if current[candidate-1] == i+1:
            index_lst += [i+1, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].pop(0)
    count += 1

Submission status: Time Limit Exceeded

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

current = []
for i in range(n):
    current.append(lst[i].pop(0))

count = 0
while True:
    index_lst = []
    for i in range(len(current)):
        candidate = current[i]
        if candidate == 0:
            continue
        if current[candidate-1] == i+1:
            index_lst += [i+1, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].pop(0)
    count += 1

Submission status: Time Limit Exceeded

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

n = int(input())
A = [[int(i) -1 for i in input().split()]for _ in range(n)]
Aday = [0]*n
Anum = [1]*n


que =[i for i in range(n)]
s = 0

while len(que)!=0:
    i = que.pop(0)
    if len(A[i])!= 0:
        j = A[i][0]
        if A[j][0] == i:
            day = max(Aday[i],Aday[j]) +1
            Aday[i] = day
            Aday[j] = day
            A[i].pop(0)
            A[j].pop(0)
            if len(A[i])!=0:
                que.append(i)
            else:
                s += 1
            if len(A[j]) != 0:
                que.append(j)
            else:
                s += 1

if s != n:
    print(-1)
else:
    print(max(Aday))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i + 1] = inp
    new = tuple(sorted([i + 1, inp[0]]))
    cur_stage.update([new])

cnt = 0
while True:
    flg = 0
    _next = set()
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 1:
                battle_dict[i].pop(0)
            else:
                battle_dict[i].pop(0)
                battle_dict.pop(i)
            if len(battle_dict[j]) > 1:
                battle_dict[j].pop(0)
            else:
                battle_dict[j].pop(0)
                battle_dict.pop(j)
            _next.update(v)
            cur_stage[v] = 0
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    cur_stage.clear()
    for i, j in battle_dict.items():
        new = tuple(sorted([i, j[0]]))
        if i in _next or j[0] in _next:
           cur_stage.update([new])
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

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)]#その周回ですでにバトルしたかどうかのフラグです
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)
    if idx[j] != N-1:
      a = A[j][idx[j]]
      if a>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
if f:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
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 = []

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

v_len = [-1 for _ in range(n)] * n
finished = [False for _ in range(n)] * n

def dfs(id):
    next_list = graph[id]

    if v_len[id] != -1:
        if not finished[id]:
            print(-1)
            sys.exit()
        return v_len[id]

    v_len[id] = 1

    for next in next_list:
        v_len[id] = max(v_len[id], dfs(next)+1)

    finished[id] = True
    return v_len[id]

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])
    
ans = 0

for id in index_list:
    ans = max(dfs(id), ans)

print(ans)