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 bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = defaultdict(set)

    V = set()

    def ij2v(i, j):
        if i > j:
            i, j = j, i
        return i * 10**6 + j
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = ij2v(i, a[j])
            v = ij2v(i, a[j+1])
            g[u].append(v)
            rg[v].add(u)
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if rg[v]:
            pass
        else:
            s.append(v)

    done = set(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                if v in done:
                    continue
                rg[v].remove(u)
                if len(rg[v]) == 0:
                    ns.append(v)
                    done.add(v)
        s = ns

    if len(done) != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    g = defaultdict(list)
    rg = defaultdict(set)

    V = set()
    for i, a in enumerate(A, start=1):
        for j in range(len(a)-1):
            u = (min(i, a[j]), max(i, a[j]))
            v = (min(i, a[j+1]), max(i, a[j+1]))
            g[u].append(v)
            rg[v].add(u)
            V.add(u)
            V.add(v)

    s = []
    for v in V:
        if rg[v]:
            pass
        else:
            s.append(v)

    done = set(s)
    ans = 0
    while s:
        ans += 1
        ns = []
        for u in s:
            for v in g[u]:
                if v in done:
                    continue
                rg[v].remove(u)
                if len(rg[v]) == 0:
                    ns.append(v)
                    done.add(v)
        s = ns

    if len(done) != N * (N-1) // 2:
        return -1

    return ans



def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

n=int(input())
a=[[0]*(n-1) for i in range(n)]
id=[[-1]*(n) for i in range(n)]
MAXV=n*(n-1)//2
to=[[]*(n) for i in range(MAXV)]
  
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):
  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():
  for i in range(n):
    a[i]=list(map(lambda x:int(x)-1,input().split()))
  v=0
  for i in range(n):
    for j in range(n):
      if i<j:
        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])
      
  ans=0
  for i in range(v):
    res=dfs(i)
    if res==-1:
      print(-1)
      exit(0)
    ans=max(ans, res)

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

Submission status: Time Limit Exceeded

Solution code:
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())

    A = [[0]*(N)]
    for i in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    del reverseMemo
    del A
    
    stepMemo = {}
    def dfs(i,j,path):
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            if (i,j) in path:
                print(-1)
                exit()
            else:
                path.add((i,j))
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,path)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j,set()))
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(input())

    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

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

    edges = {}
    for match in matchs:
        edges[match] = []
        i,j = match
        if reverseMemo[i][j] != N-1:
            nx = A[i][reverseMemo[i][j]+1]
            edges[match].append((min(i,nx),max(i,nx)))
        if reverseMemo[j][i] != N-1:
            nx = A[j][reverseMemo[j][i]+1]
            edges[match].append((min(j,nx),max(j,nx)))

    stepMemo = {}
    def dfs(i,j,path):
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            if (i,j) in path:
                print(-1)
                exit()
            else:
                path.add((i,j))
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,path)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j,set()))
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(input())

    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

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

    edges = {}
    for match in matchs:
        edges[match] = []
        i,j = match
        if reverseMemo[i][j] != N-1:
            nx = A[i][reverseMemo[i][j]+1]
            edges[match].append((min(i,nx),max(i,nx)))
        if reverseMemo[j][i] != N-1:
            nx = A[j][reverseMemo[j][i]+1]
            edges[match].append((min(j,nx),max(j,nx)))

    stepMemo = {}
    def dfs(i,j,cnt):
        if cnt > len(matchs):
            print(-1)
            exit()
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,cnt+1)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j,1))
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(input())

    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

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

    edges = {}
    for match in matchs:
        edges[match] = []
        i,j = match
        if reverseMemo[i][j] != N-1:
            nx = A[i][reverseMemo[i][j]+1]
            edges[match].append((min(i,nx),max(i,nx)))
        if reverseMemo[j][i] != N-1:
            nx = A[j][reverseMemo[j][i]+1]
            edges[match].append((min(j,nx),max(j,nx)))

    stepMemo = {}
    def dfs(i,j,cnt):
        if cnt > N*N:
            print(-1)
            exit()
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,cnt+1)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j,1))
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
import sys
sys.setrecursionlimit(1000000)

N = int(input())

A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))
 
#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

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

edges = {}
for match in matchs:
    edges[match] = []
    i,j = match
    if reverseMemo[i][j] != N-1:
        nx = A[i][reverseMemo[i][j]+1]
        edges[match].append((min(i,nx),max(i,nx)))
    if reverseMemo[j][i] != N-1:
        nx = A[j][reverseMemo[j][i]+1]
        edges[match].append((min(j,nx),max(j,nx)))

