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 collections import defaultdict
N = int(input())
L = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]


def make_hash(a, b):
    a, b = min(a, b), max(a, b)
    return N*a+b


def un_hash(n):
    a = n//N
    b = n % N
    return a, b


from_to = defaultdict(lambda: set())
pointed = defaultdict(int)
pointing = defaultdict(int)

for i in range(N):
    for node_from, node_to in zip(L[i], L[i][1:]):
        from_to[make_hash(i, node_from)].add(make_hash(i, node_to))
        pointed[make_hash(i, node_to)] += 1
        pointing[make_hash(i, node_from)] += 1

START = set()
DST = set()
for i in range(N):
    for j in range(i+1, N):
        h = make_hash(i, j)
        pointed_i = pointed[h]
        pointing_i = pointing[h]
        if pointed_i == 0:
            START.add(h)
        if pointing_i == 0:
            DST.add(h)
if len(START) == 0 or len(DST) == 0:
    print(-1)

else:
    Q = [[v, 1] for v in START]
    dist = 1
    while Q:
        q, d = Q.pop()
        for nex in from_to[q]:
            Q.append([nex, d+1])
            dist = d+1
    print(dist)

Submission status: Wrong Answer

Solution code:
N = int(input())
G = {(i,j):[[],[]] for i in range(1,N) for j in range(i+1,N+1)}
for i in range(1,N+1):
    A = list(map(int,input().split()))
    for j in range(1,N-1):
        i1 = i
        a = A[j-1]
        if a<i1:
            i1,a = a,i1
        i2 = i
        b = A[j]
        if i2>b:
            i2,b = b,i2
        G[(i1,a)][1].append((i2,b))
        G[(i2,b)][0].append((i1,a))
G1 = sorted([[a,len(G[a][0])] for a in G],key=lambda x:x[1])
D = []
d = []
for i in range(len(G1)):
    if G1[i][1]==0:
        d.append(G1[i][0])
    else:break
if len(d)>0:
    D.append(d)
while d:
    d1 = D[-1]
    d = []
    for a in d1:
        for b in G[a][1]:
            G[b][0].remove(a)
            if len(G[b][0])==0 and b not in d:
                d.append(b)
        del G[a]
    if len(d)>0:
        D.append(d)
if len(D)==0:
    print(-1)
else:
    print(len(D))

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
MATCHES = [[(0,0) for _ in range(N-1)] for _ in range(N)]

for i in range(N):
    lis = LI()
    for j in range(N-1):
        if i+1 < lis[j]:
            MATCHES[i][j] = (i+1, lis[j])
        else:
            MATCHES[i][j] = (lis[j], i+1)

CONT = True
IDXS=[0]*N
days = 0
ST=set()

next_check = range(N)
while CONT:
    cont = False
    _next_check = []
    for i in next_check:
        if IDXS[i] < N-1:
            pair = MATCHES[i][IDXS[i]]
            p, q = pair
            if pair in ST:
                ST.remove(pair)
                print("{}: {}".format(days, pair))
                if IDXS[i] < N-1:
                    IDXS[p-1] += 1
                    IDXS[q-1] += 1
                    cont = True
                    _next_check.append(p-1)
                    _next_check.append(q-1)
            else:
                ST.add(pair)
    next_check = _next_check
    CONT = cont
    days += cont

# print(IDXS)
if sum(IDXS) == N*(N-1):
    print(days)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
MATCHES = [[(0,0) for _ in range(N-1)] for _ in range(N)]

for i in range(N):
    lis = LI()
    for j in range(N-1):
        if i+1 < lis[j]:
            MATCHES[i][j] = (i+1, lis[j])
        else:
            MATCHES[i][j] = (lis[j], i+1)

ST=set()
CONT = True
IDXS=[0]*N
DONE=[False]*N
days = 0
while CONT:
    cont = False
    for i in range(N): DONE[i] = False
    for i in range(N):
        if IDXS[i] < N-1 and not DONE[MATCHES[i][IDXS[i]][0]-1] and not DONE[MATCHES[i][IDXS[i]][1]-1]:
            if MATCHES[i][IDXS[i]] in ST:

                ST.remove(MATCHES[i][IDXS[i]])
                DONE[MATCHES[i][IDXS[i]][0]-1] = True
                DONE[MATCHES[i][IDXS[i]][1]-1] = True
                # print("{}: {}".format(days, MATCHES[i][IDXS[i]]))
                if IDXS[i] < N-1:
                    IDXS[i] += 1
                    cont = True
            else:
                ST.add(MATCHES[i][IDXS[i]])
                IDXS[i] += 1
    # print(ST)
    CONT = cont
    days += cont


