CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(eval(input()))
a = [list([int(x)-1 for x in input().split()]) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    # uからdfs
    seen[u] = True
    ans = 0
    for v in ns[u]:
        if done[v]:
            ans = max(ans, vals[v]+1)
            continue
        elif seen[v]:
            # サイクルを検出
            return 1
        else:
            pos = dfs(v)
            if pos>=0:
                return 1
            ans = max(ans, vals[v]+1)
    done[u] = True
    vals[u] = ans
    return -1
ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos>=0:
        print((-1))
        break
else:
    print((max(vals)+1))

# Optimized solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(eval(input()))
a = [list([int(x)-1 for x in input().split()]) for _ in range(n)]
N = n*(n-1)//2
index = {}
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i,j] = ind
        index[j,i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i,a[i][j]]
        v = index[i,a[i][j+1]]
        ns[u].append(v)
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    # 閉路発見
                    return True
        else:
            u = ~u
            done[u] = True
            # ここに帰りがけ処理を書く
            val = 0
            for v in ns[u]:
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print((-1))
        break
else:
    print((max(vals)+1))
# Original solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(eval(input()))
a = [list([int(x)-1 for x in input().split()]) for _ in range(n)]
N = n*(n-1)//2
index = [[0]*(n) for i in range(n)]
ind = 0
from collections import defaultdict
ns = defaultdict(list)
for i in range(n):
    for j in range(i+1,n):
        index[i][j] = ind
        index[j][i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i][a[i][j]]
        v = index[i][a[i][j+1]]
        ns[u].append(v)
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            # 非負の値: 新しい頂点に到達
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    # 閉路発見
                    return True
        else:
            u = ~u
            done[u] = True
            # ここに帰りがけ処理を書く
            val = 0
            for v in ns[u]:
                # uの子はすべて処理が終わっている
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print((-1))
        break
else:
    print((max(vals)+1))

# Optimized solution
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(eval(input()))
a = [list([int(x)-1 for x in input().split()]) for _ in range(n)]
N = n*(n-1)//2
index = [[0]*(n) for i in range(n)]
ind = 0
from collections import defaultdict
ns = [[] for _ in range(N)]
for i in range(n):
    for j in range(i+1,n):
        index[i][j] = ind
        index[j][i] = ind
        ind += 1
for i in range(n):
    for j in range(n-2):
        u = index[i][a[i][j]]
        v = index[i][a[i][j+1]]
        ns[u].append(v)
### サイクル検出 cycle detection
seen = [False] * N
done = [False] * N
vals = [None] * N
def dfs(u):
    s = [u]
    while s:
        u = s.pop()
        if u>=0:
            # 非負の値: 新しい頂点に到達
            seen[u] = True
            s.append(~u)
            for v in ns[u]:
                if done[v]:
                    continue
                elif not seen[v]:
                    s.append(v)
                else:
                    # 閉路発見
                    return True
        else:
            u = ~u
            done[u] = True
            # ここに帰りがけ処理を書く
            val = 0
            for v in ns[u]:
                # uの子はすべて処理が終わっている
                val = max(val, vals[v]+1)
            vals[u] = val
    return False

ans = -float("inf")
for u in range(N):
    if seen[u]:
        continue
    pos = dfs(u)
    if pos:
        print((-1))
        break
else:
    print((max(vals)+1))
# Original solution
from collections import deque

def main():
  n=int(eval(input()))
  a=[0]*n
  for i in range(n):
    a[i]=deque(list([int(x)-1 for x in input().split()]))
  q=deque([])
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      if x not in q and y not in q:
        q.append(x)
        q.append(y)
        a[x].popleft()
        a[y].popleft()

  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if len(a[y])==0: continue;
      if x == a[y][0] and x not in q and y not in q:
        q.append(x)
        q.append(y)
        a[x].popleft()
        a[y].popleft()

    #print(f'a={a}')
    if len(q)==0: break;


  for i in range(n):
    if len(a[i])!=0:
      print((-1))
      exit()
  print(day)


