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:
from collections import deque

n = int(input())

a = [[int(i) for i in input().split()] for j in range(n)]

check = [0]*n
used = [False]*n

d = deque()

for i in reversed(range(n)):
    if used[i] == True:
        continue
    if a[a[i][0]-1][0] == i+1:
        d.appendleft([i+1,a[i][0]])
        used[i] = True
        used[a[i][0]-1] = True
        check[i] = 1
        check[a[i][0]-1] = 1
        
ans = 0

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

#print(d)

while len(d) > 0:
    used = [False]*n
    ans += 1
    num = len(d)
    for i in range(num):
        tmp = d.popleft()
        for j in range(2):
            if check[tmp[j]-1] == n-1:
                continue
            psn = a[tmp[j]-1][check[tmp[j]-1]]-1
            mys = tmp[j]-1
            #print(tmp,psn,a[psn][check[psn]])
            #print(i,j,tmp,psn,check[mys],check[psn])
            if used[mys] == True or used[psn] == True:
                continue
            if check[mys] == n-1 or check[psn] == n:
                continue
            if a[psn][check[psn]] == mys+1:
                d.append([psn+1,mys+1])
                used[mys] = True
                used[psn] = True
                check[mys] += 1
                check[psn] += 1
    #print(d)

for i in range(n):
    if check[i] != n-1:
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import time
def input():
    return sys.stdin.readline()[:-1]
 
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    l = [0] * N
    ans = 0
    count = 0
    check = [False] * N
    tmpl = []
    next = False
 
    while(count < N):
        check = [False] * N
        for i in range(N):
            if l[i] < N - 1:
                to = A[i][l[i]] - 1
                if (not check[to]) and (not check[i]):
                    if A[to][l[to]] - 1 == i:
                        l[i] += 1
                        l[to] += 1
                        check[to] = True
                        check[i] = True
                        next = True
                    if l[i] == N - 1:
                        count += 1
                    if l[to] == N - 1:
                        count += 1
        ans += 1
        if not next:
            print(-1)
            exit()
        next = False
 
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[[] for i in range(N)]
Aflag=[N-1]*N
for i in range(N):
  A[i]=list(map(int,input().split()))
M=0
flag=0
C=set(range(N-1))
while(1):
  M+=1
  bflag=[0]*N
  prAflag=Aflag[:]
  D=set(C)
  for i in C:
    if Aflag[i]>0:
      k=A[i][N-1-Aflag[i]]-1
      l=A[k][N-1-Aflag[k]]-1
      if i==l:
        if bflag[i]==0 and bflag[k]==0:
          Aflag[i]-=1
          Aflag[k]-=1
          bflag[i]=1
          bflag[k]=1
          D|={i,k}
      else:
        D.discard(i)
  C=set(D)
  if sum(Aflag)==0:
    flag=1
    break
  if prAflag==Aflag:
    flag=0
    break
if flag==0:
  print(-1)
else:
  print(M)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[[] for i in range(N)]
Aflag=[N-1]*N
for i in range(N):
  A[i]=list(map(int,input().split()))
M=0
flag=0
C=set(range(N-1))
while(1):
  M+=1
  bflag=[0]*N
  prAflag=Aflag[:]
  D=set(C)
  for i in C:
    if Aflag[i]>0:
      k=A[i][N-1-Aflag[i]]-1
      l=A[k][N-1-Aflag[k]]-1
      if bflag[i]==0 and bflag[k]==0 and i==l:
        Aflag[i]-=1
        Aflag[k]-=1
        bflag[i]=1
        bflag[k]=1
        if Aflag[i]==0:
          D.discard(i)
        if Aflag[k]==0:
          D.discard(k)
  C=set(D)
  if sum(Aflag)==0:
    flag=1
    break
  if prAflag==Aflag:
    flag=0
    break
if flag==0:
  print(-1)
else:
  print(M)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[[] for i in range(N)]
Aflag=[N-1]*N
for i in range(N):
  A[i]=list(map(int,input().split()))
M=0
flag=0
while(1):
  M+=1
  bflag=[0]*N
  prAflag=Aflag[:]
  for i in range(N-1):
    if Aflag[i]>0:
      k=A[i][N-1-Aflag[i]]-1
      l=A[k][N-1-Aflag[k]]-1
      if bflag[i]==0 and bflag[k]==0 and i==l:
        Aflag[i]-=1
        Aflag[k]-=1
        bflag[i]=1
        bflag[k]=1
  if sum(Aflag)==0:
    flag=1
    break
  if prAflag==Aflag:
    flag=0
    break