# print(IDXS)
if sum(IDXS) == N*(N-1):
    print(days)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
MATCHES = [[(0,0) for _ in range(N-1)] for _ in range(N)]

for i in range(N):
    lis = LI()
    for j in range(N-1):
        if i+1 < lis[j]:
            MATCHES[i][j] = (i+1, lis[j])
        else:
            MATCHES[i][j] = (lis[j], i+1)

ST=set()
CONT = True
IDXS=[0]*N
days = 0
while CONT:
    cont = False
    for i in range(N):
        if IDXS[i] < N-1:
            if MATCHES[i][IDXS[i]] in ST:
                ST.remove(MATCHES[i][IDXS[i]])
                if IDXS[i] < N-1:
                    IDXS[i] += 1
                    cont = True
            else:
                ST.add(MATCHES[i][IDXS[i]])
                IDXS[i] += 1
    # print(ST)
    CONT = cont
    days += 1

if sum(IDXS) == N*(N-1):
    print(days)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
#sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = [[-1] + [int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]
 
if N == 3:
  print(1)
  
A.append([-1])
 
def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        if A[n][-1] != -1:
            cand1.add(A[n][-1])
    return len(can_use),cand1

answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x,cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

def dfs(path, visited, i, j, memo = dict()):
    if (i, j) not in path: return 1
    if (i, j) in memo: return memo[(i, j)]
    maxlength = 0
    for ni, nj in path[(i, j)]:
        if (ni, nj) in visited: 
            memo[(i, j)] = -1
            return -1
        else:
            nl = dfs(path, visited | {(i, j)}, ni, nj, memo)
            if nl == -1: return -1
            else: maxlength = max(maxlength, nl)
            
        memo[(i, j)] = maxlength + 1
        return maxlength + 1

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

    memo = dict()
    print(dfs(path, set(), -1, -1, memo))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

def dfs(path, visited, i, j, memo = dict()):
    if (i, j) not in path: return 1
    if (i, j) in memo: return memo[(i, j)]
    maxlength = 0
    for ni, nj in path[(i, j)]:
        if (ni, nj) in visited: return -1
        else:
            nl = dfs(path, visited | {(i, j)}, ni, nj, memo)
            if nl == -1: return -1
            else: maxlength = max(maxlength, nl)

        return maxlength + 1

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

    memo = dict()
    print(dfs(path, set(), -1, -1, memo))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N=int(input())
# 試合ペアを管理
games=[[[] for j in range(N)] for i in range(N)]

# 自分の直前に実施されるべき試合がいくつあるかを管理（試合をしたら1減らす）
bef=[[0 for j in range(N)] for i in range(N)]
for i in range(N):
  for j in range(N):
    if i>=j:
      games[i][j]=None
      bef[i][j]=-1

for i in range(N):
  a=list(map(int,input().split()))
  for j in range(len(a)-1):
    me=i
    you=a[j]-1
    nex=a[j+1]-1
    games[min(me,you)][max(me,you)].append([min(me,nex),max(me,nex)])
    bef[min(me,nex)][max(me,nex)]+=1
    
#    games[i][a[j]-1]=[i,a[j+1]-1] #次の試合
#    bef[i][a[j+1]-1]+=1
    
#for i in range(len(games)):
#  print(games[i])
  
#for i in range(len(bef)):
#  print(bef[i])

# 始点となる試合（befが0）をstackに入れる
stack=[]
for i in range(N):
  for j in range(N):
    if bef[i][j]==0:
      stack.append([i,j,1])

ans=0
while stack:
  node=stack.pop()
  y=node[0]
  x=node[1]
  days=node[2]
  #print("days:",days,"y:",y,"x:",x)
  bef[y][x]-=1
  if bef[y][x]>0:
    continue
  if days>ans:
    ans=days
  # そこまでに消化する試合が全ておわっている。=次に行ける
  game=games[y][x]
  for g in game:
    stack.append([g[0],g[1],days+1])


if ans==0:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
print("practice")

from collections import deque

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

check = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
q = deque((i + 1, a.pop()) for i, a in enumerate(A))
day = 0
#print("A:", A)
#print("q:", q)