if __name__=='__main__':
  main()

# Optimized solution
from collections import deque

def main():
  n=int(eval(input()))
  a=[0]*n
  for i in range(n):
    a[i]=deque(list([int(x)-1 for x in input().split()]))
  q=deque([])
  tmp=set()
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      tmp.add(x)
      tmp.add(y)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  
  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    tmp=set()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if x == a[y][0]:
        tmp.add(x)
        tmp.add(y)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    if len(q)==0: break;

  for i in range(n):
    if len(a[i])!=0:
      print((-1))
      exit()
  print(day)


if __name__=='__main__':
  main()
# Original solution
from collections import deque

def main():
  n=int(eval(input()))
  a=[0]*n
  for i in range(n):
    a[i]=deque(list([int(x)-1 for x in input().split()]))
  q=deque([])
  tmp=set()
  for idx,i in enumerate(a):
    x=idx
    y=i[0]
    if x == a[y][0]:
      tmp.add(x)
      tmp.add(y)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  
  day=0
  while True:
    day+=1
    t=q.copy()
    q=deque()
    tmp=set()
    while t:
      x=t.popleft()
      if len(a[x])==0: continue;
      y=a[x][0]
      if x == a[y][0]:
        tmp.add(x)
        tmp.add(y)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    if len(q)==0: break;

  for i in range(n):
    if len(a[i])!=0:
      print((-1))
      exit()
  print(day)


if __name__=='__main__':
  main()

# Optimized solution
from collections import deque

def main():
  n=int(eval(input()))
  a=[0]*n
  for i in range(n):
    a[i]=deque(list([int(x)-1 for x in input().split()]))
  tmp=set()
  for p1,p in enumerate(a):
    p2=p[0]
    if p1==a[p2][0]:
      tmp.add(p1)
      tmp.add(p2)
  q=deque(tmp)
  for i in tmp:
    a[i].popleft()
  
  day=0
  while True:
    day+=1
    tmp=set()
    while q:
      p1=q.popleft()
      if len(a[p1])==0: continue;
      p2=a[p1][0]
      if p1==a[p2][0]:
        tmp.add(p1)
        tmp.add(p2)
    q=deque(tmp)
    for i in tmp:
      a[i].popleft()
    tmp=set()
    if len(q)==0: break;
    
  for i in a:
    if i:
      print((-1))
      exit()
  print(day)


if __name__=='__main__':
  main()
# Original solution
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(eval(input()))
X = 10000
INF = 1 << 50
edges = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in list(G.keys()):
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print((-1))
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
for V in vs:
    if used[V]: continue
    used[V] = 1
    q = deque([V])
    while len(q) > 0:
        v = q.popleft()
        for u in edges[v]: 
            if used[u] <= used[v]:
                q.append(u)
                used[u] = max(used[u], used[v] + 1)
print((max(used)))

# Optimized solution
import sys
input = sys.stdin.readline
from collections import defaultdict, deque
n = int(eval(input()))
X = 10000
INF = 1 << 50
edges = defaultdict(list)
edges_r = defaultdict(list)
def topological_sort(G):

    cnt_in = defaultdict(int)
    for k in list(G.keys()):
        for v in G[k]:
            cnt_in[v] += 1
    # print(cnt_in)
    res = []
    # 入次数==0
    q = deque([i for i in list(G.keys()) if cnt_in[i]==0])
    while len(q) > 0:
        v = q.popleft()
        res.append(v)
        for next_v in G[v]:
            # 入次数を下げていく
            cnt_in[next_v] -= 1
            # 入次数が0に残ったところを次に追加
            if cnt_in[next_v] == 0:
                q.append(next_v)
    # トポソ不可能！
    if len(G) != len(res):
        print((-1))
        exit()
    return res

