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:
# -*- coding: utf-8 -*-

import sys
from collections import deque

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

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
nxtli = set(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    curli = nxtli.copy()
    nxtli = set()
    for i in curli:
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    # 変更があった場所をセットに入れておく
                    nxtli.add(i)
                    nxtli.add(a)
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

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

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
nxtli = list(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    curli = nxtli.copy()
    nxtli = []
    for i in curli:
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    # 変更があった場所をリストに入れておく
                    nxtli += [i, a]
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)

Submission status: Time Limit Exceeded

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


def topological_sort(G):
    V = len(G)      # グラフの頂点数を取得
    indeg = [0]*V   # 各頂点の入次数を記録。indeg[i]は頂点iの入次数を表す。
    for u in G:
        for v in u:
            indeg[v] += 1
    res = []        # ソート結果を記録
    hq = [i for i in range(V) if indeg[i] == 0]  # 入次数0の頂点を格納
    while hq:  # 入次数0の頂点を除いたグラフの中で入次数0の点を探し、入次数0の点がなくなるまで繰り返す
        u = heapq.heappop(hq)   # 頂点番号の小さいものを優先
        res.append(u)
        for v in G[u]:
            indeg[v] -= 1       # uから辺が伸びていた先の頂点の入次数を1減らす
            if indeg[v] == 0:   # 入次数が0の点があればキューに入れる
                heapq.heappush(hq, v)
    if len(res) == V:  # DAGでない場合はトポロジカルソート後にDPで最長経路を求める
        dp = [1]*V
        for i in res:
            for j in G[i]:
                dp[j] = max(dp[j], dp[i] + 1)
        return max(dp)
    else:
        return -1


N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]
enID = [[False]*N for _ in range(N)]
ID = 0
for i in range(N-1):
    for j in range(i+1, N):
        enID[i][j] = ID
        enID[j][i] = ID
        ID += 1
for i in range(N):
    for j in range(N-1):
        A[i][j] = enID[i][A[i][j]]