if flag==0:
  print(-1)
else:
  print(M)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N = int(input())

match = [[-1] * (N) for _ in range(N)]
c = 0
for i in range(N):
    for j in range(i+1, N):
        match[i][j] = c
        c += 1


def get_id(i, j):
    if i > j:
        i, j = j, i
    return match[i][j]


start = []
G = {k: [] for k in range(c)}
for i in range(N):
    L = map(int, input().split())
    pid = -1
    for j, l in enumerate(L):
        id = get_id(i, l-1)
        if j == 0:
            start.append(id)
        else:
            G[pid].append(id)
        pid = id

visited = [False]*c
calculated = [False]*c
dp = [-1]*c


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nxt in G[v]:
        if visited[nxt] is True and calculated[nxt] is False:
            print(-1)
            exit()
        d = dfs(nxt)
        if d >= dp[v]:
            dp[v] = d+1
    calculated[v] = True
    return dp[v]


ans = 0
for i in start:
    res = dfs(i)
    ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N = int(input())

match = [[-1] * (N) for _ in range(N)]
c = 0
for i in range(N):
    for j in range(i+1, N):
        match[i][j] = c
        c += 1


def get_id(i, j):
    if i > j:
        i, j = j, i
    return match[i][j]


G = {k: [] for k in range(c)}
for i in range(N):
    L = map(int, input().split())
    pid = -1
    for l in L:
        id = get_id(i, l-1)
        if pid != -1:
            G[id].append(pid)
        pid = id

visited = [False]*c
calculated = [False]*c
dp = [-1]*c


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nxt in G[v]:
        if visited[nxt] is True and calculated[nxt] is False:
            print(-1)
            exit()
        d = dfs(nxt)
        if d >= dp[v]:
            dp[v] = d+1
    calculated[v] = True
    return dp[v]


ans = 0
for i in range(c):
    res = dfs(i)
    ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N = int(input())

match = [[-1] * (N) for _ in range(N)]
c = 0
for i in range(N):
    for j in range(i+1, N):
        match[i][j] = c
        c += 1
# print(match)


def get_id(i, j):
    if i > j:
        i, j = j, i
    return match[i][j]


G = {k: [] for k in range(c)}
for i in range(N):
    L = map(int, input().split())
    pid = -1
    for l in L:
        id = get_id(i, l-1)
        if pid != -1:
            G[id].append(pid)
        pid = id

visited = [False]*c
calculated = [False]*c
dp = [-1]*c


def dfs(v):
    if dp[v] >= 0:
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nxt in G[v]:
        if visited[nxt] is True and calculated[nxt] is False:
            print(-1)
            exit()
        dp[v] = max(dp[v], dfs(nxt)+1)
    calculated[v] = True
    return dp[v]


ans = 0
for i in range(c):
    res = dfs(i)
    ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N = int(input())

match = [[-1] * (N) for _ in range(N)]
c = 0
for i in range(N):
    for j in range(i+1, N):
        match[i][j] = c
        c += 1
# print(match)


def get_id(i, j):
    if i > j:
        i, j = j, i
    return match[i][j]


G = {k: [] for k in range(c)}
for i in range(N):
    L = map(int, input().split())
    pid = -1
    for l in L:
        id = get_id(i, l-1)
        if pid != -1:
            G[id].append(pid)
        pid = id

visited = [False]*c
calculated = [False]*c
dp = [-1]*c


def dfs(v):
    if visited[v]:
        if not calculated[v]:
            print(-1)
            exit()
        return dp[v]
    visited[v] = True
    dp[v] = 1
    for nxt in G[v]:
        dp[v] = max(dp[v], dfs(nxt)+1)
    calculated[v] = True
    return dp[v]


ans = 0
for i in range(c):
    res = dfs(i)
    ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
my_append = A.append
for i in range(N):
    my_append(list(map(int,input().split())))