stepMemo = {}
def dfs(i,j,cnt):
    if cnt > len(matchs):
        print(-1)
        exit()
    #i,jの試合日を含めて、あと何日必要なのかを返す。
    if (i,j) not in stepMemo:
        res = 1
        for a,b in edges[(i,j)]:
            res = max(res,dfs(a,b,cnt+1)+1)
        stepMemo[(i,j)] = res
    return stepMemo[(i,j)]

ans = 0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        ans = max(ans,dfs(i,j,1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
import sys
sys.setrecursionlimit(1000000)

N = int(input())

A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))
 
#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

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

edges = {}
for match in matchs:
    edges[match] = []
    i,j = match
    if reverseMemo[i][j] != N-1:
        nx = A[i][reverseMemo[i][j]+1]
        edges[match].append((min(i,nx),max(i,nx)))
    if reverseMemo[j][i] != N-1:
        nx = A[j][reverseMemo[j][i]+1]
        edges[match].append((min(j,nx),max(j,nx)))

stepMemo = {}
def dfs(i,j,cnt):
    if cnt > N*N:
        print(-1)
        exit()
    #i,jの試合日を含めて、あと何日必要なのかを返す。
    if (i,j) not in stepMemo:
        res = 1
        for a,b in edges[(i,j)]:
            res = max(res,dfs(a,b,cnt+1)+1)
        stepMemo[(i,j)] = res
    return stepMemo[(i,j)]

ans = 0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        ans = max(ans,dfs(i,j,1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  n=int(input())
  a=[0]*n
  for i in range(n):
    a[i]=deque(list(map(lambda x:int(x)-1,input().split())))
  q=deque([])
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      if x not in q and y not in q:
        q.append(x)
        q.append(y)
        a[x].popleft()
        a[y].popleft()

  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if len(a[y])==0: continue;
      if x == a[y][0] and x not in q and y not in q:
        q.append(x)
        q.append(y)
        a[x].popleft()
        a[y].popleft()

    #print(f'a={a}')
    if len(q)==0: break;


  for i in range(n):
    if len(a[i])!=0:
      print(-1)
      exit()
  print(day)


if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n=int(input())
a=[0]*n

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

  
q=deque([])
for idx,i in enumerate(a):
  x=idx
  y=i[0]
  if x == a[y][0]:
    if x not in q and y not in q:
      q.append(x)
      q.append(y)
      a[x].popleft()
      a[y].popleft()

      
day=0
while True:
  day+=1
  t=deque([])
  while q:
    t.append(q.popleft())
  while t:
    i=t.popleft()
    if len(a[i])==0: continue;
    #print(f'i={i},a[i][0]={a[i][0]}')
    j=a[i][0]
    if len(a[j])==0: continue;
    if i == a[j][0] and i not in q and j not in q:
      q.append(i)
      q.append(j)
      a[i].popleft()
      a[j].popleft()
  
  #print(f'a={a}')
  if len(q)==0: break;


for i in range(n):
  if len(a[i])!=0:
    print(-1)
    exit()
print(day)

Submission status: Time Limit Exceeded

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

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
flags = [False for i in range(n)]
nums = [0 for i in range(n)]
day = 0
flag = True
while False in flags:
    if flag == False:
        break
    match = set()
    for i in range(n):
        if nums[i] == n - 1 or i in match:
            continue
        num = a[i][nums[i]] - 1
        if nums[num] == n - 1:
            flag = False
            break
        if num in match:
            continue
        if a[num][nums[num]] - 1 == i:
            match.add(i)
            match.add(num)
            nums[i] += 1
            nums[num] += 1
            if nums[i] == n - 1:
                flags[i] = True
            if nums[num] == n - 1:
                flags[num] = True
    if not match:
        flag = False
        break
    day += 1
if flag == True:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
flags = [False for i in range(n)]
nums = [0 for i in range(n)]
day = 0
flag = True
while False in flags:
    if flag == False:
        break
    match = set()
    for i in range(n):
        if nums[i] == n - 1:
            continue
        num = a[i][nums[i]] - 1
        if nums[num] == n - 1:
            flag = False
            break
        if a[num][nums[num]] - 1 == i:
            if i not in match and num not in match:
                match.add(i)
                match.add(num)
                nums[i] += 1
                nums[num] += 1
                if nums[i] == n - 1:
                    flags[i] = True
                if nums[num] == n - 1:
                    flags[num] = True
    if not match:
        flag = False
        break
    day += 1
if flag == True:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())) + [-1])
flags = [False for i in range(n)]
nums = [0 for i in range(n)]
day = 0
flag = True
while False in flags:
    if flag == False:
        break
    match = set()
    for i in range(n):
        if nums[i] == n - 1:
            continue
        num = a[i][nums[i]] - 1
        if nums[num] == n - 1:
            flag = False
            break
        if a[num][nums[num]] - 1 == i:
            if i not in match and num not in match:
                match.add(i)
                match.add(num)
                nums[i] += 1
                nums[num] += 1
                if nums[i] == n - 1:
                    flags[i] = True
                if nums[num] == n - 1:
                    flags[num] = True
    if not match:
        flag = False
        break
    day += 1