for i in range(n):
    r = list(map(int, input().split()))
    # 初期
    mn = min(i, r[0]-1)
    mx = max(i, r[0]-1)
    prev = mn * n + mx
    for e in r[1:]:
        e -= 1
        mn = min(i,e)
        mx = max(i,e)
        now = mn*n+mx
        edges[prev].append(now)
        edges_r[now].append(prev)
        prev = now
vs = topological_sort(edges)

# トポソの順番で経路長を入れていく
used = [0] * n**2
# for V in vs:
#     if used[V]: continue
#     used[V] = 1
#     q = deque([V])
#     while len(q) > 0:
#         v = q.popleft()
#         for u in edges[v]: 
#             if used[u] <= used[v]:
#                 q.append(u)
#                 used[u] = max(used[u], used[v] + 1)

for V in vs:
    if used[V]:continue
    used[V] = 1
    mx = 1
    for b in edges_r[V]:
        mx = max(mx, used[b]+1)
    used[V] = mx
# print(used)
print((max(used)))
# Original solution
n = int(eval(input()))
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
    for j in range(n-1):
        a[i][j] -= 1
    a[i].reverse()
q = []

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = q
    prevQ = get_unique_list(prevQ)
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
    for i,j in prevQ:
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print((-1))
        exit()
print(day)

# Optimized solution
n = int(eval(input()))
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
    for j in range(n-1):
        a[i][j] -= 1
    a[i].reverse()
q = []

def check(i):
    if len(a[i]) == 0:
        return 
    j = a[i][-1]
    if len(a[j]) == 0:
        return
    if a[j][-1] == i:
        q.append([min(i,j), max(i,j)])
for i in range(n):
    check(i)
day = 0
while (len(q) > 0):
    day += 1
    prevQ = list(map(list, set(map(tuple, q))))
    q = []
    for i,j in prevQ:
        a[i].pop()
        a[j].pop()
        check(i)
        check(j)
for i in range(n):
    if len(a[i]) > 0:
        print((-1))
        exit()
print(day)
# Original solution
from collections import deque

N = int(eval(input()))
A = [deque(list(map(int,input().split()))) for _ in range(N)]
day = 0
match = 0
que = [0 for _ in range(N+1)]

while match!=(N-1) * N / 2:
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    day = -1
    break
  day += 1
  
print(day)

# Optimized solution
from collections import deque
import time

zuru = time.time()
N = int(eval(input()))
A = [deque(list(map(int,input().split()))) for _ in range(N)]
match = 0
que = [0 for _ in range(N+1)]