def League():
    A_cnt = [0]*N
    A_cnt_copy = [0]*N
    day = 0
    flag = 0
    for i in range((N*(N-1))//2):
        for j in range(N):
            try:
                index = A[j][A_cnt[j]]-1
                if j<index and A[index][A_cnt[index]]-1==j:
                    A_cnt_copy[j]+=1
                    A_cnt_copy[index]+=1
                    flag = 1
            except:
                pass
        A_cnt = A_cnt_copy[:]
        if flag == 1:
            day+=1
            flag = 0
            if A_cnt==[N-1 for i in range(N)]:
                return A_cnt, day
        else:
            if not A_cnt==[N-1 for i in range(N)]:
                return A_cnt, -1
    return A_cnt, day

A_cnt, day = League()
if A_cnt==[N-1 for i in range(N)]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
my_append = A.append
for i in range(N):
    my_append(list(map(int,input().split())))
def League():
    A_cnt = [0 for i in range(N)]
    A_cnt_copy = [0 for i in range(N)]
    day = 0
    flag = 0
    for i in range((N*(N-1))//2):
        for j in range(N):
            try:
                index = A[j][A_cnt[j]]-1
                if j<index and A[index][A_cnt[index]]-1==j:
                    A_cnt_copy[j]+=1
                    A_cnt_copy[index]+=1
                    flag = 1
            except:
                pass
        A_cnt = A_cnt_copy[:]
        if flag == 1:
            day+=1
            flag = 0
            if A_cnt==[N-1 for i in range(N)]:
                return A_cnt, day
        else:
            if not A_cnt==[N-1 for i in range(N)]:
                return A_cnt, -1
    return A_cnt, day

A_cnt, day = League()
if A_cnt==[N-1 for i in range(N)]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int,input().split())))
def League():
    A_cnt = [0 for i in range(N)]
    A_cnt_copy = [0 for i in range(N)]
    day = 0
    flag = 0
    for i in range((N*(N-1))//2):
        for j in range(N):
            try:
                index = A[j][A_cnt[j]]-1
                if j<index and A[index][A_cnt[index]]-1==j:
                    A_cnt_copy[j]+=1
                    A_cnt_copy[index]+=1
                    flag = 1
            except:
                pass
        A_cnt = A_cnt_copy[:]
        if flag == 1:
            day+=1
            flag = 0
            if A_cnt==[N-1 for i in range(N)]:
                return A_cnt, day
        else:
            if not A_cnt==[N-1 for i in range(N)]:
                return A_cnt, -1
    return A_cnt, day

A_cnt, day = League()
if A_cnt==[N-1 for i in range(N)]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int,input().split())))
def League():
    A_cnt = [0 for i in range(N)]
    A_cnt_copy = [0 for i in range(N)]
    day = 0
    flag = 0
    for i in range((N*(N-1))//2):
        for j in range(N):
            try:
                index = A[j][A_cnt[j]]-1
                if j<index and A[index][A_cnt[index]]-1==j:
                    A_cnt_copy[j]+=1
                    A_cnt_copy[index]+=1
                    flag = 1
            except:
                pass
        A_cnt = A_cnt_copy[:]
        if flag == 1:
            day+=1
            flag = 0
        if A_cnt==[N-1 for i in range(N)]:
            return A_cnt, day
    return A_cnt, day

A_cnt, day = League()
if A_cnt==[N-1 for i in range(N)]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int,input().split())))
def League():
    A_cnt = [0 for i in range(N)]
    A_cnt_copy = [0 for i in range(N)]
    day = 0
    flag = 0
    for i in range((N*(N-1))//2):
        for j in range(N):
            try:
                index = A[j][A_cnt[j]]-1
                if j<index and A[index][A_cnt[index]]-1==j:
                    A_cnt_copy[j]+=1
                    A_cnt_copy[index]+=1
                    flag = 1
            except:
                pass
        A_cnt = A_cnt_copy[:]
        if flag == 1:
            day+=1
            flag = 0
    return A_cnt, day

A_cnt, day = League()
if A_cnt==[N-1 for i in range(N)]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
flag = 0
for i in range(N):
    A.append(list(map(int,input().split())))
A_cnt = [0 for i in range(N)]
A_cnt_copy = [0 for i in range(N)]
day = 0
for i in range((N*(N-1))//2):
    for j in range(N):
        try:
            index = A[j][A_cnt[j]]-1
            if j<index and A[index][A_cnt[index]]-1==j:
                A_cnt_copy[j]+=1
                A_cnt_copy[index]+=1
                flag = 1
        except:
            pass
    A_cnt = A_cnt_copy[:]
    if flag == 1:
        day+=1
        flag = 0
    if A_cnt==[N-1 for i in range(N)]:
        break

if A_cnt==[N-1 for i in range(N)]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
flag = 0
for i in range(N):
    A.append(list(map(int,input().split())))
A_cnt = [0 for i in range(N)]
A_cnt_copy = [0 for i in range(N)]
day = 0
for i in range((N*(N-1))//2):
    for j in range(N):
        try:
            index = A[j][A_cnt[j]]-1
            if j<index and A[index][A_cnt[index]]-1==j:
                A_cnt_copy[j]+=1
                A_cnt_copy[index]+=1
                flag = 1
        except:
            pass
    A_cnt = A_cnt_copy[:]
    if flag == 1:
        day+=1
        flag = 0

if A_cnt==[N-1 for i in range(N)]:
    print(day)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n=int(input())

    # id table
    N=0
    id=[[None]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            id[i][j]=N
            N+=1
    toID=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(n-2):
            u=toID(i,A[j])
            v=toID(i,A[j+1])
            E[u].append(v)

    # longest path problem
    dp=[-1]*N
    @lru_cache(None)
    def dfs(v):
        dp[v]=-2
        res=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(n)]

    N=0
    id=[[None]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            id[i][j]=N
            N+=1

    to_id=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        for j in range(n-2):
            u=to_id(i,A[i][j])
            v=to_id(i,A[i][j+1])
            E[u].append(v)

    # longest path problem
    dp=[None]*N
    visited=[0]*N

    def dfs(v):
        if(dp[v] is not None): return dp[v]
        visited[v]=1
        res=0
        for nv in E[v]:
            if((dp[nv] is None) and visited[nv]):
                print(-1)
                exit(0)
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n=int(input())
    A=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(n)]

    N=0
    V={}
    for i in range(n):
        for j in range(i+1,n):
            V[(i,j)]=N
            N+=1

    E=[[] for _ in range(N)] # N=n*(n-1)//2
    for i in range(n):
        for j in range(n-2):
            u=V[(min(i,A[i][j]),max(i,A[i][j]))]
            v=V[(min(i,A[i][j+1]),max(i,A[i][j+1]))]
            E[u].append(v)

    # longest path problem
    dp=[None]*N
    visited=[0]*N

    def dfs(v):
        if(dp[v] is not None): return dp[v]
        visited[v]=1
        res=0
        for nv in E[v]:
            if((dp[nv] is None) and visited[nv]):
                print(-1)
                exit(0)
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n=int(input())
    A=[tuple(map(lambda x:int(x)-1,input().split())) for _ in range(n)]

    N=0
    V={}
    for i in range(n):
        for j in range(i+1,n):
            V[(i,j)]=N
            N+=1

    E=[[] for _ in range(N)] # N=n*(n-1)//2
    for i in range(n):
        for j in range(n-2):
            u=V[(min(i,A[i][j]),max(i,A[i][j]))]
            v=V[(min(i,A[i][j+1]),max(i,A[i][j+1]))]
            E[u].append(v)

    # longest path problem
    calculated=[0]*N
    visited=[0]*N

    @lru_cache(None)
    def dfs(v):
        visited[v]=1
        res=0
        for nv in E[v]:
            if((not calculated[nv]) and visited[nv]):
                print(-1)
                exit(0)
            res=max(res,dfs(nv)+1)
        calculated[v]=1
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    from collections import defaultdict

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # O(N)
    def is_not_empty():
        for x in A:
            if x:
                return True
        return False

    answer = 0
    while is_not_empty():
        played = defaultdict(int)
        for i in range(1,N+1):
            if played[i] == 1:
                continue
            if not A[i]:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and played[enemy] == 0:
                played[enemy] = 1
                played[ME] = 1
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not played:
            print(-1)
            exit()
        answer += 1

    print(answer)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    from collections import defaultdict

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # O(N)
    def is_not_empty():
        for x in A:
            if x:
                return True
        return False

    answer = 0
    while is_not_empty():
        played = defaultdict(int)
        for i in range(1,N+1):
            if i in played:
                continue
            if not A[i]:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and played[enemy] == 0:
                played[enemy] += 1
                played[ME] += 1
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not played:
            print(-1)
            exit()
        answer += 1

    print(answer)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # O(N)
    def is_not_empty():
        for x in A:
            if x:
                return True
        return False

    answer = 0
    while is_not_empty():
        if answer == N*(N-1)//2:
            print(-1)
            exit()
        played = set()
        for i in range(1,N+1):
            if i in played:
                continue
            if not A[i]:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in played):
                played.add(ME)
                played.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not played:
            print(-1)
            exit()
        answer += 1

    print(answer)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # O(N)
    def is_not_empty():
        for x in A:
            if x:
                return True
        return False

    answer = 0
    while is_not_empty():
        played = set()
        for i in range(1,N+1):
            if i in played:
                continue
            if not A[i]:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in played):
                played.add(ME)
                played.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not played:
            print(-1)
            exit()
        answer += 1

    print(answer)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # O(N)
    def is_not_empty():
        for x in A:
            if x:
                return True
        return False

    answer = 0
    while is_not_empty():
        played = set()
        for i in range(1,N+1):
            if i in played:
                continue
            if not A[i]:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in played):
                played.add(ME)
                played.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if len(played) == 0:
            print(-1)
            exit()
        answer += 1

    print(answer)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())
    # i-indexed
    A = [deque() for _ in range(N+1)]
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    def is_not_empty():
        for x in A:
            if len(x) != 0:
                return True
        return False

    answer = 0
    while is_not_empty():
        played = set()
        for i in range(1,N+1):
            if i in played:
                continue
            if len(A[i]) == 0:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in played):
                played.add(ME)
                played.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if len(played) == 0:
            print(-1)
            exit()
        answer += 1

    print(answer)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N = int(input())