if flag == True:
    print(day)
else:
    print(-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())) + [-1])
flags = [False for i in range(n)]
nums = [0 for i in range(n)]
day = 0
flag = True
while False in flags:
    if flag == False:
        break
    match = set()
    for i in range(n):
        if nums[i] == n - 1:
            continue
        num = a[i][nums[i]] - 1
        if nums[num] == n - 1:
            flag = False
            break
        if a[num][nums[num]] - 1 == i:
            if i not in match and num not in match:
                match.add(i)
                match.add(num)
                nums[i] += 1
                nums[num] += 1
                if nums[i] == n - 1:
                    flags[i] = True
                if nums[num] == n - 1:
                    flags[num] = True
    if not match:
        flag = False
        break
    day += 1
if flag == True:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

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


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
Last = [True] * N
while cnt:
    flag = True
    Done = [False] * N
    for i, a in enumerate(A):
        if not Last[i]:
            continue
        if len(a) == 0:
            continue
        if Done[i]:
            continue
        x = a[-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1
    Last = Done
    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

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


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
while cnt:
    flag = True
    Done = [False] * N
    for i, a in enumerate(A):
        if len(a) == 0:
            continue
        if Done[i]:
            continue
        x = a[-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1

    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

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


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
while True:
    flag = True
    Done = [False] * N
    for i, a in enumerate(A):
        if len(a) == 0:
            continue
        if Done[i]:
            continue
        x = a[-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            flag = False
    if flag:
        break
    day += 1
F = False
for a in A:
    if len(a) != 0:
        F = True
        break
if F:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
while True:
    flag = True
    Done = [False] * N
    for i, a in enumerate(A):
        if len(a) == 0:
            continue
        if Done[i]:
            continue
        x = a[-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            flag = False
    if flag:
        break
    day += 1
F = False
for a in A:
    if len(a) != 0:
        F = True
        break
if F:
    print(-1)
else:
    print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(now):
  res=day[now]
  if vis[now]:
    if res==-1:return -1
    else:return res
  res=1
  vis[now]=1
  for to in d[now]:
    r=dfs(to)
    if r==-1:return -1
    res=max(res,r+1)
  day[now]=res
  return res
n=int(input())
INF=10**18
c=[]
for i in range(n):
  for j in range(i+1,n):
    c+=[(i,j)]
d=dict(zip(c,[[] for _ in range(n*(n-1)//2)]))
s=[]
for i in range(n):
  a=list(map(int,input().split()))
  if i<a[0]-1:b=(i,a[0]-1)
  else:b=(a[0]-1,i)
  s+=[b]
  for j in a[1:]:
    j-=1
    if i<j:
      d[b]+=[(i,j)]
      b=(i,j)
    else:
      d[b]+=[(j,i)]
      b=(j,i)
vis=dict(zip(c,[0]*(n*(n-1)//2)))
day=dict(zip(c,[-1]*(n*(n-1)//2)))
ans=0
for i in s:
  di=dfs(i)
  if di==-1:
    print(-1)
    exit()
  ans=max(ans,di)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(now):
  res=1
  if vis[now]:
    if day[now]==-1:return -1
    else:return day[now]
  vis[now]=1
  for to in d[now]:
    r=dfs(to)
    if r==-1:return -1
    res=max(res,r+1)
  day[now]=res
  return res
n=int(input())
INF=10**18
c=[]
for i in range(n):
  for j in range(i+1,n):
    c+=[(i,j)]
d=dict(zip(c,[[] for _ in range(n*(n-1)//2)]))
s=[]
for i in range(n):
  a=list(map(int,input().split()))
  if i<a[0]-1:b=(i,a[0]-1)
  else:b=(a[0]-1,i)
  s+=[b]
  for j in a[1:]:
    j-=1
    if i<j:
      d[b]+=[(i,j)]
      b=(i,j)
    else:
      d[b]+=[(j,i)]
      b=(j,i)
vis=dict(zip(c,[0]*(n*(n-1)//2)))
day=dict(zip(c,[-1]*(n*(n-1)//2)))
ans=0
for i in s:
  di=dfs(i)
  if di==-1:
    print(-1)
    exit()
  ans=max(ans,di)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    rem = N * (N - 1) // 2
    for day in range(N * (N - 1) // 2):
        did_play = [0] * N
        for i in range(N):
            if did_play[i] or A[i] == []:
                continue
            opponent = A[i][-1]
            if A[opponent][-1] == i and not did_play[opponent]:
                A[i].pop()
                A[opponent].pop()
                rem -= 1
                did_play[i] = 1
                did_play[opponent] = 1
        if sum(did_play) == 0:
            break
        if rem == 0:
            return day + 1
    return -1


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

Submission status: Time Limit Exceeded

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

for day in range(N * (N - 1) // 2):
    did_play = [0] * N
    for i in range(N):
        if did_play[i] or A[i] == []:
            continue
        opponent = A[i][-1]
        if A[opponent][-1] == i and not did_play[opponent]:
            A[i].pop()
            A[opponent].pop()
            did_play[i] = 1
            did_play[opponent] = 1
    if all(a == [] for a in A):
        print(day + 1)
        break
else:
    print(-1)

Submission status: Time Limit Exceeded

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


def main():
    n = int(read())
    V = 1000000

    g = [[] for _ in range(V)]
    deg = [0] * V
    vlist = [False] * V

    for i in range(n):
        a = list(map(lambda x: int(x) - 1, read().rstrip().split()))
        for j in range(n - 2):
            v1 = min(i, a[j]) * 1000 + max(i, a[j])
            v2 = min(i, a[j + 1]) * 1000 + max(i, a[j + 1])
            vlist[v1] = True
            vlist[v2] = True
            g[v1].append(v2)
            deg[v2] += 1

    d = [0] * V
    check_cnt = 0
    q = []
    for v in range(V):
        if vlist[v] and deg[v] == 0:
            q.append(v)

    if len(q) == 0:
        print(-1)
        exit()

    for v in q:
        check_cnt += 1
        for nv in g[v]:
            d[nv] = max(d[nv], d[v] + 1)
            deg[nv] -= 1
            if deg[nv] == 0:
                q.append(nv)
    if check_cnt == n * (n - 1) // 2:
        print(max(d) + 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    n = int(read())
    V = 1001000

    g = [[] for _ in range(V)]
    deg = [0] * V
    vlist = set()

    for i in range(1, n + 1):
        a = list(map(int, read().rstrip().split()))
        for j in range(n - 1):
            v1 = min(i, a[j]) * 1001 + max(i, a[j])
            vlist.add(v1)
            if j == n - 2:
                break
            v2 = min(i, a[j + 1]) * 1001 + max(i, a[j + 1])
            g[v1].append(v2)
            deg[v2] += 1

    d = [0] * V
    check_cnt = 0
    q = deque()
    for v in vlist:
        if deg[v] == 0:
            q.append(v)

    if len(q) == 0:
        print(-1)
        exit()

    while len(q):
        v = q.popleft()
        check_cnt += 1
        for nv in g[v]:
            d[nv] = max(d[nv], d[v] + 1)
            deg[nv] -= 1
            if deg[nv] == 0:
                q.append(nv)
    if check_cnt == n * (n - 1) // 2:
        print(max(d) + 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    n = int(read())
    V = 1001000

    g = [[] for _ in range(V)]
    deg = [0] * V
    vlist = set()

    for i in range(1, n + 1):
        a = list(map(int, read().rstrip().split()))
        for j in range(n - 2):
            v1 = min(i, a[j]) * 1001 + max(i, a[j])
            v2 = min(i, a[j + 1]) * 1001 + max(i, a[j + 1])
            vlist.add(v1)
            vlist.add(v2)
            g[v1].append(v2)
            deg[v2] += 1

    d = [0] * V
    check_cnt = 0
    q = []
    for v in vlist:
        if deg[v] == 0:
            q.append(v)

    if len(q) == 0:
        print(-1)
        exit()

    for v in q:
        check_cnt += 1
        for nv in g[v]:
            d[nv] = max(d[nv], d[v] + 1)
            deg[nv] -= 1
            if deg[nv] == 0:
                q.append(nv)
    if check_cnt == n * (n - 1) // 2:
        print(max(d) + 1)
    else:
        print(-1)


if __name__ == '__main__':
    main()