for day in range(1, (N-1) * N // 2 + 1):
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    ans = -1
    break
  if match==(N-1) * N / 2:
    ans = day
    break
  if time.time()-zuru > 1.5:
    ans = N*(N-1)//2
    break
print(ans)
# Original solution
import sys

input = sys.stdin.readline

n = int(eval(input()))

e = [[] for _ in range(n)]
for i in range(n):
    a = list(map(int, input().split()))
    for aa in a:
        aa -= 1
        e[i].append(aa)
# print(e)

inds = [0] * n
cur = [e[i][0] for i in range(n)]
# print(cur)
cnt = 0
while sum(cur) != -n:
    flg = False
    bls = [False] * n
    for ind, target in enumerate(cur):
        if bls[ind] or bls[target]:
            continue
        if cur[target] == ind:
            flg = True
            inds[ind] += 1
            inds[target] += 1
            bls[ind] = True
            bls[target] = True
            cur[ind] = e[ind][inds[ind]] if inds[ind] < n - 1 else -1
            cur[target] = e[target][inds[target]] if inds[target] < n - 1 else -1
    if not flg:
        print((-1))
        exit()
    cnt += 1
    # print(cur, cnt)

print(cnt)


# Optimized solution
def check(player):
    if not a[player]:
        return
    opponent = a[player][-1]
    if not a[opponent]:
        return
    if a[opponent][-1] == player:
        tpl = (player, opponent)
        q.add((min(tpl), max(tpl)))


n = int(eval(input()))

a = []
for _ in range(n):
    t = list([int(x) - 1 for x in input().split()])
    t.reverse()
    a.append(t)

q = set()
for i in range(n):
    check(i)

day = 0
while q:
    day += 1
    prev_q = set()
    q, prev_q = prev_q, q
    for player, opponent in prev_q:
        a[player].pop()
        a[opponent].pop()
    for player, opponent in prev_q:
        check(player)
        check(opponent)

if any(a[player] for player in range(n)):
    print((-1))
    exit()

print(day)
# Original solution
# -*- coding: utf-8 -*-

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print((-1))
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print((N*(N-1)//2))
        exit()
print(day)


# Optimized solution
# -*- coding: utf-8 -*-

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(eval(input()))
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

start = time.time()

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print((-1))
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print((N*(N-1)//2))
        exit()
print(day)
# Original solution
n=int(eval(input()))

battle=[]

def mainasu(x):
    return int(x)-1
front=[]

for _ in range(n):
    tmp=list(map(mainasu,input().split()))[::-1]
    front.append(tmp.pop())
    battle.append(tmp)

day=0

#pri()
cnt=0
while 1:
    flag=0
    for i in range(n):
        if front[i]<n and i==front[front[i]]:
            flag=1
            front[front[i]]=n
            front[i]=n

    if flag==0:
        break

    cnt=0
    for i in range(n):
        if front[i]==n:
            if len(battle[i])>0:
                front[i]=battle[i].pop()
            else:
                cnt+=1
    day+=1
    

if cnt==n:
    print(day)
else:
    print((-1))            

    




# Optimized solution
n=int(eval(input()))

battle=[]

def mainasu(x):
    return int(x)-1

front=[]

for _ in range(n):
    tmp=list(map(mainasu,input().split()))[::-1]
    front.append(tmp.pop())
    battle.append(tmp)

def pri():
    global front,battle,day,checkday
    print((day,front,battle,checkday))

day=0

checkday=[-1]*n

#pri()
cnt=0
while 1:
    flag=0
    for i in range(n):
        if i<n and front[i]<n and i==front[front[i]] and checkday[i]<day and checkday[front[i]]<day:
            flag=1
            if len(battle[front[i]])>0:
                front[front[i]]=battle[front[i]].pop()
                checkday[front[i]]=day
            else:
                front[front[i]]=n
                cnt+=1
            
            if len(battle[i])>0:
                front[i]=battle[i].pop()
                checkday[i]=day
            else:
                front[i]=n
                cnt+=1
    #pri()
    if flag==0:
        break
    
    day+=1


if cnt==n:
    print(day)
else:
    print((-1))
# Original solution
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

A = [[]] + A

cnt = 0
ok = True
q = list(range(1, N+1))

for _ in range(N * (N - 1) // 2):
    can_match_today = [False] * (N+1)
    fin = True
    match = False
    nq = []
    for i in q:
        if can_match_today[i] or not A[i]:
            continue

        fin = False
        l = A[i][-1]

        if can_match_today[l]:
            continue
        r = A[l][-1]

        if r == i:
            match = True
            can_match_today[l] = True
            can_match_today[i] = True
            A[l].pop()
            A[i].pop()
            nq.append(l)
            nq.append(i)

    if fin:
        break

    if not match:
        ok = False
        break

    cnt += 1
    q = nq


if ok:
    print(cnt)
else:
    print((-1))


# Optimized solution
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

A = [[-1]] + A


def check(a, q=[]):
    if not A[a]:
        return False

    b = A[a][-1]
    b_op = A[b][-1]

    ok = False
    if a == b_op:
        ok = True

        if b < a:
            a, b = b, a
        q.append((a, b))

    return ok


q = []
for i in range(1, N + 1):
    check(i, q)

q = list(set(q))

day = 0
while q:
    nq = []
    for a, b in q:
        A[a].pop()
        A[b].pop()
        check(a, nq)
        check(b, nq)

    day += 1
    q = list(set(nq))

for i in range(1, N + 1):
    if len(A[i]) != 0:
        print((-1))
        exit()

print(day)
exit()