CodeEff/ECCO huggingface dataset:
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    from collections import deque

    # input
    n=int(eval(input()))
    V=[(i,j) for i,j in product(list(range(n)),repeat=2) if i<j]
    E={v:[] for v in V}
    indeg={v:0 for v in V}
    for i in range(n):
        a=list([int(x)-1 for x in input().split()])
        for j in range(1,n-1):
            p0,q0=min(i,a[j-1]),max(i,a[j-1])
            p1,q1=min(i,a[j]),max(i,a[j])
            E[(p0,q0)].append((p1,q1))
            indeg[(p1,q1)]+=1

    # topological sort
    Q=deque(k for k,v in list(indeg.items()) if v==0)
    res=[]
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in E[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)

    # judge whether DAG or not
    if len(res)<n*(n-1)//2:
        print((-1))
        return

    # calculate diameter
    LP={v:1 for v in V}
    for v0 in res:
        for v1 in E[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print((max(LP.values())))
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(eval(input()))
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(list(range(n)),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

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

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list([int(x)-1 for x in input().split()])
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print((-1))
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print((max(dp)+1 if(flag) else -1))
resolve()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(eval(input()))
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(list(range(n)),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

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

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list([int(x)-1 for x in input().split()])
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # 頂点数Vの有向グラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    def dfs(v):
        if(dp[v]>=0): return
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print((-1))
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print((max(dp)+1))
resolve()

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(eval(input()))
    # popするため逆順にしておく
    A=[list([int(x)-1 for x in input().split()]) for _ in range(n)]
    for i in range(n): A[i].reverse()
    stack=[]

    def check(i):
        if(not A[i]): return
        j=A[i][-1]
        if(A[j][-1]==i):
            stack.append((min(i,j),max(i,j)))

    # calculate
    for i in range(n): check(i)
    day=0
    while(stack):
        day+=1
        stack=list(set(stack)) # uniqueを取る
        prev,stack=stack,[]
        for i,j in prev:
            A[i].pop(); A[j].pop()
        for i,j in prev:
            check(i); check(j)
    print((-1 if(any(A[i] for i in range(n))) else day))
resolve()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n=int(eval(input()))

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

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

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

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

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(eval(input()))

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

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

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

    print((max(dfs(v) for v in range(N))+1))
resolve()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(eval(input()))

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

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

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

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

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(eval(input()))

    # id table
    N=0
    id=[[None]*n for _ in range(n)]
    from itertools import product
    for i,j in product(list(range(n)),repeat=2):
        if(i>=j): continue
        id[i][j]=N
        N+=1
    toID=lambda i,j:id[min(i,j)][max(i,j)]

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

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

    print((max(dfs(v) for v in range(N))+1))
resolve()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(eval(input()))

    # id table
    N=0
    id=[[None]*n for _ in range(n)]
    from itertools import product
    for i,j in product(list(range(n)),repeat=2):
        if(i>=j): continue
        id[i][j]=N
        N+=1
    toID=lambda i,j:id[min(i,j)][max(i,j)]

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

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

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

# Optimized solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(eval(input()))
    M=[None]*n
    for i in range(n):
        M[i]=list([int(x)-1 for x in input().split()])[::-1]

    # i が誰かしらと対戦できるか
    def check(i):
        if(not M[i]): # 既に試合を終えている
            return False
        j=M[i][-1]
        if(not M[j]): # これは起こり得ない
            return False
        return i==M[j][-1]

    # 初日に対戦できる人をピックアップ
    # 重複が起こるが、後で unique を取る
    Q=[]
    for i in range(n):
        if(check(i)):
            j=M[i][-1]
            if(i>j): i,j=j,i # i<j
            Q.append((i,j))

    # 処理を行なっていく
    day=0
    nQ=[] # 次の試合相手
    while(Q):
        # Q には重複があるので unique
        Q=list(set(Q))
        # 先に全ての試合を終わらせる必要がある
        for i,j in Q:
            M[i].pop(); M[j].pop()
        # 試合を終えた人は次の試合を行える可能性がある
        for i,j in Q:
            if(check(i)):
                k=M[i][-1]
                nQ.append((min(i,k),max(i,k)))
            if(check(j)):
                k=M[j][-1]
                nQ.append((min(j,k),max(j,k)))
        Q,nQ=nQ,[]
        day+=1

    print((day if(all(M[i]==[] for i in range(n))) else "-1"))
resolve()
# Original solution
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(eval(input()))
    M=[None]*n
    for i in range(n):
        M[i]=list([int(x)-1 for x in input().split()])[::-1]

    # i が誰かしらと対戦できるか
    def check(i):
        if(not M[i]): # 既に試合を終えている
            return False
        j=M[i][-1]
        if(not M[j]): # これは起こり得ない
            return False
        return i==M[j][-1]

    # 初日に対戦できる人をピックアップ
    # 重複が起こるが、後で unique を取る
    Q=[]
    for i in range(n):
        if(check(i)):
            j=M[i][-1]
            if(i>j): i,j=j,i # i<j
            Q.append((i,j))

    # 処理を行なっていく
    day=0
    nQ=[] # 次の試合相手
    while(Q):
        # Q には重複があるので unique
        Q=list(set(Q))
        # 先に全ての試合を終わらせる必要がある
        for i,j in Q:
            M[i].pop(); M[j].pop()
        # 試合を終えた人は次の試合を行える可能性がある
        for i,j in Q:
            if(check(i)):
                k=M[i][-1]
                nQ.append((min(i,k),max(i,k)))
            if(check(j)):
                k=M[j][-1]
                nQ.append((min(j,k),max(j,k)))
        Q,nQ=nQ,[]
        day+=1

    print((day if(all(M[i]==[] for i in range(n))) else "-1"))
resolve()

# Optimized solution
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(eval(input()))
    A = [None] * n
    for i in range(n):
        tmp = list([int(x) - 1 for x in input().split()])
        tmp.reverse()
        A[i] = tmp

    now = set()
    for i in range(n):
        j = A[i][-1]
        if i == A[j][-1]:
            now.add((min(i, j), max(i, j)))

    cnt = 0
    while now:
        next = set()
        for i, j in now:
            A[i].pop()
            A[j].pop()

        for i0, i1 in now:
            for i in (i0, i1):
                if not A[i]:
                    continue
                j = A[i][-1]
                if not A[j]:
                    continue
                if i == A[j][-1]:
                    next.add((min(i, j), max(i, j)))

        now = next
        cnt += 1

    if any(row for row in A):
        print((-1))
        return
    print(cnt)
resolve()
# Original solution
N = int(eval(input()))

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

cnt = [0] * N

S = []
for i in range(N):
  t = A[i][cnt[i]] - 1
  if i == A[t][cnt[t]] - 1:
    if cnt[i] != N - 2:
      S.append(i)

ans = 1
while S:
  ans += 1
  L = [True] * N
  for i in S:
    cnt[i] += 1
  T = []
  for i in S:
    if L[i]:
      t = A[i][cnt[i]] - 1
      if i == A[t][cnt[t]] - 1:
        if cnt[i] != N - 2:
          L[i] = False
          T.append(i)
        if L[t]:
          L[t] = False
          if cnt[t] != N - 2:
            T.append(t)
  S = T

for i in range(N):
  if cnt[i] != N - 2:
    print((-1))
    break
else:
  print(ans)


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

cnt = [0] * N

S = []
for i in range(N):
  t = A[i][cnt[i]] - 1
  if i == A[t][cnt[t]] - 1:
    if cnt[i] != N - 2:
      S.append(i)

ans = 1
L = [True] * N
while S:
  ans += 1
  for i in S:
    cnt[i] += 1
    L[i] = True
  T = []
  for i in S:
    if L[i]:
      t = A[i][cnt[i]] - 1
      if i == A[t][cnt[t]] - 1:
        if cnt[i] != N - 2:
          L[i] = False
          T.append(i)
        if L[t]:
          L[t] = False
          if cnt[t] != N - 2:
            T.append(t)
  S = T

for i in range(N):
  if cnt[i] != N - 2:
    print((-1))
    break
else:
  print(ans)
# Original solution
from collections import defaultdict
from heapq import heappush, heappop
N = int(eval(input()))
dic = defaultdict(list)
toNum = {}
L = N*(N-1)//2
s = [0]
for i in range(N-1,0,-1):
  s += [s[-1]+i]
dist = [0]*L
for i in range(N):
  inf = [int(c)-1 for c in input().split()]
  pa = min(i,inf[0])
  pb = max(i,inf[0])
  pnum = s[pa]+(pb-pa-1)
  for j in range(1,N-1):
    a = min(i,inf[j])
    b = max(i,inf[j])
    num = s[a]+(b-a-1)
    dic[pnum]  += [num]
    dist[num] += 1
    pa = a
    pb = b
    pnum = num

hq = []
for i in range(L):
  if dist[i]==0:
    heappush(hq,(1,i))
  dist[i] = 0
if hq==[]:
  print((-1))
  import sys
  sys.exit()
cnt = 0
ans = 0
while hq:
  c, n = heappop(hq)
  if dist[n]>=c:
    continue
  dist[n] = c
  cnt += 1
  for m in dic[n]:
    if dist[m]>=c+1:
      continue
    if ans<c+1:
      ans = c+1
    heappush(hq,(c+1,m))
  if ans>L:
    print((-1))
    break
else:
  print(ans)

# Optimized solution
N = int(eval(input()))
A = [0 for i in range(N)]
for i in range(N):
  A[i] = [-1]+[int(c)-1 for c in input().split()][::-1]

def f(cand):
  can_use = []
  candl = set()
  for i in cand:
    c = A[i][-1]
    if A[c][-1]==i:
      can_use += [i]
  for n in can_use:
    A[n].pop()
    candl.add(n)
    if A[n][-1]!=-1:
      candl.add(A[n][-1])
  return len(can_use),candl

ans = 0
rest = N*(N-1)
cand = set(range(N))
while True:
  ans += 1
  x, cand = f(cand)
  if x==0:
    ans = -1
    break
  rest -= x
  if rest==0:
    break
print(ans)
# Original solution
n=int(eval(input()))

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

day=0
zan=[n-1]*n
zann=sum(zan)
sumi=set(range(n))

while True:
  day+=1

  kouho=list(sumi)
  sumi=set()
  
  for i in kouho:
    try:
      if A[A[i][-1]-1][-1]-1==i:
        sumi.add(i)
        sumi.add(A[i][-1]-1)
    except:
      pass

  for k in sumi:
    A[k].pop()
    zan[k]-=1

  if zann==sum(zan):
    print((-1))
    exit(0)
  
  zann=sum(zan)
  
  if zann==0:
    print(day)
    exit(0)
    


# Optimized solution
import sys
 
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

def main():

  n=int(eval(input()))

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

  day=0
  zan=[n-1]*n
  zann=sum(zan)
  sumi=set(range(n))

  while True:
    day+=1

    kouho=list(sumi)
    sumi=set()
  
    for i in kouho:
      try:
        if A[A[i][-1]-1][-1]-1==i:
          sumi.add(i)
          sumi.add(A[i][-1]-1)
      except:
        pass

    for k in sumi:
      A[k].pop()
      zan[k]-=1

    if zann==sum(zan):
      print((-1))
      exit(0)
  
    zann=sum(zan)
  
    if zann==0:
      print(day)
      exit(0)
    
if __name__ == "__main__":
	main()
# Original solution
def main():
    N = int(eval(input()))
    a = [list(map(int, input().split())) for i in range(N)]

    now = [0] * N
    day = 0
    MAX = (N*(N-1)) // 2
    gamed_day = [-1] * N
    finished = 0
    while True:
        if day > MAX:
            print((-1))
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print((day+1))
            else:
                print(day)
            break
        if not had_game:
            print((-1))
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()


# Optimized solution
import time
def main():
    N = int(eval(input()))
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.8:
            print(((N*(N-1))//2))
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print((day+1))
            else:
                print(day)
            break
        if not had_game:
            print((-1))
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()
# Original solution
import time
def main():
    N = int(eval(input()))
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.8:
            print(((N*(N-1))//2))
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print((day+1))
            else:
                print(day)
            break
        if not had_game:
            print((-1))
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()


# Optimized solution
import time
def main():
    N = int(eval(input()))
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.6:
            print(((N*(N-1))//2))
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print((day+1))
            else:
                print(day)
            break
        if not had_game:
            print((-1))
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()