# i-indexed
A = [deque() for _ in range(N+1)]
for i in range(1,N+1):
    for j in input().split():
        A[i].append(int(j))

def is_not_empty():
    for x in A:
        if len(x) != 0:
            return True
    return False

answer = 0
while is_not_empty():
    played = []
    append = played.append
    for i in range(1,N+1):
        if i in played:
            continue
        if len(A[i]) == 0:
            continue
        enemy = A[i].popleft()
        ME = A[enemy].popleft()
        if ME == i and not(enemy in played):
            append(ME)
            append(enemy)
        else:
            A[i].appendleft(enemy)
            A[enemy].appendleft(ME)
    if len(played) == 0:
        print(-1)
        exit()
    answer += 1

print(answer)

Submission status: Time Limit Exceeded

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

N = int(input())
# i-indexed
A = [deque() for _ in range(N+1)]
for i in range(1,N+1):
    for j in input().split():
        A[i].append(int(j))

def is_not_empty():
    for x in A:
        if len(x) != 0:
            return True
    return False

answer = 0
while is_not_empty():
    played = []
    append = played.append
    for i in range(1,N+1):
        if i in played:
            continue
        if len(A[i]) == 0:
            continue
        enemy = A[i].popleft()
        ME = A[enemy].popleft()
        if ME == i and not(enemy in played):
            append(ME)
            append(enemy)
        else:
            A[i].appendleft(enemy)
            A[enemy].appendleft(ME)
    if len(played) == 0:
        print(-1)
        exit()
    answer += 1

