CodeEff/ECCO huggingface dataset:
# Original solution
import sys

input=sys.stdin.readline

N=int(eval(input()))
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}

for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
q=set([])
flag={n:0 for n in node}
for key in node:
    if not _from[key]:
        q.add(key)
sub=set([])
while q:
    while q:
        x=q.pop()
        for n in _to[x]:
            flag[n]+=1
            if flag[n]==len(_from[n]):
                sub.add(n)
        if not q:
            q=sub
            sub=set([])
            day+=1
            break
able=True
for n in node:
    if flag[n]!=len(_from[n]):
        able=False
if able:
    print(day)
else:
    print((-1))

# Optimized solution
N=int(eval(input()))
A=[[] for i in range(0,N)]
nodes=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        nodes.append((i,j))

order={i:[0 for j in range(0,N)] for i in range(0,N)}
for i in range(0,N):
    A[i]=list(map(int,input().split()))
    for j in range(0,N-1):
        order[i][A[i][j]-1]=j
        #i番目の人がj番目の人と戦うのが何番目か


q=set([])
for battle in nodes:
    i,j=battle
    if order[i][j]==0 and order[j][i]==0:
        q.add(battle)

flag=[0 for i in range(0,N)]

day=0
sub=set([])
while q:
    while q:
        i,j=q.pop()
        flag[i]+=1
        flag[j]+=1
        if flag[i]!=N-1:
            s=A[i][order[i][j]+1]-1
            if flag[s]>=order[s][i]:
                sub.add((i,s))
        if flag[j]!=N-1:
            t=A[j][order[j][i]+1]-1
            if flag[t]>=order[t][j]:
                sub.add((j,t))

        if not q:
            day+=1
            q=sub
            sub=set([])
            break

able=True
for i in range(0,N):
    if flag[i]!=N-1:
        able=False

if able:
    print(day)
else:
    print((-1))
# Original solution
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(eval(input()))
    A = []
    for _ in range(n):
        t = deque(list(([int(x) - 1 for x in input().split()])))
        A.append(t)

    res = 0
    emp = [1] * n
    while True:
        check = [0] * n
        for i in range(n):
            if A[i] and not check[i]:
                idx = A[i][0]
                if not check[idx] and A[idx][0] == i:
                    A[i].popleft()
                    A[idx].popleft()
                    check[i] = check[idx] = 1
            if not A[i]:
                emp[i] = 0
        res += 1
        if sum(emp) == 0:
            break
        if sum(check) == 0:
            print((-1))
            exit()
    print(res)





if __name__ == '__main__':
    resolve()


# Optimized solution
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(eval(input()))
    A = []
    for _ in range(n):
        t = deque(list(([int(x) - 1 for x in input().split()])))
        A.append(t)

    que = deque(list(range(n)))
    res = 0
    emp = [False] * n
    while que:
        next_que = deque([])
        check = set()
        while que:
            i = que.popleft()
            if A[i]:
                idx = A[i][0]
                if i not in check and idx not in check and A[idx][0] == i:
                    A[i].popleft()
                    A[idx].popleft()
                    next_que.append(i)
                    next_que.append(idx)
                    check.add(i)
                    check.add(idx)
            else:
                emp[i] = True
        que = next_que
        if que:
            res += 1
    else:
        print((res if all(emp) else -1))


if __name__ == '__main__':
    resolve()
# Original solution
import sys
from collections import defaultdict
n=int(eval(input()))
a=[]
hd=[0]*n
for i in range(n):
    a.append(tuple(map(int,input().split())))
d=defaultdict(int)
for i in range(n):
    for j in range(n-1):
        d[(i,j)]=a[i][j]
loop=0
flag=0
while(flag<n):
    stk=[]
    for i in range(n):
        if hd[i]==n-1:
            continue
        idx=d[(i,hd[i])]-1
        if hd[idx]==n-1:
            print((-1))
            sys.exit()
        if d[(idx,hd[idx])]==i+1:
            stk.append(i)
    if not stk:
        loop=-2
        break
    for j in stk:
        hd[j]+=1
        if hd[j]==n-2:
            flag+=1
    loop+=1