G = [[] for _ in range(N*(N-1)//2)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])

print(topological_sort(G))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
from collections import defaultdict
d=defaultdict(int)
l=defaultdict(list)
for i in range(N):
    x,y=(i,A[i][0]-1) if i<A[i][0]-1 else (A[i][0]-1,i)
    d[(x,y)]+=1
    l[(x,y)].append(i)
p=[0]*N
r=0
while len(d)>0:
    r+=1
    f=0
    diff=defaultdict(int)
    for k in list(d.keys()):
        if d[k]==2:
            del d[k]
            for i in l[k]:
                p[i]+=1
                if p[i]>N-2:
                    continue
                x,y=(i,A[i][p[i]]-1) if i<A[i][p[i]]-1 else (A[i][p[i]]-1,i)
                diff[(x,y)]+=1
                l[(x,y)].append(i)
            f=1
    for x,y in diff.keys():
        d[(x,y)]+=diff[(x,y)]
    if f==0:
        break
print(r if f>0 else -1)

Submission status: Time Limit Exceeded

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

day=0

match=[0 for i in range(n)]

while True:
  day+=1
  check=[True for i in range(n)]
  for i in range(n):
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
      
    if i==n-1:
      if not False in check:
        print(-1)
        sys.exit()
  if min(match)==n-1 and min(match)==max(match):
    break
        
print(day)

Submission status: Time Limit Exceeded

Solution code:


def main():
    import sys
    sys.setrecursionlimit(10 ** 8)

    MAXN = 1005
    MAXV = (MAXN * (MAXN - 1)) // 2
    to = [[] for _ in range(MAXV)]
    ID = [[-1] * MAXN for _ in range(MAXN)]

    def toID(i, j):
        if i > j:
            i, j = j, i
        return ID[i][j]

    visited = [False] * MAXV
    calculated = [False] * MAXV
    dp = [0] * MAXV
    def dfs(v): #DAGの最長経路を求める
        if visited[v]: #すでに訪れたことがある時
            if not calculated[v]: #計算されたことがない時 = ループがある
                return -1
            return dp[v]
        visited[v] = True
        dp[v] = 1
        for u in to[v]:
            res = dfs(u)
            if res == -1:
                return -1
            dp[v] = max(dp[v], res + 1)
        calculated[v] = True
        return dp[v]

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

    V = 0 #頂点の数
    for i in range(N - 1):
        for j in range(i + 1, N):
            ID[i][j] = V
            V += 1
    
    for i in range(N):
        for j in range(N - 1):
            a[i][j] = toID(i, a[i][j]) #対戦相手で管理していたのを試合番号に変える
        for j in range(N - 2):
            to[a[i][j + 1]].append(a[i][j])
    
    # import numpy as np
    # print (np.array(to))
    # print (np.array(ID))

    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print (-1)
            return 0
        ans = max(ans, res)
    print (ans)
    return 0

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

MAXN = 1005
MAXV = (MAXN * (MAXN - 1)) // 2
to = [[] for _ in range(MAXV)]
ID = [[-1] * MAXN for _ in range(MAXN)]

def toID(i, j):
    if i > j:
        i, j = j, i
    return ID[i][j]

visited = [False] * MAXV
calculated = [False] * MAXV
dp = [0] * MAXV
def dfs(v): #DAGの最長経路を求める
    if visited[v]: #すでに訪れたことがある時
        if not calculated[v]: #計算されたことがない時 = ループがある
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        res = dfs(u)
        if res == -1:
            return -1
        dp[v] = max(dp[v], res + 1)
    calculated[v] = True
    return dp[v]

def main():
    N = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

    V = 0 #頂点の数
    for i in range(N - 1):
        for j in range(i + 1, N):
            ID[i][j] = V
            V += 1
    
    for i in range(N):
        for j in range(N - 1):
            a[i][j] = toID(i, a[i][j]) #対戦相手で管理していたのを試合番号に変える
        for j in range(N - 2):
            to[a[i][j + 1]].append(a[i][j])
    
    # import numpy as np
    # print (np.array(to))
    # print (np.array(ID))

    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print (-1)
            return 0
        ans = max(ans, res)
    print (ans)
    return 0

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#"""
import sys
input = sys.stdin.readline
#"""
def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
# YouTube2
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
input=sys.stdin.readline

def main():
    def dfs(u):
        if dis[u] > 0:
            return dis[u]
        if dis[u] == 0:
            return -1
        dis[u] = 0
        res = 1
        for v in to[u]:
            tmp = dfs(v) + 1
            if tmp == 0: return -1
            res = max(res, tmp)
        dis[u] = res
        return res

    to = defaultdict(list)
    n = int(input()[:-1])
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
    all_game = n * (n - 1) // 2
    dis = [-1] * all_game
    game = [[0] * n for _ in range(n)]
    u = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            game[i][j] = game[j][i] = u
            u += 1

    for i in range(n):
        ai=a[i]
        gamei=game[i]
        j = ai[0]
        pre = gamei[j]
        for gi in range(1, n - 1):
            j = ai[gi]
            to[pre].append(gamei[j])
            pre = gamei[j]
#    print(to)

    ans=0
    for i in range(all_game):
        tmp=dfs(i)
        if tmp == -1:
            print(-1)
            exit()
        if tmp>ans:
            ans=tmp
#    print(dis)
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

def main():
    N = int(input())
    A = [deque(map(int, input().split())) for i in range(N)]
    
    ans = 0
    finish = False
    base_used = [True] + [False] * N
    count = 0
    
    while not finish and count != N:
        finish = True
        ans += 1
        used = copy.deepcopy(base_used)
        
        for idx, u in enumerate(used):
            if not u:
                a = A[idx-1][0]
                if not used[a] and A[a-1][0] == idx:
                    for x in [idx, a]:
                        used[x] = True
                        A[x-1].popleft()

                        if not A[x-1]:
                            base_used[x] = True
                            count += 1
                    finish = False     
    
    if N != count:
        ans = -1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edges = {}
allnodes = set()
for a in range(1,N+1):
    l = [int(x) for x in input().split()]
    prev = (0, 0)
    for y in l:
        x = a 
        if x > y:
            x, y = y, x 
        allnodes.add((x, y))
        edges.setdefault(prev, set()).add((x, y))
        edges.setdefault((x, y), set())
        prev = x, y

indegree = {n:0 for n in allnodes}
for n in allnodes:
    for v in edges[n]:
        indegree[v]+=1

def schedule(indegree):
    from heapq import heappush, heappop, heapify
    pendings = []
    for n in allnodes:
        if indegree[n] > 0:
            continue
        heappush(pendings, (-len(edges[n]), n))
    scheduled = set()
    players = set()

    d = 1
    while pendings:
        players.clear()

        next = []
        while pendings:
            entry = heappop(pendings)
            o, n =  entry
            a, b = n
            if a in players or b in players:
                next.append(entry)
                break
            for e in edges[n]:
                if e in scheduled:
                    return -1    
                indegree[e]-=1
                if indegree[e] == 0:
                    next.append((-len(edges[e]), e))
            players.add(a)
            players.add(b)
            scheduled.add(n)
        if next:
            pendings = next
            heapify(pendings)
            d += 1
    if len(scheduled) != len(allnodes):
        return -1
    return d

print(schedule(indegree))

Submission status: Time Limit Exceeded

Solution code:
import copy

def main():
    N = int(input())
    A = [list(map(int, input().split())) for i in range(N)]
    
    ans = 0
    finish = False
    base_used = [True] + [False] * N
    count = 0
    
    while not finish and count != N:
        finish = True
        ans += 1
        used = copy.deepcopy(base_used)
        
        for idx, u in enumerate(used):
            if not u:
                a = A[idx-1][0]
                if not used[a] and A[a-1][0] == idx:
                    for x in [idx, a]:
                        used[x] = True
                        A[x-1].pop(0)
                        
                        if not A[x-1]:
                            base_used[x] = True
                            count += 1
                    finish = False     
    
    if N != count:
      ans = -1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# YouTube2
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

def main():
    def dfs(u):
        if dis[u] > 0:
            return dis[u]
        if dis[u] == 0:
            return -1
        dis[u] = 0
        res = 1
        for v in to[u]:
            tmp = dfs(v) + 1
            if tmp == 0: return -1
            res = max(res, tmp)
        dis[u] = res
        return res

    to = defaultdict(list)
    n = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
    all_game = n * (n - 1) // 2
    dis = [-1] * all_game
    game = [[0] * n for _ in range(n)]
    u = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            game[i][j] = game[j][i] = u
            u += 1

    for i in range(n):
        j = a[i][0]
        pre = game[i][j]
        for gi in range(1, n - 1):
            j = a[i][gi]
            to[pre].append(game[i][j])
            pre = game[i][j]
#    print(to)

    for i in range(all_game):
        if dfs(i) == -1:
            print(-1)
            exit()
#    print(dis)
    print(max(dis))

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
N = int(input())
edges = {}
allnodes = set()
for a in range(1,N+1):
    l = [int(x) for x in input().split()]
    prev = (0, 0)
    for y in l:
        x = a 
        if x > y:
            x, y = y, x 
        allnodes.add((x, y))
        edges.setdefault(prev, set()).add((x, y))
        edges.setdefault((x, y), set())
        prev = x, y

indegree = {n:0 for n in allnodes}
for n in allnodes:
    for v in edges[n]:
        indegree[v]+=1

def schedule():
    pendings = []
    for n in allnodes:
        if indegree[n] > 0:
            continue
        heappush(pendings, (-len(edges[n]), n))
    scheduled = set()
    players = set()

    d = 1
    while pendings:
        players.clear()

        next = []
        while pendings:
            entry = heappop(pendings)
            o, n =  entry
            a, b = n
            if a in players or b in players:
                next.append(entry)
                continue
            for e in edges[n]:
                if e in scheduled:
                    return -1    
                indegree[e]-=1
                if indegree[e] == 0:
                    next.append((-len(edges[e]), e))
            players.add(a)
            players.add(b)
            scheduled.add(n)
        if next:
            pendings = next
            heapify(pendings)
            d += 1
    if len(scheduled) != len(allnodes):
        return -1
    return d
print(schedule())

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

def main():
    N = int(input())
    A = [deque(map(int, input().split())) for i in range(N)]
    
    ans = 0
    finish = False
    base_used = [True] + [False] * N
    count = 0
    
    while not finish and count != N:
      finish = True
      ans += 1
      used = copy.deepcopy(base_used)
      
      for idx, u in enumerate(used):
        if not u:
          a = A[idx-1][0]
          if not used[a] and A[a-1][0] == idx:
            used[idx] = True
            used[a] = True
            A[idx-1].popleft()
            A[a-1].popleft()
            finish = False
            
            if not A[idx-1]:
                base_used[idx] = True
                count += 1
                
            if not A[a-1]:
                base_used[a] = True
                count += 1
     
    if N != count:
      ans = -1
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]

    V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
    Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0) if i<a0 else (a0,i)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1) if i<a1 else (a1,i)
            Ef[k0].append(k1)
            V[k1] += 1

    q = [k for k in V if V[k] == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for k in q:
            for k2 in Ef[k]:
                V[k2] -= 1
                rmv += 1
                if V[k2] == 0 : qq.append(k2)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()

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 [0]*N]

    V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
    Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0) if i<a0 else (a0,i)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1) if i<a1 else (a1,i)
            Ef[k0].append(k1)
            V[k1] += 1

    q = [k for k in V if V[k] == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for k in q:
            for k2 in Ef[k]:
                V[k2] -= 1
                rmv += 1
                if V[k2] == 0 : qq.append(k2)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    Ass = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N)]

    games = []
    for i in range(N):
        for j in range(i+1, N):
            games.append((i, j))
    adjL = dict([(game, []) for game in games])

    indegs = dict([(game, 0) for game in games])
    for i, As in enumerate(Ass):
        for j in range(len(As)-1):
            p1, p2, p3, p4 = i, As[j], i, As[j+1]
            if p1 > p2:
                p1, p2 = p2, p1
            if p3 > p4:
                p3, p4 = p4, p3
            adjL[(p1, p2)].append((p3, p4))
            indegs[(p3, p4)] += 1

    gameTodays = set()
    for game in games:
        if indegs[game] == 0:
            gameTodays.add(game)

    ans = 0
    numDone = 0
    while gameTodays:
        gameTomorrows = set()
        for game in gameTodays:
            numDone += 1
            for game2 in adjL[game]:
                indegs[game2] -= 1
                if indegs[game2] == 0:
                    gameTomorrows.add(game2)
        ans += 1
        gameTodays = gameTomorrows

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