print(answer)

Submission status: Time Limit Exceeded

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

d = 0
while A != [[] for i in range(N)]:
  s = []
  for i in range(len(A)-1):
    for j in range(i+1, len(A)):
      if A[i] != [] and A[j] != []:
        if i+1 == A[j][0] and j+1 == A[i][0]:
          s.append(i)
          s.append(j)
  if s != []:
    for k in range(len(s)):
      del A[s[k]][0]
    d += 1
  elif s == []:
    d = -1
    break
  
print(d)
#print(A)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    temp = list(map(int, input().split()))
    for j in range(N-1):
        temp[j] -= 1
    A.append(temp)

cur = [0] * N
goal = 0
day = 0
while goal < N:
    day += 1
    changed = False
    new_cur = cur[:]
    for i in range(N):
        if cur[i] == N-1:
            continue
        opponent =  A[i][cur[i]]
        if cur[opponent] == N-1:
            continue
        
        if A[opponent][cur[opponent]] == i:
            new_cur[i] += 1
            new_cur[opponent] += 1
            cur[opponent] = N-1
            changed = True
            if new_cur[i] == N-1:
                goal += 1
            if new_cur[opponent] == N-1:
                goal += 1
                
    cur = new_cur
    if not changed:
        print(-1)
        exit()

print(day)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
    temp = list(map(int, input().split()))
    for j in range(N-1):
        temp[j] -= 1
    A.append(temp)

cur = [0] * N
goal = 0
day = 0
while goal < N:
    day += 1
    changed = False
    new_cur = cur[:]
    for i in range(N):
        if cur[i] == N-1:
            continue
        opponent =  A[i][cur[i]]
        if A[opponent][cur[opponent]] == i:
            new_cur[i] += 1
            changed = True
            if new_cur[i] == N-1:
                goal += 1
    cur = new_cur
    if not changed:
        print(-1)
        exit()

print(day)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            no_ls.append(i)
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = copy.deepcopy(next_candidate)
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)