Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

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
remain = list(range(n))
rest = n * (n - 1) / 2
while rest:
    combis = set()
    no_ls = []
    flg = False
    for i in remain:
        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:
            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))
    remain = list(set(remain) - set(no_ls))
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

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
remain = list(range(n))
while True:
    combis = set()
    no_ls = []
    flg = False
    for i in remain:
        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:
            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))
    remain = set(remain) - set(no_ls)
    if not flg:
        if not any([len(i) for i in a_ls.values()]):
            break
        cnt = -1
        break
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

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
while True:
    combis = set()
    flg = False
    for i in range(n):
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            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))
    if not flg:
        if not any([len(i) for i in a_ls.values()]):
            break
        cnt = -1
        break
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline())
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
while True:
    combis = set()
    flg = False
    for i in range(n):
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            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))
    if not flg:
        if not any([len(i) for i in a_ls.values()]):
            break
        cnt = -1
        break
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

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()]
    res = tuple(sorted((i, inp[0])))
    if ct.get(res) is None:
        ct[res] = 1
    else:
        ct[res] += 1
    a_ls[i] = inp[1:]
cnt = 0
while sum(ct.values()) > 0:
    ls = []
    flg = False
    for k, v in ct.items():
        if v > 1:
            if len(a_ls[k[0]]) > 0:
                ls.append(tuple(sorted((a_ls[k[0]][0], k[0]))))
                a_ls[k[0]].pop(0)
            if len(a_ls[k[1]]) > 0:
                ls.append(tuple(sorted((a_ls[k[1]][0], k[1]))))
                a_ls[k[1]].pop(0)
            ct[k] = 0
            flg = True
    for l in ls:
        if ct[l] is None:
            ct[l] = 0
        ct[l] += 1
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())


def main():
    N = next(read)
    A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
    day = 0

    while True:
        done = set()
        for i in range(1, N + 1):
            if i not in done and A[i]:
                if A[A[i][0]][0] == i and A[i][0] not in done:
                    done.add(A[A[i][0]].popleft())
                    done.add(A[i].popleft())

        if len(done) == 0:
            for i in A:
                if len(i) > 0:
                    print(-1)
                    exit()
            else:
                print(day)
                exit()

        day += 1


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
day = 0

while True:
    done = set()
    for i in range(1, N + 1):
        if i not in done and A[i]:
            if A[A[i][0]][0] == i and A[i][0] not in done:
                done.add(A[A[i][0]].popleft())
                done.add(A[i].popleft())

    if len(done) == 0:
        for i in A:
            if len(i) > 0:
                print(-1)
                exit()
        else:
            print(day)
            exit()
    
    day += 1

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    dr=[]
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            dr.append((i,j))
            cnt+=1
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            if i>=j:temp.append(d[(j-1,i)])
            else:temp.append(d[(i,j-1)])
        for j,k in enumerate(temp[1:]):
            g[temp[j]].append(k)
            gr[k]+=1
    q=[i for i,j in enumerate(gr) if j==0]
    cnt=0
    while q:
        cnt+=1
        qq=[]
        temp=[]
        s=set()
        for i in q:
            x,y=dr[i]
            if (x not in s) and (y not in s):
                temp.append(i)
                s.add(x)
                s.add(y)
            else:
                qq.append(i)
        for i in temp:
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    dr=[]
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            dr.append((i,j))
            cnt+=1
    #print(d)
    #print(dr)
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            j-=1
            if i>j:temp.append(d[(j,i)])
            else:temp.append(d[(i,j)])
        for j in range(len(temp)-1):
            g[temp[j]].append(temp[j+1])
            gr[temp[j+1]]+=1
    #print(g)
    #print(gr)
    q=[]
    for i in range(m):
        if gr[i]==0:
            q.append(i)
    cnt=0
    #print(q)
    while q:
        cnt+=1
        qq=[]#次回に回す分
        temp=[]#今回試合する分
        s=set()#戦うチーム
        while q:#今回の試合を抽出
            i=q.pop()
            x,y=dr[i]
            if (x not in s) and (y not in s):
                temp.append(i)
                s.add(x)
                s.add(y)
            else:
                qq.append(i)
        #print(temp,"t")
        while temp:
            i=temp.pop()
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        #print(qq)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print(-1)



