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:
N = int(input())
mat = []
for i in range(N):
  mat.append(list(map(int,input().split())))

def seek(p1,p2):
  shiai = mat[p2-1]
  for tap in zip(range(len(shiai)),shiai):
    if tap[1]==p1:
      return tap[0]
  return -1

f = False
cnt = 0
for p1 in range(1,N+1):
  for ndx,p2 in zip(range(N-1),mat[p1-1]):
    pt1 = p1
    pt2 = p2
    ndx0 = ndx
    while(True):
      t_ndx = seek(pt1,pt2)
      #print("pt1:{} pt2:{} ndx0:{} ndx:{} t_ndx:{}".format(pt1,pt2,ndx0,ndx,t_ndx))
      if pt2 == p1 and t_ndx >ndx0:
         f = True
         #print("FLASE!! cannot arrange")
         break
      if ndx < t_ndx:
        cnt+=1
        ndx = t_ndx -1
        pt3 = mat[pt2-1][ndx]
        pt1 = pt2
        pt2 = pt3
      else:break
    if f:break
  if f: break
if f:print(-1)
else: print(N - 1 + cnt//2)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)

D=[[]for i in range(N**2+1)]

L=[0 for i in range(N+1)]
E=dict()
cnt=0
for i in range(1,N):
    if A[A[i][0]][0]==i and i not in E and A[i][0] not in E:
        D[i].append((i,A[i][0]))
        L[i]+=1
        L[A[i][0]]+=1
        E[i]=1
        E[A[i][0]]=1
        cnt+=1
#print(L)
#print(D)

for i in range(1,N**2+1):
    if len(D[i])==0:
        if cnt==N*(N-1)//2:
            print(i-1)
        else:
            print(-1)
        #print(E)
        #print(D)
        exit()
    else:
        E=[]
        E=dict()
        for j in D[i]:
            for k in range(2):
                T=A[j[k]][L[j[k]]]
                if A[T][L[T]]==j[k] and j[k] not in E and T not in E:
                    D[i+1].append((j[k],T))
                    L[j[k]]+=1
                    L[T]+=1
                    E[j[k]]=1
                    E[T]=1
                    cnt+=1

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)

D=[[]for i in range(N**2+1)]

L=[0 for i in range(N+1)]

for i in range(1,N):
    if A[A[i][0]][0]==i and i<A[i][0]:
        D[i].append((i,A[i][0]))
        L[i]+=1
        L[A[i][0]]+=1
#print(L)
#print(D)

for i in range(1,N**2+1):
    if len(D[i])==0:
        if min(L[1:])==N-1:
            print(i-1)
        else:
            print(-1)
        exit()
    else:
        E=[]
        E=dict()
        for j in D[i]:
            for k in range(2):
                T=A[j[k]][L[j[k]]]
                if A[T][L[T]]==j[k] and j[k] not in E and T not in E:
                    D[i+1].append((j[k],T))
                    L[j[k]]+=1
                    L[T]+=1
                    E[j[k]]=1
                    E[T]=1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if not r:
        print(_)
        break
    ne = set()
    flag = True
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j].pop(0)
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
  
    node_from = dict()
    node_to = dict()
    
    for i in range(1, N + 1):
        a = [int(b) for b in input().split()]
        for j in range(N - 2):
            if (min(i, a[j]), max(i, a[j])) not in node_to: 
                node_to[(min(i, a[j]), max(i, a[j]))] = set()
            if (min(i, a[j]), max(i, a[j])) not in node_from: node_from[(min(i, a[j]), max(i, a[j]))] = 0
            node_to[(min(i, a[j]), max(i, a[j]))] |= {(min(i, a[j+1]), max(i, a[j+1]))}

            if (min(i, a[j+1]), max(i, a[j+1])) not in node_from: node_from[(min(i, a[j+1]), max(i, a[j+1]))] = 0
            node_from[(min(i, a[j+1]), max(i, a[j+1]))] += 1

        if (min(i, a[N-2]), max(i, a[N-2])) not in node_to: node_to[(min(i, a[N-2]), max(i, a[N-2]))] = set()
        
    zero_in = deque()
    for node in node_from:
        if node_from[node] == 0: zero_in.append((node, 1))
    #print(node_from)
    #print(node_to)
    ans = []
    max_day = 0
    while zero_in:
        now_node, day = zero_in.popleft()
        ans.append(now_node)
        max_day = max(max_day, day)
        for next_node in node_to[now_node]: 
            node_from[next_node] -= 1
            if node_from[next_node] == 0: zero_in.append((next_node, day + 1))

    #print(ans)

    if len(ans) > N * (N - 1) // 2 or max_day == 0: print(-1)
    else: print(max_day)

    return 0