solve()

Submission status: Time Limit Exceeded

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

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

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    a0 = B[0]-1
    k1 = (i,a0) if i<a0 else (a0,i)
    for j in range(N-2):
        a1 = B[j+1]-1
        k0 = k1
        k1 = (i,a1) if i<a1 else (a1,i)
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

Submission status: Time Limit Exceeded

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

games = []
for i in range(N):
    for j in range(i+1, N):
        games.append((i, j))
adjL = dict([(game, []) for game in games])

indegs = dict([(game, 0) for game in games])
for i, As in enumerate(Ass):
    for j in range(len(As)-1):
        p1, p2, p3, p4 = i, As[j], i, As[j+1]
        if p1 > p2:
            p1, p2 = p2, p1
        if p3 > p4:
            p3, p4 = p4, p3
        adjL[(p1, p2)].append((p3, p4))
        indegs[(p3, p4)] += 1

gameTodays = set()
for game in games:
    if indegs[game] == 0:
        gameTodays.add(game)

ans = 0
numDone = 0
while gameTodays:
    gameTomorrows = set()
    for game in gameTodays:
        numDone += 1
        for game2 in adjL[game]:
            indegs[game2] -= 1
            if indegs[game2] == 0:
                gameTomorrows.add(game2)
    ans += 1
    gameTodays = gameTomorrows

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