while q:
  day += 1
  r = deque()
  while q:
    x, y = q.popleft()

    if x < y:
      x, y = y, x
    check[x][y] += 1 # この管理方法思いつかなかった。
    if check[x][y] >= 2:
      check[x][y] = 0
      if A[x - 1]:
        r.append((x, A[x - 1].pop()))
      if A[y - 1]:
        r.append((y, A[y - 1].pop()))
  q = r

if sum(map(len, A)):
  print(-1)
else:
  print(day)

Submission status: Wrong Answer

Solution code:
print("reference: https://atcoder.jp/contests/abc139/submissions/7282652")

from collections import deque
 
N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)] # 逆順にするとpopの計算量がいらない。
print("A:", A)

check = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
q = deque([(i + 1, a.pop()) for i, a in enumerate(A)])
print("A:", A)
print("q:", q)

day = 0

while q:
    day += 1
    r = deque()
    while q:
        x, y  = q.popleft() # x:戦う元、y:戦う先。
        if x > y:
            x, y = y, x
        check[x][y] += 1
        if check[x][y] >= 2: # 2つ目で管理するのはうまい。
            check[x][y] -= 2
            if A[x - 1]:
                r.append((x, A[x - 1].pop())) # 右から出すと計算量削減。次の組み合わせを。
            if A[y - 1]:
                r.append((y, A[y - 1].pop())) # 右から出すと計算量削減。次の組み合わせを。
    q = r

if sum(map(len, A)):
    print(-1)
else:
    print(day)

Submission status: Wrong Answer

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

select=[list(range(n))]

day=0
mat=0
for _ in range(int(n*(n-1)/2)):
    nex=[]
    for x in select[day]:
        if len(match[x]) != 0 and not match[x][0]-1 in nex and match[match[x][0]-1][0] == (x+1):
            nex.append(x)
            nex.append(match[x][0]-1)
            match[match[x][0]-1].pop(0)
            match[x].pop(0)
            mat+=1

    if len(nex) == 0 and mat==int(n*(n-1)/2):
        break
    
    if len(nex) == 0:
        print(-1)
        exit()

    select.append(nex)
    day+=1

print(day)

Submission status: Wrong Answer

