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: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
import time
ts=time.time()
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
ans=0
MacthNum=0
yet=set(range(n))
n_yet=set(range(n))
while flg and MacthNum<n*(n-1)//2:
    elp=time.time()-ts
    if elp>1.8:
        ans=0#n*(n-1)//2
        break
    ans+=1
    IsMatch=False
    done=set()
    #print('Day',ans,IsMatch,nx)
    for i in yet:
        n_yet=[]
        if (i in done) or (nx[i] in done) or nx[i]==n:
            continue
        c1=i
        c2=nx[i]
        if c1==nx[c2]:
            IsMatch=True
            MacthNum+=1
            #print('Day',ans,'Match',c1,'vs',c2)
            if t[c1]:
                n_i=t[c1].pop()
                n_yet.append(c1)
            else:
                n_i=n
            if t[c2]:
                n_n_i=t[c2].pop()
                n_yet.append(c2)
            else:
                n_n_i=n
            #print(i,nx[i],nx)
            nx[nx[i]],nx[i]=n_n_i,n_i
            done.add(c1)
            done.add(c2)
            #print('i,t,d',i,t,'done=',done,'nx=',nx,n_i,n_n_i)
    yet=[i for i in n_yet]
    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

print(ans)

Submission status: Wrong Answer

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict,deque
    import copy
    
    N = int(input())
    A = defaultdict(list)
    C = defaultdict(list)
    parent = deque()
    
    for i in range(1,N+1):
        tmp = list(map(int, input().split()))
        for j in range(1,len(tmp)):
            ii0 = min(i,tmp[j-1])
            jj0 = max(i,tmp[j-1])
            ii1 = min(i,tmp[j])
            jj1 = max(i,tmp[j])
            if A[(ii0,jj0)] == []:
                A[(ii0,jj0)] = [[],[]]
                C[(ii0,jj0)] = [[],[]]
            if A[(ii1,jj1)] == []:
                A[(ii1,jj1)] = [[],[]]
                C[(ii1,jj1)] = [[],[]]
            A[(ii0,jj0)][1].append((ii1,jj1))
            A[(ii1,jj1)][0].append((ii0,jj0))
    
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if A[(i,j)][0] == []:
                parent.append((i,j))
    #print(A)                        
    def toposort(node):
        #print(D)
        
        if D[node] == 1:
            print(-1)
            sys.exit()
        elif D[node] == 0:
            D[node] = 1
            for i in A[node][1]:
                toposort(i)
            D[node] = 2
            L.appendleft(node)
    
    L = deque()
    D = defaultdict(int)
    if parent == []:
      print(-1)
      sys.exit()
    for i in parent:
      toposort(i)
    
    
    B = defaultdict(int)
    mattan = []
    #print(L)
    for i in L:
        tmp = 0
        for j in A[i][0]:
            if tmp < B[j]:
                tmp = B[j]
        B[i] = tmp+1
        if A[i][1] == []:
            mattan.append(i)
    ans = 0
    
    for i in mattan:
        if B[i] > ans:
            ans = B[i]
    print(ans)
 
        
        
    
    
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  for i in range(N):
    if b[i]==i+1:
      cnt+=0
    elif i==b[b[i]-1]-1:
      c[i]+=1
  #print('c='+str(c))
  for i in range(N):
    b[i]=a[i][c[i]]
  #print('b='+str(b))
  cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()

print('1')

Submission status: Wrong Answer