Submission status: Time Limit Exceeded

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

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

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    a0 = B[0]-1
    k1 = (i,a0) if i<a0 else (a0,i)
    for j in range(N-2):
        a1 = B[j+1]-1
        k0 = k1
        k1 = (i,a1) if i<a1 else (a1,i)
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

Submission status: Time Limit Exceeded

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

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

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    for a0,a1 in zip(B[:-1],B[1:]):
        k0 = tuple(sorted((i,a0)))
        k1 = tuple(sorted((i,a1)))
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

Submission status: Time Limit Exceeded

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

V = {(i,j):0 for i in range(N) for j in range(i+1,N)}
Ef = {(i,j):[] for i in range(N) for j in range(i+1,N)}
for i,B in enumerate(A):
    for a0,a1 in zip(B[:-1],B[1:]):
        k0 = tuple(sorted((i,a0)))
        k1 = tuple(sorted((i,a1)))
        Ef[k0].append(k1)
        V[k1] += 1

q = [k for k in V if V[k] == 0]
ans = 0
rmv = 0
while q:
    qq = []
    for k in q:
        for k2 in Ef[k]:
            V[k2] -= 1
            rmv += 1
            if V[k2] == 0 : qq.append(k2)
    ans += 1
    q = qq
if rmv != N*(N-2) : ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
from collections import deque

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return