if __name__ == "__main__": solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
flag = True
l = []
r = set(list(range(n)))
N = n*(n-1) // 2 + 1
for _ in range(N):
    if l and not r:
        print(ans)
        break
    ne = set()
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    l = list(ne)
    for j in l:
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
        ans += 1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
flag = True
l = []
r = set(list(range(n)))
N = n*(n-1) // 2
for _ in range(N):
    if l and not r:
        print(ans)
        break
    ne = set()
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    l = list(ne)
    for j in l:
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
        ans += 1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = 0
flag = True
r = set(list(range(n)))
while True:
    ne = set()
    if not r:
        print(ans)
        break
    for j in r:
        if not a[j]:
            continue
        c = a[j][0]
        if c == "-":
            continue
        if j + 1 == a[c-1][0]:
            a[j][0] = "-"
            a[c-1][0] = "-"
            ne.add(j)
            ne.add(c-1)
    for j in list(ne):
        if a[j]:
            if a[j][0] == "-":
                a[j] = a[j][1:]
                flag = False
                if not a[j]:
                    ne.remove(j)
    if flag:
        print(-1)
        break
    else:
        r = ne
        ans += 1

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

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

node_id_db = [[0] * (N+1) for _ in range(N + 1)]
v = 0
for i in range(N):
    for j in range(i + 1, N):
        node_id_db[i][j] = v
        v += 1


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


start_nodes = []
edges = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
    Ai = A[i]
    from_id = get_node_id(i, Ai[0] - 1, node_id_db)
    if Ai[1] > i:
        start_nodes.append(from_id)
    for j in range(1, N - 1):
        to_id = get_node_id(i, Ai[j] - 1, node_id_db)
        edges[from_id].append(to_id)
        from_id = to_id