Solution code:
# トポロジカルソートを使った例
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict,deque
    import copy
    
    N = int(input())
    A = defaultdict(list)
    C = defaultdict(list)
    parent = deque()
    
    for i in range(1,N+1):
        tmp = list(map(int, input().split()))
        for j in range(1,len(tmp)):
            ii0 = min(i,tmp[j-1])
            jj0 = max(i,tmp[j-1])
            ii1 = min(i,tmp[j])
            jj1 = max(i,tmp[j])
            if A[(ii0,jj0)] == []:
                A[(ii0,jj0)] = [[],[]]
                C[(ii0,jj0)] = [[],[]]
            if A[(ii1,jj1)] == []:
                A[(ii1,jj1)] = [[],[]]
                C[(ii1,jj1)] = [[],[]]
            A[(ii0,jj0)][1].append((ii1,jj1))
            A[(ii1,jj1)][0].append((ii0,jj0))
    
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if A[(i,j)][0] == []:
                parent.append((i,j))
    #print(A)                        
    def toposort(node):
        #print(D)
        
        if D[node] == 1:
            print(-1)
            sys.exit()
        elif D[node] == 0:
            D[node] = 1
            for i in A[node][1]:
                toposort(i)
            D[node] = 2
            L.appendleft(node)
    
    L = deque()
    D = defaultdict(int)
    flag = 0
    for i in range(1,N+1):
      for j in range(i+1,N+1):
        toposort((i,j))
    print(flag)
    if flag == 1:
      print(-1)
      sys.exit()
    
    
    B = defaultdict(int)
    mattan = []
    #print(L)
    for i in L:
        tmp = 0
        for j in A[i][0]:
            if tmp < B[j]:
                tmp = B[j]
        B[i] = tmp+1
        if A[i][1] == []:
            mattan.append(i)
    ans = 0
    
    for i in mattan:
        if B[i] > ans:
            ans = B[i]
    print(ans)

        
        
    
    
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
n = int(input())
league = [[int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]

total_match=n*(n-1)//2
match=0
day=0


for _ in range(total_match):
    day+=1
    today_match=[]

    for i in range(n):
        try:
            m=league[i][-1]-1
            if not i in today_match and not m in today_match:
                if league[m][-1]-1==i:
                    today_match.extend((i,m))
                    league[i].pop()
                    league[m].pop()
        except:
            continue
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2
    if match>=total_match:
        break

print(day)

Submission status: Wrong Answer

Solution code:



def judge_and_count(A_lst, played_count):
    count = 0
    p1, p2 = -1, -1
    ends = [0]*(len(A_lst))
    already_played = [0]*(len(A_lst) + 1)
    p = [(-1,-1)]
    for p1 in range(1, N+1):
        for p2 in range(p1+1, N+1):
            if A_lst[p1][0] == p2 and A_lst[p2][0] == p1 and already_played[p1] == 0 and already_played[p2] == 0:
                p.append((p1, p2))
                A_lst[p1].pop(0)
                A_lst[p2].pop(0)
                already_played[p1] = 1
                already_played[p2] = 1

    for i in range(len(already_played)):
        already_played[i] = 0

    ###########
#    print(p)
    ###########

    new_play = False
    while True:
        
        if p[0] == (-1, -1):
            count += 1
            p.pop(0)
            p.append((-1, -1))
            
            for i in range(len(already_played)):
                already_played[i] = 0
            new_play = False

        e1, e2 = p.pop(0)
        if len(A_lst[e1]) == 0:
            p1 = 0
        else:
            p1 = A_lst[e1][0]
        if len(A_lst[e2]) == 0:
            p2 = 0
        else:
            p2 = A_lst[e2][0]

        if len(A_lst[p1]) > 0 and already_played[p1] == 0 and already_played[e1] == 0:
            if A_lst[p1][0] == e1:
                p.append((p1, e1))
                A_lst[p1].pop(0)
                A_lst[e1].pop(0)
                already_played[p1] = 1
                already_played[e1] = 1
                new_play = True
                if len(A_lst[p1]) == 0:
                    ends[p1] = 1
                if len(A_lst[e1]) == 0:
                    ends[e1] = 1
                
        if len(A_lst[p2]) > 0 and already_played[p2] == 0 and already_played[e2] == 0:
            if A_lst[p2][0] == e2:
                p.append((p2, e2))
                A_lst[p2].pop(0)
                A_lst[e2].pop(0)
                already_played[p2] = 1
                already_played[e2] = 1
                new_play = True
                if len(A_lst[p2]) == 0:
                    ends[p2] = 1
                if len(A_lst[e2]) == 0:
                    ends[e2] = 1


        if not new_play:
            return -1
        if sum(ends) == len(ends) - 1:
            count += 1
            return count

    

    


N = int(input())

played_count = [0]*(N+1)

A_lst = [[]]


for i in range(N):
    A_low = list(map(int, input().split()))
    A_lst.append(A_low)


ans = judge_and_count(A_lst, played_count)

print(ans)

Submission status: Wrong Answer

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

N = int(input())
A = [deque([int(i)-1 for i in input().split()]) for _ in range(N)]

def solve() :
    q = []
    for i in range(N) :
        if A[i][0] > i :
            q.append(i)
            
    count = 0
    ret = 0
    while count != N * (N - 1) // 2 :
        if len(q) == 0 :
            return -1
        q_ = []
        done = [False] * N
        for v in q :
            w = A[v][0]
            if v == A[w][0] :
                if done[v] or done[w] :
                    q_.append(min(v, w))
                else :
                    A[v].popleft()
                    A[w].popleft()
                    done[v] = done[w] = True
                    count += 1
                    if len(A[v]) > 0 and A[v][0] > v :
                        q_.append(v)
                    if len(A[w]) > 0 and A[w][0] > w :
                        q_.append(w)        

        ret += 1
        q = q_
        
    return ret
    
print(solve())

Submission status: Wrong Answer

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

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

def main(N, A):
    now = [A[i].pop() for i in range(N)]
    day = 1
    rest = N * (N-1) // 2

    # WCS O(N**2) <- 1日に1試合だけのときN(N-1)/2回while文が繰り返される
    while True:
        # terminal condition
        # O(1)
        if rest == 0:
            return day

        # see if we have match today
        have_match = False
        # O(N)
        for i in range(N):
            if now[now[i]] == i:
                now[now[i]] = A[now[i]].pop()
                now[i] = A[i].pop()

                rest -= 1
                have_match = True
        if not have_match:
            return -1
        day += 1

print(main(N, A))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())

    def f(i, j):
        return  max(i, j) * N + min(i, j)

    edges = defaultdict(deque)
    deg = defaultdict(int)

    for i in range(1, N + 1):
        A = list(map(int, input().split()))
        for j in range(N - 2):
            edges[f(i, A[j])].append(f(i, A[j + 1]))
            deg[f(i, A[j + 1])] += 1

    que = set()
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            if deg[f(i, j)] == 0:
                que.add(f(i, j))

    que = deque(que)
    L = deque()
    while que:
        now = que.popleft()
        L.append(now)

        while edges[now]:
            to = edges[now].popleft()
            deg[to] -= 1
            if deg[to] == 0:
                que.append(to)

    for _, e in edges.items():
        if e:
            print('-1')
            return

    return 0
    ans = 0
    while L:
        V = set()
        while L:
            player, enemy = divmod(L[0], N)
            if player in V or enemy in V:
                break
            V.add(player)
            V.add(enemy)
            L.popleft()
        ans += 1

    print(ans)