Solution code:
import sys
import random
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            if min(i,x)*10**3+max(i,x) in d:
                if prev!=-1:
                    edge1[prev].append(d[min(i,x)*10**3+max(i,x)])
                    edge2[d[min(i,x)*10**3+max(i,x)]].append(prev)
            else:
                d[min(i,x)*10**3+max(i,x)]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
            prev=d[min(i,x)*10**3+max(i,x)]
    stack=[]
    days=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            stack.append(i)
            days[i]=1
    for i in range(len(stack)):
        r=random.randrange(len(stack))
        stack[i],stack[r]=stack[r],stack[i]
    if stack:
        for _ in range(10**7):
            v=stack.pop()
            for x in edge1[v]:
                if days[x]<days[v]+1:
                    days[x]=days[v]+1
                    stack.append(x)
            if not stack:
                print(max(days))
                exit()
    max_days=max(days)
    if max_days>N*(N-1)//2:
        print(-1)
    else:
        print(max_days)
        

    

        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import random
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            if min(i,x)*10**3+max(i,x) in d:
                if prev!=-1:
                    edge1[prev].append(d[min(i,x)*10**3+max(i,x)])
                    edge2[d[min(i,x)*10**3+max(i,x)]].append(prev)
            else:
                d[min(i,x)*10**3+max(i,x)]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
            prev=d[min(i,x)*10**3+max(i,x)]
    queue=deque()
    days=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            queue.append(i)
            days[i]=1
    for i in range(len(queue)):
        r=random.randrange(len(queue))
        queue[i],queue[r]=queue[r],queue[i]
    if queue:
        for _ in range(10**6):
            v=queue.popleft()
            for x in edge1[v]:
                if days[x]<days[v]+1:
                    days[x]=days[v]+1
                    queue.append(x)
            if not queue:
                print(max(days))
                exit()
    max_days=max(days)
    if max_days>N*(N-1)//2-1:
        print(-1)
    else:
        print(max_days)
        

    

        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            if min(i,x)*10**3+max(i,x) in d:
                if prev!=-1:
                    edge1[prev].append(d[min(i,x)*10**3+max(i,x)])
                    edge2[d[min(i,x)*10**3+max(i,x)]].append(prev)
            else:
                d[min(i,x)*10**3+max(i,x)]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
            prev=d[min(i,x)*10**3+max(i,x)]
    queue=deque()
    days=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            queue.append(i)
            days[i]=1
    if queue:
        for _ in range(8*10**6):
            v=queue.popleft()
            for x in edge1[v]:
                if days[x]<days[v]+1:
                    days[x]=days[v]+1
                    queue.append(x)
            if not queue:
                print(max(days))
                exit()
    print(-1)
        

    

        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            if min(i,x)*10**3+max(i,x) in d:
                if prev!=-1:
                    edge1[prev].append(d[min(i,x)*10**3+max(i,x)])
                    edge2[d[min(i,x)*10**3+max(i,x)]].append(prev)
            else:
                d[min(i,x)*10**3+max(i,x)]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
            prev=d[min(i,x)*10**3+max(i,x)]
    stack=[]
    days=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            stack.append(i)
            days[i]=1
    if stack:
        for _ in range(10**7):
            v=stack.pop()
            for x in edge1[v]:
                if days[x]<days[v]+1:
                    days[x]=days[v]+1
                    stack.append(x)
            if not stack:
                print(max(days))
                exit()
    print(-1)
        

    

        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    d={}
    c=0
    edge1=[[] for _ in range(N*(N-1)//2)]
    edge2=[[] for _ in range(N*(N-1)//2)]
    for i in range(N):
        l=list(map(lambda x: int(x)-1,input().split()))
        prev=-1
        for x in l:
            if min(i,x)*10**3+max(i,x) in d:
                if prev!=-1:
                    edge1[prev].append(d[min(i,x)*10**3+max(i,x)])
                    edge2[d[min(i,x)*10**3+max(i,x)]].append(prev)
            else:
                d[min(i,x)*10**3+max(i,x)]=c
                if prev!=-1:
                    edge1[prev].append(c)
                    edge2[c].append(prev)
                c+=1
            prev=d[min(i,x)*10**3+max(i,x)]
    stack=[]
    d=[-1]*(N*(N-1)//2)
    for i,l in enumerate(edge2):
        if not l:
            stack.append(i)
            d[i]=1
    if stack:
        for _ in range(10**7):
            v=stack.pop()
            for x in edge1[v]:
                d[x]=max(d[x],d[v]+1)
                stack.append(x)
            if not stack:
                print(max(d))
                exit()
    print(-1)
        

    

        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from collections import deque

def main():

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from collections import deque

def main():

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

from collections import deque

def main():

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
C = [[set() for _ in range(n)] for i in range(n)]
P = [[set() for _ in range(n)] for i in range(n)]
seen = [[False]*(n) for i in range(n)]
dp = [[1]*(n) for i in range(n)]
for i in range(n):
  A = list(map(int, input().split()))
  for j in range(n-2):
    l1, l2 = i, i
    s, t = A[j]-1, A[j+1]-1
    if l1 > s:
      l1, s = s, l1
    if l2 > t:
      l2, t = t, l2
    C[l1][s].add((l2, t))
    P[l2][t].add((l1, s))
rep = []
def dfs(v1, v2):
  seen[v1][v2] = True
  for i1, i2 in C[v1][v2]:
    if seen[i1][i2]:
      continue
    dfs(i1, i2)
  rep.append((v1, v2))
for i in range(n-1):
  for j in range(i+1, n):
    if seen[i][j]:
      continue
    dfs(i, j)
count = n*(n-1)//2
rep = rep[::-1]
for i in range(count-1):
  i1, i2 = rep[i+1]
  for j1, j2 in P[i1][i2]:
    dp[i1][i2] = max(dp[j1][j2]+1, dp[i1][i2])
a, b = rep[-1]
print(dp[a][b])

Submission status: Wrong Answer

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

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


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


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

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


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


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

Submission status: Wrong Answer

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

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


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


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

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


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


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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, deque
input = lambda: sys.stdin.readline().rstrip()

graph = defaultdict(list)
deg = defaultdict(int)
n = int(input())
m = n * (n-1) // 2

for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n-2):
        v = tuple({i, a[j]-1})
        u = tuple({i, a[j+1]-1})
        graph[v].append(u)
        deg[u] += 1

q = deque(v for v in graph if deg[v] == 0)
cnt = 0
dp = defaultdict(int)

while q:
    v = q.popleft()
    cnt += 1
    for u in graph[v]:
        deg[u] -= 1
        dp[u] = max(dp[u], dp[v] + 1)
        if deg[u] == 0:
            q.append(u)

print(-1 if cnt != m else max(dp.values())+1)