print((loop+1))

# Optimized solution
import sys
sys.setrecursionlimit(10**9)
n=int(eval(input()))
a=[]
for i in range(n):
    a.append(tuple(map(int,input().split())))
#print(a)

root=[[] for i in range(n*(n-1)//2)]
buf=0
for i in range(n):
    buf=0
    for j in range(n-1):
        if j==0:
            x=min(i,a[i][j]-1)
            y=max(i,a[i][j]-1)
            buf=x*(2*n-2-x+1)//2+(y-x)-1
            #print(x,y,buf)
            continue
        x=min(i,a[i][j]-1)
        y=max(i,a[i][j]-1)
        node=x*(2*n-2-x+1)//2+(y-x)-1
        #print(x,y,node)
        root[buf].append(node)
        buf=node
flag=[True]

#閉路☑
def dfs(node,par): 
    dp[node]=0
    for item in root[node]:
        if item==par:
            continue
        if dp[item]==0:
            flag[0]=False
            return
        if dp[item]==-1: 
            dfs(item,node)
    dp[node]=1#finish
dp=[-1]*(n*(n-1)//2)
for i in range(n*(n-1)//2):
    if dp[i]==-1:
        dfs(i,i)
        if flag[0]==False:
            break
if flag[0]==False:
    print((-1))
    sys.exit()
dp=[-1]*(n*(n-1)//2)
def dfs1(node,par): 
    buf=0
    for item in root[node]:
        if item==par:
            continue
        if dp[item]!=-1:
            buf=max(buf,dp[item])
            continue
        if dp[item]==-1: 
            buf=max([buf,dfs1(item,node)])
    dp[node]=buf+1#finish
    return buf+1

for i in range(n*(n-1)//2):
    if dp[i]==-1:
        dp[i]=dfs1(i,i)
print((max(dp)))
# Original solution
import sys
input = sys.stdin.readline

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(list(range(N)), 2))
graph = {i:[] for i in nodes}
in_cnt = {k:0 for k in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].append(now)
    in_cnt[now] += 1 
    prev = now

d = {k:1 for k in nodes}
q = [i for i in nodes if not in_cnt[i]]

if not q:
  print((-1))
  exit()
ans = 0
while q:
  x = q.pop()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print((-1))
  exit()

print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

N = int(input().strip())
M = N*(N-1)//2

graph = [[] for i in range(M)]
in_cnt = [0 for i in range(M)]
for x in range(1,N+1):
  l = list(map(int,input().split()))
  y = l[0]
  b,s = max(x,y),min(x,y)
  prev = (b-1)*(b-2)//2+s-1
  for y in l[1:]:
    b,s = max(x,y),min(x,y)
    now = (b-1)*(b-2)//2+s-1
    graph[prev].append(now)
    in_cnt[now] += 1 
    prev = now

d = [1 for k in range(M)]
q = [i for i in range(M) if not in_cnt[i]]

if not q:
  print((-1))
  exit()
ans = 0
while q:
  x = q.pop()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in range(M) if in_cnt[i]]:
  print((-1))
  exit()

print(ans)
# Original solution
import queue
import copy

N=int(eval(input()))
A=[[] for _ in range(N)]

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

NE=[0]*N#i番目の人が，次何番目の試合をするかのリスト
F=[0]*N#i番目の人が，該当する日に試合をしたか記憶しておく

#i+1日目の試合をする人はi日目に試合をした人なので，それを記憶．
q1=queue.Queue()
q2=queue.Queue()

#初日
for i in range(N):
    opp=A[i][0]-1
    if A[opp][0]-1==i:
        NE[i]+=1
        q1.put(i)

ans=1
#d日目
for d in range(N*(N-1)//2):
    F=[0]*N
    while not q2.empty():
        a=q2.get()
        q1.put(a)
    while not q1.empty():
        i=q1.get()
        if NE[i]==N-1:
            continue
        opp=A[i][NE[i]]-1
        if F[i]==1 or F[opp]==1:#その日に試合したことがある人はスルー,oppの重複防止
            continue
        if A[opp][NE[opp]]-1==i:
            NE[i]+=1
            NE[opp]+=1
            F[i]=1
            F[opp]=1
            if NE[i]!=N-1:
                q2.put(i)
            if NE[opp]!=N-1:
                q2.put(opp)
    ans+=1
    if q2.empty() and q2.empty():
        break

for i in range(N):
    if NE[i]!=N-1:
        ans=-1
print(ans)

# Optimized solution
N=int(eval(input()))
A=[[] for _ in range(N)]

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

NE=[0]*N#i番目の人が，次何番目の試合をするかのリスト
F=[0]*N#i番目の人が，該当する日に試合をしたか記憶しておく

#i+1日目の試合をする人はi日目に試合をした人なので，それを2つのqueueに記憶．
Q=[[],[]]

#初日
for i in range(N):
    opp=A[i][0]-1
    if A[opp][0]-1==i:
        NE[i]+=1
        Q[0].append(i)

ans=1
#d日目
for d in range(N*(N-1)//2):
    F=[0]*N
    a=d%2
    b=(d+1)%2
    while len(Q[a])!=0:
        i=Q[a].pop()
        if NE[i]==N-1:
            continue
        opp=A[i][NE[i]]-1
        if F[i]==1 or F[opp]==1:#その日に試合したことがある人はスルー,oppの重複防止
            continue
        if A[opp][NE[opp]]-1==i:
            NE[i]+=1
            NE[opp]+=1
            F[i]=1
            F[opp]=1
            if NE[i]!=N-1:
                Q[b].append(i)
            if NE[opp]!=N-1:
                Q[b].append(opp)
    ans+=1
    if len(Q[a])==0 and len(Q[b])==0:
        break

for i in range(N):
    if NE[i]!=N-1:
        ans=-1
print(ans)
# Original solution
N=int(eval(input()))
A=[[] for _ in range(N)]

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

NE=[0]*N#i番目の人が，次何番目の試合をするかのリスト
F=[0]*N#i番目の人が，該当する日に試合をしたか記憶しておく

#i+1日目の試合をする人はi日目に試合をした人なので，それを2つのqueueに記憶．
Q=[[],[]]

#初日
for i in range(N):
    opp=A[i][0]-1
    if A[opp][0]-1==i:
        NE[i]+=1
        Q[0].append(i)

ans=1
#d日目
for d in range(N*(N-1)//2):
    F=[0]*N
    a=d%2
    b=(d+1)%2
    while len(Q[a])!=0:
        i=Q[a].pop()
        if NE[i]==N-1:
            continue
        opp=A[i][NE[i]]-1
        if F[i]==1 or F[opp]==1:#その日に試合したことがある人はスルー,oppの重複防止
            continue
        if A[opp][NE[opp]]-1==i:
            NE[i]+=1
            NE[opp]+=1
            F[i]=1
            F[opp]=1
            if NE[i]!=N-1:
                Q[b].append(i)
            if NE[opp]!=N-1:
                Q[b].append(opp)
    ans+=1
    if len(Q[a])==0 and len(Q[b])==0:
        break

for i in range(N):
    if NE[i]!=N-1:
        ans=-1
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline

def I(): return int(eval(input()))
def MI(): return list(map(int, input().split()))
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=[]
    inf=10**6
    for _ in range(N):
        a=LI()+[inf]
        for j in range(N-1):
            a[j]-=1
        A.append(a)
        
        
    cur=[0]*N#i番目の人が何試合消化したか
    
    st=[]# stackに，みるべき人を入れていいく，変化があった人だけ見れば良い
    nxt=[]
    
    #初日は全員みる，N>=3より初日で終わることはない
    for i in range(N):
        for j in range(i+1,N):
            if A[i][0]==j and A[j][0]==i:
                cur[i]=1
                cur[j]=1
                st.append(i)
                st.append(j)
    day=1
    
    while st:
        used=[0]*N
        day+=1
        
        while st:
            i=st.pop()#みる人
            j=A[i][cur[i]]#相手候補
            
            if used[i]==0 and used[j]==0:
                if A[j][cur[j]]==i:#マッチング
                    cur[i]+=1
                    cur[j]+=1
                    nxt.append(i)
                    nxt.append(j)
                    used[i]=1
                    used[j]=1
               
        while nxt:
            a=nxt.pop()
            if cur[a]!=N-1:
                st.append(a)
        
    if sum(cur)==N*(N-1):
        print(day)
    else:
        print((-1))
        
            
        
        
    

main()
# Original solution
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    N = int(eval(input()))

    A_all = []
    for i in range(N):
        As = list(map(int, input().split()))
        A_all.append(As)
    A_index = [0] * N

    for i in range(N * (N - 1) // 2 + 1):
        matches = set()
        for j in range(1, N+1):
            A_idx = A_index[j - 1]
            if A_idx >= N - 1:
                continue
            k = A_all[j - 1][A_idx]
            B_idx = A_index[k - 1]
            if B_idx >= N - 1:
                continue
            if j == A_all[k - 1][B_idx]:
                pair = tuple(sorted([j, k]))
                matches.add(pair)

        if not matches:
            break

        for match in matches:
            for j in match:
                A_index[j - 1] += 1

    if all([A_idx == N - 1 for A_idx in A_index]):
        print(i)
    else:
        print((-1))


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    input = sys.stdin.readline
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    N = int(eval(input()))

    A_all = []
    for i in range(N):
        As = list(map(int, input().split()))
        A_all.append(As)
    A_index = [0] * N

    candidates = set(range(1, N+1))
    for i in range(N * (N - 1) // 2 + 1):
        matches = set()
        for j in candidates:
            A_idx = A_index[j - 1]
            if A_idx >= N - 1:
                continue
            k = A_all[j - 1][A_idx]
            B_idx = A_index[k - 1]
            if B_idx >= N - 1:
                continue
            if j == A_all[k - 1][B_idx]:
                pair = tuple(sorted([j, k]))
                matches.add(pair)

        if not matches:
            break

        candidates = set()
        for match in matches:
            for j in match:
                A_index[j - 1] += 1
                candidates.add(j)

    if all([A_idx == N - 1 for A_idx in A_index]):
        print(i)
    else:
        print((-1))


if __name__ == '__main__':
    main()
# Original solution
N=int(eval(input()))
A=[list(map(int,input().split())) for i in range(N)]
from collections import defaultdict
d=defaultdict(int)
l=defaultdict(list)
for i in range(N):
    x,y=(i,A[i][0]-1) if i<A[i][0]-1 else (A[i][0]-1,i)
    d[(x,y)]+=1
    l[(x,y)].append(i)
p=[0]*N
r=0
while len(d)>0:
    r+=1
    f=0
    diff=defaultdict(int)
    for k in list(d.keys()):
        if d[k]==2:
            del d[k]
            for i in l[k]:
                p[i]+=1
                if p[i]>N-2:
                    continue
                x,y=(i,A[i][p[i]]-1) if i<A[i][p[i]]-1 else (A[i][p[i]]-1,i)
                diff[(x,y)]+=1
                l[(x,y)].append(i)
            f=1
    for x,y in list(diff.keys()):
        d[(x,y)]+=diff[(x,y)]
    if f==0:
        break
print((r if f>0 else -1))

# Optimized solution
N=int(eval(input()))
A=[list(map(int,input().split())) for i in range(N)]
from collections import defaultdict
d=defaultdict(int)
l=defaultdict(list)
for i in range(N):
    x,y=(i,A[i][0]-1) if i<A[i][0]-1 else (A[i][0]-1,i)
    d[(x,y)]+=1
    l[(x,y)].append(i)
p=[0]*N
r=0
cand=list(d.keys())
while len(d)>0:
    r+=1
    f=0
    diff=defaultdict(int)
    for k in cand:
        if d[k]==2:
            del d[k]
            for i in l[k]:
                p[i]+=1
                if p[i]>N-2:
                    continue
                x,y=(i,A[i][p[i]]-1) if i<A[i][p[i]]-1 else (A[i][p[i]]-1,i)
                diff[(x,y)]+=1
                l[(x,y)].append(i)
            f=1
    for x,y in list(diff.keys()):
        d[(x,y)]+=diff[(x,y)]
    cand=list(diff.keys())
    if f==0:
        break
print((r if f>0 else -1))
# Original solution
from collections import deque
import sys
input = sys.stdin.readline

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

def solve() :
    q = list(range(N))
    count = 0
    ret = 0
    while count != N * (N - 1) :
        if len(q) == 0 :
            return -1
        
        done = [False] * N
        schedule = []
        for i in q :
            j = A[i][0]
            if done[i] or done[j]:
                continue
                
            if i == A[j][0] :
                schedule.append(i)
                schedule.append(j)
                done[i] = done[j] = True
                
        ret += 1
        q = []
        for i in schedule :
            A[i].popleft()
            if len(A[i]) > 0 :
                q.append(i)
        count += len(schedule)
        
    return ret
    
print((solve()))

# Optimized solution
from collections import deque
import sys
input = sys.stdin.readline

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

def solve() :
    q = list(range(N))
    count = 0
    ret = 0
    while count != N * (N - 1) :
        if len(q) == 0 :
            return -1
        
        schedule = set()
        for i in q :
            j = A[i][0]
            if i in schedule or j in schedule :
                continue
                
            if i == A[j][0] :
                schedule.add(i)
                schedule.add(j)
                
        ret += 1
        q = []
        for i in schedule :
            A[i].popleft()
            if len(A[i]) > 0 :
                q.append(i)
        count += len(schedule)
        
    return ret
    
print((solve()))
# Original solution
import sys
import collections
import copy
def input(): return sys.stdin.readline().strip()
N = int(eval(input()))
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
chk = 0
for j in range(N*(N-1)//2):
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
print(ans)

# Optimized solution
import sys
import collections
import copy
def input(): return sys.stdin.readline().strip()
N = int(eval(input()))
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
chk = 0
for j in range(N*(N-1)//2):
    if j >= 4000:
        chk = 1
        break
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
if chk == 0:
    print(ans)
else:
    print((N*(N-1)//2))
# Original solution
def main():
    n=int(eval(input()))
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    dr=[]
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            dr.append((i,j))
            cnt+=1
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            if i>=j:temp.append(d[(j-1,i)])
            else:temp.append(d[(i,j-1)])
        for j,k in enumerate(temp[1:]):
            g[temp[j]].append(k)
            gr[k]+=1
    q=[i for i,j in enumerate(gr) if j==0]
    cnt=0
    while q:
        cnt+=1
        qq=[]
        temp=[]
        s=set()
        for i in q:
            x,y=dr[i]
            if (x not in s) and (y not in s):
                temp.append(i)
                s.add(x)
                s.add(y)
            else:
                qq.append(i)
        for i in temp:
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print((-1))
main()

# Optimized solution
def main():
    n=int(eval(input()))
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            cnt+=1
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            if i>=j:temp.append(d[(j-1,i)])
            else:temp.append(d[(i,j-1)])
        for j,k in enumerate(temp[1:]):
            g[temp[j]].append(k)
            gr[k]+=1
    q=[i for i,j in enumerate(gr) if j==0]
    cnt=0
    while q:
        cnt+=1
        qq=[]
        for i in q:
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print((-1))
main()