sol()

Submission status: Wrong Answer

Solution code:
import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [IL()[::-1] for i in range(N)]

used = [-1]*N
total = N*(N-1)//2
flag = 1
cnt = 0
days = 0
while flag:
  flag = 0
  for i in range(N):
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        flag = 1
        cnt += 1
  else:
    if flag == 1:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(0)

Submission status: Wrong Answer

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

N = int(input())
A = [deque([int(i)-1 for i in input().split()]) for _ in range(N)]

def solve() :
    q = []
    for i in range(N) :
        if A[i][0] > i :
            q.append(i)
            
    count = 0
    ret = 0
    while count != N * (N - 1) // 2 :
        if len(q) == 0 :
            return -1
        q_ = []
        done = [False] * N
        for v in q :
            w = A[v][0]
            if v == A[w][0] :
                if done[w] :
                    q_.append(v)
                else :
                    A[v].popleft()
                    A[w].popleft()
                    done[w] = True
                    count += 1
                    if len(A[v]) > 0 and A[v][0] > v :
                        q_.append(v)
                    if len(A[w]) > 0 and A[w][0] > w :
                        q_.append(w)        

        ret += 1
        q = q_
        q.sort()
        
    return ret
    
print(solve())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from copy import deepcopy as dc
import time
st = time.time()
N = int(input())
e = dd(list)

matche = dd(list)

for i in range(1, N + 1):
  e[i] = list(map(int, input().split()))

for i in range(1, N + 1):
  for j in range(N - 2):
    if matche[(min(e[i][j], i), max(e[i][j], i))] != []:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    else:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    #print(i, j, matche)