dp = [-1 for _ in range(N * (N - 1) // 2)]
UNVISITED = -1
PROCESSING = 0


def dfs(node_id):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = PROCESSING
    result = 1
    for n in edges[node_id]:
        t = dfs(n)
        if t == PROCESSING:  # looped
            print(-1)
            exit()
        result = max(result, t + 1)
    dp[node_id] = result
    return result


print(max(dfs(n) for n in start_nodes))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[[0]*n]*n
l=[]
l2=[]

for i in range(n):
  a[i]=[int(x)-1 for x in input().split()]

for i in range(n):
  j=a[i][0]
  if i<j:
    if i==a[j][0]:
      l.append(i)
      l.append(j)

t = 0 if len(l)>0 else -1

while len(l)>0:
  l2=l
  l=[]
  t+=1
  for i in range(len(l2)):
    j = l2[i]
    a[j].pop(0)
  for i in range(len(l2)):
    j = l2.pop(0)
    if len(a[j]):
      k=a[j][0]
      if j<k:
        if j==a[k][0]:
          l.append(j)
          l.append(k)
print(t)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[[0]*n]*n
l=[]
l2=[]

for i in range(n):
  a[i]=[int(x)-1 for x in input().split()]

for i in range(n):
  j=a[i][0]
  if i<j:
    if i==a[j][0]:
      l.append(i)
      l.append(j)

t = 0 if len(l)>0 else -1

while len(l)>0:
  l2=l
  l=[]
  t+=1
  for i in range(len(l2)):
    j = l2.pop(0)
    a[j].pop(0)
    if len(a[j]):
      k=a[j][0]
      if j==a[k][0]:
        l.append(j)
        l.append(k)
print(t)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = [deque(LI()) for _ in range(n)]

match_set = set()
for i in range(n):
    if i in match_set:
        continue
    if L[L[i][0] - 1][0] - 1 == i:
        k = L[i].popleft() - 1
        L[k].popleft()
        match_set.add(i)
        match_set.add(k)


pre_match_set = match_set


cnt = 1
while pre_match_set:
    flag = 0
    match_set = set()
    for j in pre_match_set:
        if j in match_set:
            continue
        if L[j] and L[L[j][0] - 1] and L[L[j][0] - 1][0] - 1 == j:
            flag = 1
            l = L[j].popleft() - 1
            L[l].popleft()
            match_set.add(j)
            match_set.add(l)
    pre_match_set = match_set
    if flag:
        cnt += 1




if any([i for i in L]):
    print(-1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = [deque(LI()) for _ in range(n)]

match_set = set()
for i in range(n):
    if i in match_set:
        continue
    if L[L[i][0] - 1][0] - 1 == i:
        k = L[i].popleft() - 1
        L[k].popleft()
        match_set.add(i)
        match_set.add(k)


pre_match_set = match_set


flag = 1
cnt = 1
while flag:
    cnt += 1
    match_set = set()
    flag = 0
    for j in pre_match_set:
        if j in match_set:
            continue
        if L[j] and L[L[j][0] - 1] and L[L[j][0] - 1][0] - 1 == j:
            flag = 1
            l = L[j].popleft() - 1
            L[l].popleft()
            match_set.add(j)
            match_set.add(l)
    pre_match_set = match_set




if any([i for i in L]):
    print(-1)
else:
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N = int(input())

AA = [[x-1 for x in inpl()][::-1] for _ in range(N)]

ans = 1
while True:
    updated = 0
    checked = [0] * N
    for i in range(N):
        if checked[i] or len(AA[i]) == 0:
            continue
        j = AA[i][-1]
        if len(AA[i]) and len(AA[j]) and AA[j][-1] == i:
            checked[i] = 1
            checked[j] = 1
            updated = 1
            AA[i].pop()
            AA[j].pop()
    if not updated:
        break
    ans += 1

if any(map(len, AA)):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if i<j:
    return
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
es = [[]*(N-1) for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if i<j:
    return
  if es[j]==[]:
    return
  if es[j][-1]==i:
    i = es[j].pop()
    j = es[i].pop()
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 1
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
es = [[]*(N-1) for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    i = es[j].pop()
    j = es[i].pop()
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 1
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)

Submission status: Wrong Answer

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

day = 0
match = 0
while match<=N*(N-1)//2:
    checkes = [False]*N
    check = False
    for n in range(N):
        jibun = n
        jibun_ind = indexes[jibun]
        if jibun_ind>=N-1:
            continue
        aite = A[jibun][jibun_ind] - 1
        aite_ind = indexes[aite]
        aite_no_aite = A[aite][aite_ind] - 1

        if not checkes[jibun] and not checkes[aite] and jibun == aite_no_aite:
            checkes[jibun] = True
            checkes[aite] = True
            indexes[jibun] += 1
            indexes[aite] += 1
            match += 1
            check = True
    if not check:
        day = -1
        break
    day += 1
print(day)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque
from heapq import heappush,heappop,heapify

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)
BEGIN=set()

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y=A[j]
		y_next=A[j+1]
		#print x,y,x_next,y_next
		if x>y: x,y=y,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y)].add((x_next,y_next))

		if j==0:
			BEGIN.add((x,y))

hq=[]

for x,y in BEGIN:
	if IN[(x,y)]==0:
		heappush(hq, (1,x,y))


DAY=defaultdict(lambda: 1)	#距離

ans=-1
while hq:
	cost,fro_x,fro_y=heappop(hq)
	fro=(fro_x,fro_y)
	for to in AL[fro]:
		IN[to]-=1
		alt=cost+1
		if IN[to]==0:
			ans=max(ans,alt)
			DAY[to]=alt
			heappush(hq,(alt,to[0],to[1]))

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque
from heapq import heappush,heappop,heapify

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)
BEGIN=set()

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y=A[j]
		y_next=A[j+1]
		#print x,y,x_next,y_next
		if x>y: x,y=y,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y)].add((x_next,y_next))

		if j==0:
			BEGIN.add((x,y))

hq=[]

for x,y in BEGIN:
	if IN[(x,y)]==0:
		heappush(hq, (1,x,y))


DAY=defaultdict(lambda: 1)	#距離

ans=-1
while hq:
	cost,fro_x,fro_y=heappop(hq)
	fro=(fro_x,fro_y)
	for to in AL[fro]:
		IN[to]-=1
		alt=DAY[fro]+1
		if DAY[to]<alt and IN[to]==0:
			ans=max(ans,alt)
			DAY[to]=alt
			heappush(hq,(alt,to[0],to[1]))

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)
BEGIN=set()

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y=A[j]
		y_next=A[j+1]
		#print x,y,x_next,y_next
		if x>y: x,y=y,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y)].add((x_next,y_next))

		if j==0:
			BEGIN.add((x,y))


q=deque()

for x,y in BEGIN:
	if IN[(x,y)]==0:
		q.append((x,y))


DAY=defaultdict(lambda: 1)	#距離

ans=-1
cnt=0
while q and cnt<100000:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=alt
			q.append((to[0],to[1]))
	cnt+=1

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)
BEGIN=set()

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y=A[j]
		y_next=A[j+1]
		#print x,y,x_next,y_next
		if x>y: x,y=y,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y)].add((x_next,y_next))

		if j==0:
			BEGIN.add((x,y))