main()

Submission status: Time Limit Exceeded

Solution code:
import time

t0 = time.clock()

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

ind = [0 for i in range(N)]
days = 0
while True:
    if time.clock() - t0 > 1:
        print(N * (N - 1) // 2)
        
    madeMatch = False
    
    played = [False for i in range(N)]
    for i in range(N):
        if ind[i] == N-1 or played[i]: continue
        playAgainst = mat[i][ind[i]]
        if mat[playAgainst][ind[playAgainst]] == i and not played[playAgainst]:
            madeMatch = True
            played[i] = True
            played[playAgainst] = True

            ind[playAgainst] += 1
            ind[i] += 1
    if not madeMatch: break
    days += 1
    
if all(x == N-1 for x in ind):
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import time

t0 = time.clock()

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

ind = [0 for i in range(N)]
days = 0
while True:
    if time.clock() - t0 > 1.5e+6:
        print(N * (N - 1) // 2)
        
    madeMatch = False
    
    played = [False for i in range(N)]
    for i in range(N):
        if ind[i] == N-1 or played[i]: continue
        playAgainst = mat[i][ind[i]]
        if mat[playAgainst][ind[playAgainst]] == i and not played[playAgainst]:
            madeMatch = True
            played[i] = True
            played[playAgainst] = True

            ind[playAgainst] += 1
            ind[i] += 1
    if not madeMatch: break
    days += 1
    
if all(x == N-1 for x in ind):
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

ind = [0 for i in range(N)]
days = 0
while True:
    madeMatch = False
    
    played = [False for i in range(N)]
    for i in range(N):
        if ind[i] == N-1 or played[i]: continue
        playAgainst = mat[i][ind[i]]
        if mat[playAgainst][ind[playAgainst]] == i and not played[playAgainst]:
            madeMatch = True
            played[i] = True
            played[playAgainst] = True

            ind[playAgainst] += 1
            ind[i] += 1
    if not madeMatch: break
    days += 1
    
if all(x == N-1 for x in ind):
    print(days)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = []
x_idx = [0]*n
x_idx_next = [0]*n
flag = True

for i in range(0,n):
  x.append(list(map(int, input().split())))

count = -1
while flag:
  flag = False
  count += 1
  x_idx = x_idx_next[:]
  for i in range(0,n):
    if x_idx_next[i] == x_idx[i] and x_idx[i] < n-1 and x_idx[x[i][x_idx[i]]-1] < n-1 and x[x[i][x_idx[i]]-1][x_idx[x[i][x_idx[i]]-1]] == i+1:
      x_idx_next[i] += 1
      x_idx_next[x[i][x_idx[i]]-1] += 1
      flag = True

if sum(x_idx) == n*(n-1):
  print(count)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = []
x_idx = [0]*n
x_idx_add = [0]*n
flag = True

for i in range(0,n):
  x.append(list(map(int, input().split())))

count = -1
while flag:
  flag = False
  count += 1
  for i in range(len(x_idx)):
    x_idx[i] += x_idx_add[i]
  x_idx_add = [0]*n
  for i in range(0,n):
    if x_idx_add[i] == 0 and x_idx[i] < n-1 and x_idx[x[i][x_idx[i]]-1] < n-1 and x[x[i][x_idx[i]]-1][x_idx[x[i][x_idx[i]]-1]] == i+1:
      x_idx_add[i] = 1
      x_idx_add[x[i][x_idx[i]]-1] = 1
      flag = True

if sum(x_idx) == n*(n-1):
  print(count)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = []
x_idx = [0]*n
x_idx_add = [0]*n
flag = True

for i in range(0,n):
  x.append(list(map(int, input().split())))

count = -1
while sum(x_idx_add) != 0 or flag:
  flag = False
  count += 1
  for i in range(len(x_idx)):
    x_idx[i] += x_idx_add[i]
  x_idx_add = [0]*n
  for i in range(0,n):
    if x_idx_add[i] == 0 and x_idx[i] < n-1 and x_idx[x[i][x_idx[i]]-1] < n-1 and x[x[i][x_idx[i]]-1][x_idx[x[i][x_idx[i]]-1]] == i+1:
      x_idx_add[i] = 1
      x_idx_add[x[i][x_idx[i]]-1] = 1

if sum(x_idx) == n*(n-1):
  print(count)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(1100000)
N = int(input())
side = [[[]for _ in range(N)]for _ in range(N)] 
node = [[1]*N for i in range(N)]
for i in range(N):
    A = list(map(int,input().split()))
    for j in range(N-2):
        a,b = min(i,A[j]-1),max(i,A[j]-1)
        c,d = min(i,A[j+1]-1),max(i,A[j+1]-1)
        side[a][b].append([c,d])
        node[c][d] = 0
def DFS(x,y,l):
    if l > N**2:
        print(-1)
        exit()
    ret = l
    for i,j in side[x][y]:
        ret = max(ret, DFS(i,j,l+1))
    return ret


ans = 0
for i in range(N):
    for j in range(i+1,N):
        if node[i][j]:
            ans = max(DFS(i,j,1),ans)
if ans:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
lst=[[] for i in range(n**2)]
li=[[] for i in range(n**2)]
for i in range(n):
    a=list(map(int,input().split()))
    for j in range(n-2):
        i1=i
        i2=i
        b=a[j]-1
        c=a[j+1]-1
        if i1>b:
            i1,b=b,i1
        if i2>c:
            i2,c=c,i2
        lst[n*i1+b].append(n*i2+c)
        li[n*i2+c].append(n*i1+b)
que=[1]
for _ in range(n*(n-1)//2+1):
    h=[]
    for u in que:
        for v in lst[u]:
            h.append(v)
    if not h:
        break
    que=h
else:
    print(-1)
    sys.exit()
count=0
while que:
    h=[]
    for u in que:
        for v in li[u]:
            h.append(v)
    que=h
    count+=1
    if count==n*(n-1)//2+1:
        print(-1)
        sys.exit()
print(count)

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-17 20:44:23(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n = int(sys.stdin.readline().rstrip())
    table = [None] + [list(reversed([int(x) for x in sys.stdin.readline().split()])) for _ in range(n)]


    match_remainder = n * (n - 1) // 2
    for day in range(1, n * (n - 1) // 2 + 2):
        day_finished = []
        day_matches = 0
        for i in range(1, n+1):
            if not table[i]:
                continue
            if i in day_finished:
                continue
            j = table[i][-1]
            if j in day_finished:
                continue
            # if not table[j]:
            #     continue
            if table[j][-1] == i:
                day_finished += [i, j]
                table[j].pop()
                table[i].pop()
                match_remainder -= 1
                day_matches += 1
            else:
                day_finished.append(i)
        if not day_matches:
            if match_remainder == 0:
                print(day - 1)
                sys.exit()
            print(-1)
            sys.exit()

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-17 20:44:23(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n = int(sys.stdin.readline().rstrip())
    table = [None] + [collections.deque(int(x) for x in sys.stdin.readline().split()) for _ in range(n)]


    match_remainder = n * (n - 1) // 2
    for day in range(1, n * (n - 1) // 2 + 2):
        day_finished = []
        day_matches = 0
        for i in range(1, n+1):
            if not table[i]:
                continue
            if i in day_finished:
                continue
            j = table[i][0]
            if j in day_finished:
                continue
            # if not table[j]:
            #     continue
            if table[j][0] == i:
                day_finished += [i, j]
                table[j].popleft()
                table[i].popleft()
                match_remainder -= 1
                day_matches += 1
            else:
                day_finished.append(i)
        if not day_matches:
            if match_remainder == 0:
                print(day - 1)
                sys.exit()
            print(-1)
            sys.exit()

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-17 20:44:23(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n = int(sys.stdin.readline().rstrip())
    table = [None] + [collections.deque(int(x) for x in sys.stdin.readline().split()) for _ in range(n)]


    match_remainder = n * (n - 1) // 2
    for day in range(1, n * (n - 1) // 2 + 2):
        already_played = []
        for i in range(1, n+1):
            if not table[i]:
                continue
            if i in already_played:
                continue
            j = table[i][0]
            if j in already_played:
                continue
            # if not table[j]:
            #     continue
            if table[j][0] == i:
                already_played += [i, j]
                table[j].popleft()
                table[i].popleft()
                match_remainder -= 1
        if not already_played:
            if match_remainder == 0:
                print(day - 1)
                sys.exit()
            print(-1)
            sys.exit()
        




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while True:
            if len(ql) != 0:
                d, ps = ql.popleft()
                if d == i:
                    if fq[ps]:
                        nw = a[ps][ls[ps]]
                        if fq[nw]:
                            rw = a[nw][ls[nw]]
                            if ps == rw:
                                ls[ps] += 1
                                ls[nw] += 1
                                if ls[ps] < n - 1:
                                    ql.append([d+1, ps])
                                if ls[nw] < n - 1:
                                    ql.append([d+1, nw])
                                fq[nw] = False
                                fq[ps] = False
                else:
                    ql.appendleft([d, ps])
                    break
            else:
                if sum(ls) == n * (n - 1):
                    print(i + 1)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if fq[ps]:
                    nw = a[ps][ls[ps]]
                    if fq[nw]:
                        rw = a[nw][ls[nw]]
                        if ps == rw:
                            ls[ps] += 1
                            ls[nw] += 1
                            if ls[ps] < n - 1:
                                ql.append([d+1, ps])
                            if ls[nw] < n - 1:
                                ql.append([d+1, nw])
                            fq[nw] = False
                            fq[ps] = False
            else:
                ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# 2019-11-17 20:44:23(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# import re
# import heapq
# import array
# from scipy.misc import comb # (default: exact=False)
# import numpy as np 


def main():
    n = int(sys.stdin.readline().rstrip())
    table = [None] + [collections.deque(int(x) for x in sys.stdin.readline().split()) for _ in range(n)]
    
    for day in range(1, n * (n - 1) // 2 + 2):
        already_played = []
        finished_count = 0
        for i in range(1, n+1):
            if not table[i]:
                finished_count += 1
                continue
            if i in already_played:
                continue
            j = table[i][0]
            if j in already_played:
                continue
            # if not table[j]:
            #     continue
            if table[j][0] == i:
                already_played += [i, j]
                table[j].popleft()
                table[i].popleft()
        if not already_played:
            if finished_count == n:
                print(day - 1)
                sys.exit()
            print(-1)
            sys.exit()
        




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    nw = a[ps][ls[ps]]
                    if ls[nw] < n - 1 and fq[nw]:
                        rw = a[nw][ls[nw]]
                        if ps == rw:
                            ls[ps] += 1
                            ql.append([d+1, ps])
                            ls[nw] += 1
                            ql.append([d+1, nw])
                            fq[nw] = False
                            fq[ps] = False
            else:
                ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    if ps == rw and fq[nw]:
                        ls[ps] += 1
                        ql.append([d+1, ps])
                        ls[nw] += 1
                        ql.append([d+1, nw])
                        fq[nw] = False
            else:
                if d > i:
                    ql.append([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    if ps == rw and fq[nw]:
                        ls[ps] += 1
                        ql.append([d+1, ps])
                        ls[nw] += 1
                        ql.append([d+1, nw])
                        fq[nw] = False
            else:
                if d > i:
                    ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    if ps == rw and fq[nw]:
                        if n > ls[ps] + 1:
                            ls[ps] += 1
                            ql.append([d+1, ps])
                        if n > ls[nw] + 1:
                            ls[nw] += 1
                            ql.append([d+1, nw])
                        fq[nw] = False
            else:
                if d > i:
                    ql.appendleft([d, ps])
                    break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    fq[ps] = False
                    nw = a[ps][ls[ps]]
                    rw = a[nw][ls[nw]]
                    if ps == rw and fq[nw]:
                        ls[ps] += 1
                        ql.append([d+1, ps])
                        ls[nw] += 1
                        ql.append([d+1, nw])
                        fq[nw] = False
            else:
                if d > i:
                    ql.appendleft([d, ps])
                    break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()