def gau(n):
    return n*(n+1)//2

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

    done = True
    ans = 0
    cand = [i for i in range(N)]
    while(done):
        done = False
        today = set()
        next_cand = set()
        # 向き合ってるかチェック
        for i in cand:
            if i in today or A[i][0] in today:
                continue
            elif(A[A[i][0]][0] == i):
                # print(i,A[i][0],ans)
                done = True
                today.add(i)
                today.add(A[i][0])
                A[A[i][0]].popleft()
                if len(A[A[i][0]]) != 0:
                    next_cand.add(A[i][0])
                A[i].popleft()
                if len(A[i]) != 0:
                    next_cand.add(i)

            else:
                next_cand.add(i)
                next_cand.add(A[i][0])
        cand = next_cand
        ans += 1
    for i in range(N):
        if len(A[i]) != 0:
            print(-1)
            exit()
    print(ans-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

m = 0
day = 0
while m  < (N * (N-1) // 2):
    #print("Day {}".format(day + 1))
    #print(A)
    #print("==")
    m = 0
    matched = False
    skip = []
    for i in range(N):
        if (not (i in skip)) and (A[i] != []):
            opp = A[i][0]
            if (A[opp - 1][0] == (i + 1)) and (A[opp-1] != []) and not ((opp-1) in skip):
                matched = True
                A[i] = A[i][1:]
                A[opp - 1] = A[opp - 1][1:]
                #print("{} vs {}".format(i+1,opp))
                skip.append(i)
                skip.append(opp-1)
                m = m + 1
    #print("{} matches played".format(m))
    if (not matched):
        for i in range(N):
            if (A[i] != []):
                print(-1)
                exit()
        break
    day = day + 1
print(day)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
from array import array

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return

def gau(n):
    return n*(n+1)//2

def main():
    N = int(input())
    A = [[] for _ in range(N)]
    counter = [0 for _ in range(N)]
    for i in range(N):
        A[i] = array('i',map(lambda x:int(x)-1,input().split()))

    done = True
    ans = 0
    while(done):
        done = False
        today = set()
        # 向き合ってるかチェック
        for i in range(N):
            if counter[i] == N-1 or counter[A[i][counter[i]]] == N-1:
                continue
            else:
                oc = counter[A[i][counter[i]]]
            if i in today or A[i][counter[i]] in today:
                continue
            elif(A[A[i][counter[i]]][oc] == i):
                # print(i,A[i][0],ans)
                done = True
                today.add(i)
                today.add(A[i][counter[i]])
                counter[A[i][counter[i]]]+=1
                counter[i]+=1
        ans += 1

    for i in range(N):
        if counter[i] != N-1:
            print(-1)
            exit()
    print(ans-1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy, sys
 
input = sys.stdin.readline
n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0
 
def check(p, q):
    if not len(a[p]):
        return
    o = a[p][0]
    if p == a[o][0]:
        if p > o: p, o = o, p
        if not (p, o) in q:
            q.append((p, o))
 
fin = []
for p in range(n):
    if not p in fin:
        o = a[p][0]
        if p == a[o][0]:
            q.append((p, o))
            fin += [p, o]
 
while q:
    day += 1
    pre_q = copy.copy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)
 
if all(map(len, a)):
    print(-1)
else:
    print(day)