q=deque()

for x,y in BEGIN:
	if IN[(x,y)]==0:
		q.append((x,y))


DAY=defaultdict(lambda: 1)	#距離

ans=-1
cnt=0
while q and cnt<1000000:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=alt
			q.append((to[0],to[1]))
	cnt+=1

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)


for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y_now=A[j]
		y_next=A[j+1]
		#print x,y_now,x_next,y_next
		if x>y_now: x,y_now=y_now,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y_now)].add((x_next,y_next))

q=deque()

for i in range(1,N+1):
	for j in range(i+1,N+1):
		if IN[(i,j)]==0:
			q.append((i,j))

DAY=defaultdict(lambda: 1)	#距離

ans=-1
cnt=0
while q and cnt<1000000:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=alt
			q.append((to[0],to[1]))
	cnt+=1

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)


for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y_now=A[j]
		y_next=A[j+1]
		#print x,y_now,x_next,y_next
		if x>y_now: x,y_now=y_now,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y_now)].add((x_next,y_next))

q=deque()

for i in range(1,N+1):
	for j in range(i+1,N+1):
		if IN[(i,j)]==0:
			q.append((i,j))

DAY=defaultdict(lambda: 1)	#距離

ans=-1
cnt=0
while q and cnt<100000:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			ans=max(ans,alt)
			DAY[to]=alt
			q.append((to[0],to[1]))
	cnt+=1

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)


for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y_now=A[j]
		y_next=A[j+1]
		#print x,y_now,x_next,y_next
		if x>y_now: x,y_now=y_now,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y_now)].add((x_next,y_next))

q=deque()

for i in range(1,N+1):
	for j in range(i+1,N+1):
		if IN[(i,j)]==0:
			q.append((i,j))


DAY=defaultdict(lambda: 1)	#距離
Visit=defaultdict(lambda: None)

while q:
	fro=q.pop()
	for to in AL[fro]:
		if Visit[to] is None :
			DAY[to]=max(DAY[to],DAY[fro]+1)
			Visit=defaultdict(lambda: None)
			Visit[to]=1
			q.append((to[0],to[1]))

try:
	print max(DAY.values())
except:
	print -1

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, visited, calculated, dp, to):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v] = True
  dp[v] = 1
  for u in to[v]:
    res = dfs(u, visited, calculated, dp, to)
    if res == -1:
      return -1
    dp[v] = max(dp[v], res + 1)
  calculated[v] = True
  return dp[v]