#print(matche)
matchkey = dc(matche)
S = matchkey.keys()
visited = dd(int)
depth = 0
#print(S)
def dfs(s):
  if time.time() - st > 1.7:
    print(N * (N - 1) // 2)
    exit(0)
  global visited
  global depth
  temp = 0
  #print(s)
  if matche[s] != []:
    for c in matche[s]:
      if visited[c] == 1:
        print(-1)
        #print(visited, c)
        exit(0)
      else:
        depth += 1
        visited[c] = 1
        #print(depth)
        temp = max(dfs(c), temp)
        depth -= 1
        visited[c] = 0
  else:
    return depth
  return temp
temp = 0
for s in S:
  temp = max(dfs(s), temp)
print(temp + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from copy import deepcopy as dc
import time
st = time.time()
N = int(input())
e = dd(list)

matche = dd(list)

for i in range(1, N + 1):
  e[i] = list(map(int, input().split()))

for i in range(1, N + 1):
  for j in range(N - 2):
    if matche[(min(e[i][j], i), max(e[i][j], i))] != []:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    else:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    #print(i, j, matche)
#print(matche)
matchkey = dc(matche)
S = matchkey.keys()
visited = dd(int)
depth = 0
#print(S)
def dfs(s):
  if time.time() - st > 1.94:
    print(N * (N - 1) // 2)
    exit(0)
  global visited
  global depth
  temp = 0
  #print(s)
  if matche[s] != []:
    for c in matche[s]:
      if visited[c] == 1:
        print(-1)
        #print(visited, c)
        exit(0)
      else:
        depth += 1
        visited[c] = 1
        #print(depth)
        temp = max(dfs(c), temp)
        depth -= 1
        visited[c] = 0
  else:
    return depth
  return temp
temp = 0
for s in S:
  temp = max(dfs(s), temp)
print(temp + 1)

Submission status: Wrong Answer

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

N = int(input())
A = [deque([int(i)-1 for i in input().split()]) for _ in range(N)]

def solve() :
    q = []
    for i in range(N) :
        if A[i][0] > i :
            q.append(i)
            
    count = 0
    ret = 0
    while count != N * (N - 1) // 2 :
        q_ = []
        flg = True
        done = [False] * N
        for v in q :
            if len(A[v]) == 0 :
                return -1
            w = A[v][0]
            if len(A[w]) == 0 :
                return -1
            
            if v == A[w][0] :
                if done[v] or done[w] :
                    q_.append(min(v, w))
                else :
                    A[v].popleft()
                    A[w].popleft()
                    done[v] = done[w] = True
                    count += 1
                    flg = False
                    if len(A[v]) > 0 and A[v][0] > v :
                        q_.append(v)
                    if len(A[w]) > 0 and A[w][0] > w :
                        q_.append(w)
        if flg :
            return -1
        
        ret += 1
        q = q_
    return ret
    
print(solve())

Submission status: Wrong Answer

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

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

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)

indegree = [0] * n_game
for i in range(n_game):
    for v in edge[i]:
        indegree[v] += 1

ans = 0
cand = [[i for i in range(n_game) if indegree[i] == 0], []]
n_ts = 0
while cand[ans%2]:
    n_ts += len(cand)
    cand[(ans+1)%2] = []
    for ci in cand[ans%2]:
        for v in edge[ci]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand[(ans+1)%2].append(v)
    ans += 1

if n_ts != n_game:
    ans = -1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    Ai = [int(v) - 1 for v in input().split()]
    A.append(Ai)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    Ai = [int(v) - 1 for v in input().split()]
    A.append(Ai)


def match_id(i0, i1):
    if i0 <= i1:
        return (i0, i1)
    return (i1, i0)


graph = {}
for i in range(N):
    for j in range(len(A[i]) - 1):
        mid0 = match_id(i, A[i][j])
        mid1 = match_id(i, A[i][j + 1])

        graph.setdefault(mid0, {}).setdefault('out', []).append(mid1)
        graph[mid1]['indeg'] = graph.setdefault(mid1, {}).get('indeg', 0) + 1

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
A = []
for i in range(N):
    Ai = [int(v) - 1 for v in input().split()]
    A.append(Ai)


def match_id(i0, i1):
    if i0 <= i1:
        return (i0, i1)
    return (i1, i0)


graph = {}
for i in range(N):
    for j in range(len(A[i]) - 1):
        mid0 = match_id(i, A[i][j])
        mid1 = match_id(i, A[i][j + 1])

        graph.setdefault(mid0, {}).setdefault('out', []).append(mid1)
        graph[mid1]['indeg'] = graph.setdefault(mid1, {}).get('indeg', 0) + 1

queue = []
for mid in graph:
    if graph.get(mid, {}).get('indeg', 0) == 0:
        queue.append(mid)

order = []
while len(queue) > 0:
    mid0 = queue.pop()
    order.append(mid0)
    for mid1 in graph.get(mid0, {}).get('out', []):
        graph[mid1]['indeg'] = graph.setdefault(mid1, {}).get('indeg', 0) - 1
        if graph.get(mid1, {}).get('indeg', 0) == 0:
            queue.append(mid1)
if len(order) < N * (N - 1) // 2:
    print(-1)
    sys.exit()

Submission status: Wrong Answer

Solution code:
import sys

N = int(input())
A = []
for i in range(N):
    Ai = [int(v) - 1 for v in input().split()]
    A.append(Ai)


def match_id(i0, i1):
    if i0 <= i1:
        return (i0, i1)
    return (i1, i0)


graph = {}
for i in range(N):
    for j in range(len(A[i]) - 1):
        mid0 = match_id(i, A[i][j])
        mid1 = match_id(i, A[i][j + 1])

        graph.setdefault(mid0, {}).setdefault('out', []).append(mid1)
        graph[mid1]['indeg'] = graph.setdefault(mid1, {}).get('indeg', 0) + 1

queue = []
for mid in graph:
    if graph.get(mid, {}).get('indeg', 0) == 0:
        queue.append(mid)

order = []
while len(queue) > 0:
    mid0 = queue.pop()
    order.append(mid0)
    for mid1 in graph.get(mid0, {}).get('out', []):
        graph[mid1]['indeg'] = graph.setdefault(mid1, {}).get('indeg', 0) - 1
        if graph.get(mid1, {}).get('indeg', 0) == 0:
            queue.append(mid1)
if len(order) < N * (N - 1) // 2:
    print(-1)
    sys.exit()

cnt = 1
rest = set()
for mid in order:
    i0, i1 = mid
    if i0 in rest or i1 in rest:
        cnt += 1
        rest = set()
    rest.add(i0)
    rest.add(i1)
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy

n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0

def check(p, q):
    if not len(a[p]):
        return
    o = a[p][0]
    if p == a[o][0]:
        if p > o: p, o = o, p
        if not (p, o) in q:
            q.append((p, o))

fin = []
for p in range(n):
    if not p in fin:
        o = a[p][0]
        if p == a[o][0]:
            q.append((p, o))
            fin += [p, o]

while q:
    print(q)
    day += 1
    pre_q = copy.deepcopy(q)
    q.clear()
    for (p, o) in pre_q:#pre_qの試合をして次の試合をqに入れる
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)

if all(map(len, a)):
    print(-1)
else:
    print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
day = 0
H = [0] * N
T = [i for i in range(N)]

while A != [[0]] * N:
  #print([[0]] * N)
  finish = [0] * N
  for i in T:
    x = A[i][0]
    #print(A, i)#
    if (A[x - 1][0] == i + 1) and (finish[i] == 0) and (finish[x - 1] == 0): #対戦可能な場合対戦。       x = A[i][0]
      A[i].pop(0)
      A[x - 1].pop(0)
      finish[i] = 1
      finish[x-1] = 1
      if len(A[i]) == 0:
        A[i].append(0)
        T.remove(i)
      if len(A[x-1]) == 0:
        A[x-1].append(0)
        T.remove(x-1)
        #print(A)
  day += 1
  #print(Q, A)
  #print(finish)
  if finish == H: #もし終わらないのに試合ができないなら-1で終了させる
    print("-1")
    quit()
  
print(day)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque as dq
from copy import deepcopy as dc
N = int(input())
e = dd(list)
for i in range(1, N + 1):
  e[i] = list(map(int, input().split()))
vis = [0] * (N + 1)
day = 1
Q = dq([i for i in range(1, N + 1)])

#print(e)
while day < N * (N - 1) // 2 and sum(vis) < N * (N - 1):
  Qtemp = dc(Q)
  for i in Qtemp:
    Q.popleft()
    if vis[i] >= N - 1:
      continue
    j = e[i][vis[i]]
    #print(i, j, vis[i], vis[e[j][vis[j]]])
    #print(vis)
    if i == e[j][vis[j]]:
      Q.append(i)
      Q.append(j)
      vis[i] += 1
      vis[j] += 1
    #print(vis)
  day += 1
print(day) if sum(vis) == N * (N - 1) else print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque as dq
from copy import deepcopy as dc
N = int(input())
e = dd(list)
for i in range(1, N + 1):
  e[i] = list(map(int, input().split()))
vis = [0] * (N + 1)
day = 1
Q = dq([i for i in range(1, N + 1)])

#print(e)
while day <= N * (N - 1) // 2 and sum(vis) < N * (N - 1):
  Qtemp = dc(Q)
  for i in Qtemp:
    Q.popleft()
    if vis[i] >= N - 1:
      continue
    j = e[i][vis[i]]
    #print(i, j, vis[i], vis[e[j][vis[j]]])
    #print(vis)
    if i == e[j][vis[j]]:
      Q.append(i)
      Q.append(j)
      vis[i] += 1
      vis[j] += 1
    #print(vis)
  day += 1
print(day) if sum(vis) == N * (N - 1) else print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from collections import deque as dq
from copy import deepcopy as dc
N = int(input())
e = dd(list)
for i in range(1, N + 1):
  e[i] = list(map(int, input().split()))
vis = [0] * (N + 1)
day = 1
Q = dq([i for i in range(1, N + 1)])

#print(e)
while day <= N * (N - 1) // 2 and sum(vis) < N * (N - 1):
  Qtemp = dc(Q)
  for i in Qtemp:
    Q.popleft()
    if vis[i] >= N - 1:
      continue
    j = e[i][vis[i]]
    #print(i, j, vis[i], vis[e[j][vis[j]]])
    #print(vis)
    if i == e[j][vis[j]]:
      Q.append(i)
      Q.append(j)
      vis[i] += 1
      vis[j] += 1
    print(vis)
  day += 1
print(day) if sum(vis) == N * (N - 1) else print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
import sys
import copy	

sys.setrecursionlimit(10000000)

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

g = defaultdict(list)
start = []
for i in range(n):
	for j in range(0, n-2):
		prv = (min(i, orders[i][j] - 1), max(i, orders[i][j] - 1))
		fwd = (min(i, orders[i][j + 1] - 1), max(i, orders[i][j + 1] - 1))
		g[prv].append(fwd)
		if j == 0:
			start.append(prv)

def dfs(cur, cnt, path):
	if cur in path:
		return -1
		sys.exit()
	path.append(cur)

	if len(g[cur]) == 0:
		return cnt
	if visited[cur] >= cnt:
		return visited[cur]
	else:
		visited[cur] = max([dfs(nxt, cnt + 1, path) for nxt in g[cur]])
		return visited[cur]


visited = defaultdict(int)
print(max([dfs(s, 1, []) for s in start]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC139 E

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [deque() for _ in range(n)]
for i in range(1,n+1):
    x = LI()
    for j in x:
        a[i-1].append((i,j))
ans = 0
s = time.time()
for j in range(n*(n-1)//2+1):
    check = [1]*n
    flg = False
    flg2 = False
    if time.time() - s > 1.5:
        for i in a:
            if len(i) != 0:
                print(-1)
                quit()
        print(n*(n-1)//2)
        quit()
    for i in range(n):
        if len(a[i]) == 0 or check[i] == 0:
            continue
        (x,y) = a[i].popleft()
        flg2 = True
        check[i] = 0
        if a[y-1][0] == (y,x) and check[y-1]:
            a[y-1].popleft()
            flg = True
            check[y-1] = 0
        else:
            a[i].appendleft((x,y))
    if flg:
        ans += 1
    if not flg2:
        print(ans)
        quit()
print(-1)

Submission status: Wrong Answer

Solution code:
# 愚直解

import sys
input = sys.stdin.readline

N = int(input())

A = [ [int(i) for i in input().split() ] for j in range(N) ]

for i in range(N):
	A[i].append(-1)
	A[i] = [int(s) for s in A[i]]



# Hはリスト
def search(H):
	list=[]
	counter = 0
	for i in range(N):
		if H.count(i+1) > 0:

			l = [k for k, x in enumerate(H) if x == i+1]
			
			# lengh_l = len(l)

			# for j in range(lengh_l):
			# 	if H[i] == l[j]+1 and l[j] > i:

			if l.count(H[i] -1) > 0 and i < H[i] - 1:
				ans = H[i] - 1 


				list.append((i,ans))
				counter += 1
				

	list.append(counter)
	return list

depth_col = [0]*N

look = []

for _ in range(N):
	look.append(A[_][0])

counter = 0

while min(depth_col) < N-1:
	result = search(look)

	if result[-1] == 0:
		counter = -1
		break
	else:
		lengh_search = len(result)-1
		for j in range(lengh_search):
			x = result[j][0]
			y = result[j][1]
			print(x)
			print(y)
			depth_col[x] += 1
			depth_col[y] += 1

			a = depth_col[x]
			b = depth_col[y]
			look[x] = A[x][a]
			look[y] = A[y][b]

		counter += 1

if counter < 0:
	print(-1)
else:
	print(counter)