def toId(i, j, id):
  if i > j:
    i, j = j, i
  return id[i][j]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id = [[0] * N for _ in range(N)]

  visited = [False] * (N * (N - 1) // 2)
  calculated = [False] * (N * (N - 1) // 2)
  dp = [0] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(N):
      if i >= j:
        continue
      id[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  ans = 0
  for i in range(N * (N - 1) // 2):
    res = dfs(i, visited, calculated, dp, to)
    if res == -1:
      print('-1')
      exit()
    ans = max(ans, res)
  print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
C=defaultdict(lambda: 0)

Now=[ 0 for _ in range(N+1)]
game=set()
next_game=set()

for i in range(1,N+1):
	a=i
	b=A[i][0]
	if a>b: a,b=b,a
	next_game.add((a,b))

day=1

game=next_game

#for _ in range(5):
while game:
	next_game=set()

	for x,y in game:
		now_x=Now[x]
		now_y=Now[y]

		xopp=A[x][now_x]
		yopp=A[y][now_y]

		if (x,y)==(yopp,xopp):
			if now_x<N-2:
				now_x+=1
				Now[x]=now_x
				x_nextopp=A[x][now_x]
				if x_nextopp<x: x,x_nextopp=x_nextopp,x
				next_game.add((x,x_nextopp))

			if now_y<N-2:
				now_y+=1
				Now[y]=now_y
				y_nextopp=A[y][now_y]
				if y_nextopp<y: y,y_nextopp=y_nextopp,y
				next_game.add((y,y_nextopp))
	game=next_game
	day+=1


print day

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
C=defaultdict(lambda: 0)

Now=[ 0 for _ in range(N+1)]
game=set()
next_game=set()

for i in range(1,N+1):
	a=i
	b=A[i][0]
	if a>b: a,b=b,a
	next_game.add((a,b))

day=1

game=next_game

#for _ in range(5):
while game:
	next_game=set()

	for x,y in game:
		now_x=Now[x]
		now_y=Now[y]

		xopp=A[x][now_x]
		yopp=A[y][now_y]

		if (x,y)==(yopp,xopp):
			if now_x<N-2:
				now_x+=1
				Now[x]=now_x
				x_nextopp=A[x][now_x]
				if x_nextopp<x: x,x_nextopp=x_nextopp,x
				next_game.add((x,x_nextopp))

			if now_y<N-2:
				now_y+=1
				Now[y]=now_y
				y_nextopp=A[y][now_y]
				if y_nextopp<y: y,y_nextopp=y_nextopp,y
				next_game.add((y,y_nextopp))
	game=next_game
	day+=1


for i in range(1,N+1):
	if Now[i] != N-2:
		print -1
		quit()
else:
	print day

Submission status: Wrong Answer

Solution code:
N = int(input())
dic = {}

for i in range(N):
  dic[i] = [int(i)-1 for i in input().split()][::-1]

used = [0]*N
stuck = []
for i in range(N):
  if used[i]==1:
    continue
  x = dic[i][-1]
  if dic[x][-1]==i and used[x]==0:
    b = dic[i].pop()
    a = dic[x].pop()
    used[a] = 1
    used[b] = 1
    stuck += [a,b]

if stuck==[]:
  print(-1)
else:
  count = 1
  while True:
    used = [0]*N
    nstuck= []
    for e in stuck:
      for x in dic[e]:
        if dic[x][-1]==e and used[x]==0:
          x = dic[e].pop()
          e = dic[x].pop()
          used[e] = 1
          used[x] = 1
          nstuck += [e,x]
          break
    if nstuck==[]:
      print(-1)
      break
    count += 1
    stuck = nstuck
    for k in dic.keys():
      if dic[k]:
        break
    else:
      print(count)
      break

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict,deque
N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N)]

Now=[0 for _ in range(N+1)]

day=1

q=deque(range(1,N+1))

Visit=defaultdict(lambda: None) 
flag=False

while q:
	me=q.popleft()
	now=Now[me]
	if now<N-1:	#現在値がN-1になっていたら、もうアガリ
		opponent=A[me][now]
		opponentnow=Now[opponent]
		opp_of_opp=A[opponent][opponentnow]

		if me==opp_of_opp:
			if Visit[me]==1 or Visit[opponent]==1:
				day+=1
				Visit=defaultdict(lambda: None) 

			flag=True	#前進フラグ　1回前よりも状態が進めばTrueになる
			now+=1
			opponentnow+=1
			Now[me]=now
			Now[opponent]=opponentnow
			Visit[me]=1
			Visit[opponent]=1

			q.append(me)
			q.append(opponent)
else:
		if not flag:
			print -1
			quit()	

print day

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from collections import deque

N=input()
AL=defaultdict(lambda: [])	#隣接リスト
D=defaultdict(lambda: 0)	#距離
IN=defaultdict(lambda: 0) 	#入次数

for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(1,N-1):
		before_n=i+1
		before_a=A[j-1]
		n=i+1
		a=A[j]
		if before_n>before_a: before_n,before_a=before_a,before_n
		if n>a: n,a=a,n
		AL[(before_n,before_a)].append((n,a))
		IN[(n,a)]+=1


q=deque()
for i in range(1,N+1):
	for j in range(i+1,N+1):
		if IN[i,j]==0:
			q.append((i,j))

if not q:
	print -1
	quit()

fro=q
while q:
	fro=q.popleft()
	for to in AL[fro]:
		IN[to]-=1
		D[to]=max(D[to],D[fro]+1)
		if IN[to]==0:
			q.append(to)

print max(D.values())+1

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
log = {}
es = defaultdict(list)
for i in range(1,N+1):
  for j in range(1,i):
    log[(j,i)] = True
    
for i in range(1,N+1):
  a = [int(i) for i in input().split()]
  for j in range(1,N-1):
    px = min(i,a[j-1])
    py = max(i,a[j-1])
    x = min(i,a[j])
    y = max(i,a[j])
    es[(px,py)] += [(x,y)]
    log[(x,y)] = False

stuck = []
for k in log.keys():
  if log[k]:
    stuck += [tuple(k)]
    log[k] = 1
  else:
    log[k] = -1

m = 0
if stuck==[]:
  print(-1)
else:
  while stuck:
    if m>N*(N-1)//2:
      print(-1)
      break
    e = stuck.pop()
    ls = es[e]
    for l in ls:
      if log[l]<log[e]+1:
        log[l] = log[e]+1
        if log[l]>m:
          m = log[l]
          stuck += [l]
  else:
    print(m)