CodeEff/ECCO huggingface dataset:
# Original solution
import time
s_time = time.time()


n = int(eval(input()))
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print((-1))
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print((n*(n-1) //2))
print(cnt)


# Optimized solution
import time
s_time = time.time()


n = int(eval(input()))
a = [list(map(int, input().split())) for i in range(n)]

memo = {}
for i in range(n):
    memo[i] = 0

cnt = 0
while True:
    visited = [False] * n
    flag = False
    for i in range(n):
        if memo[i] == len(a[0]):
            continue
        if visited[i] or visited[a[i][memo[i]] - 1]:
            continue
        visited[i] = True
        if i + 1 == a[a[i][memo[i]] - 1][memo[a[i][memo[i]] - 1]]:
            visited[a[i][memo[i]] - 1] = True
            flag = True
            tmp = memo[i]
            memo[i] += 1
            memo[a[i][tmp] - 1] += 1
    if flag:
        cnt += 1
    else:
        for i in memo:
            if memo[i] != len(a[0]):
                print((-1))
                exit()
        break
    if abs(s_time - time.time()) > 1.7:
        print((n*(n-1) //2))
        exit()
print(cnt)
# Original solution
import collections as cl,sys
input = sys.stdin.readline
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(eval(input()))
n = onem()

on = cl.deque()
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)


# Optimized solution
import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(eval(input()))
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)
# Original solution

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(eval(input()))
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 2000:
            ans = M+1
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print((-1))
    else:
        print(ans)


main()


# Optimized solution

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(eval(input()))
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 2:
            ans = M+1
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print((-1))
    else:
        print(ans)


main()
# Original solution
from copy import deepcopy

n = int(eval(input()))
a = [list([int(x) - 1 for x in input().split()]) for _ in range(n)]

d = [0] * n

ans = 0
temp = set([x for x in range(n)])
while 1:
    next_temp = set()
    for t in temp:
        if d[t] >= n - 1:
            continue
        u = a[t][d[t]]
        if a[u][d[u]] == t:
            next_temp.add(t)
            next_temp.add(u)
    #print(next_temp, d)
    for t in next_temp:
        d[t] += 1
    if len(next_temp) == 0:
        break
    temp = deepcopy(next_temp)
    ans += 1

if d.count(n-1) == n:
    print(ans)
else:
    print((-1))

# Optimized solution
from copy import deepcopy
from heapq import heappop, heappush

n = int(eval(input()))
a = [list([int(x) - 1 for x in input().split()]) for _ in range(n)]

d = [0] * n

ans = 0
temp = []
for x in range(n):
    heappush(temp, x)
while 1:
    next_temp = []
    while len(temp) > 0:
        x = heappop(temp)
        if d[x] >= n-1:
            continue
        y = a[x][d[x]]
        #print(x, y)
        if y not in next_temp:
            if a[y][d[y]] == x:
                heappush(next_temp, x)
                heappush(next_temp, y)
    #print(next_temp)
    for t in next_temp:
        d[t] += 1
    if len(next_temp) == 0:
        break
    temp = [] + next_temp
    ans += 1

#print(d)

if d.count(n-1) == n:
    print(ans)
else:
    print((-1))
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import deque
 
def getN():
    return int(eval(input()))
def getList():
    return list(map(int, input().split()))
import math
 
n = getN()
 
match = [0 for i in range((n*(n-1))//2)]
child = [[] for i in range((n*(n-1))//2)]
isroot = [True for i in range((n*(n-1))//2)]
 
 
def bfs():
    q = deque([])
    for root, rt in enumerate(isroot):
        if rt:
            q.append(root)
            match[root] = 1
    # print(match)
    while(q):
        item = q.popleft()
        # print(q, item, child[item])
        for ch in child[item]:
            if match[ch] < match[item] + 1:
                match[ch] = match[item] + 1
                q.append(ch)
 
    return
 
 
 
 
for idd in range(n):
    nums = getList()
    i = idd + 1
    for j,k in zip(nums, nums[1:]):
        ii, j = min(i, j), max(i,j)
        iii, k = min(i, k), max(i,k)
        idx1 = ((j-1)*(j-2))//2 + (ii-1)
        idx2 = ((k - 1) * (k - 2)) // 2 + (iii - 1)
        isroot[idx2] = False
        child[idx1].append(idx2)
        # print(i, j, k)
        # print(idx1, idx2)
 
#
# print(child)
# print(isroot)
# # sys.exit()
 
bfs()
# print("gg")
ans = 1
for m in match:
    if m > ans:
        ans = m
    if m == 0:
        print((-1))
        sys.exit()
 
print(ans)
 

# Optimized solution
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import deque


def getN():
    return int(eval(input()))


def getList():
    return list(map(int, input().split()))


import math

n = getN()

match = [0 for i in range((n * (n - 1)) // 2)]
child = [[] for i in range((n * (n - 1)) // 2)]
iriji = [0 for i in range((n * (n - 1)) // 2)]


def toposo(n, iriji, child):
    order = [0 for i in range((n*(n+1))//2)]
    q = deque([])
    for i, iri in enumerate(iriji):
        if iri == 0:
            q.append(i)
            order[i] = 1
    while(q):
        start = q.popleft()
        target = child[start]
        for tgt in target:
            iriji[tgt] -= 1
            if iriji[tgt] == 0:
                q.append(tgt)
                order[tgt] = order[start] + 1

    if sum(iriji) != 0:
        return -1

    else:
        return max(order)


for idd in range(n):
    nums = getList()
    i = idd + 1
    for j, k in zip(nums, nums[1:]):
        ii, j = min(i, j), max(i, j)
        iii, k = min(i, k), max(i, k)
        idx1 = ((j - 1) * (j - 2)) // 2 + (ii - 1)
        idx2 = ((k - 1) * (k - 2)) // 2 + (iii - 1)
        iriji[idx2] += 1
        child[idx1].append(idx2)
        # print(i, j, k)
        # print(idx1, idx2)

#
# print(child)
# print(isroot)
# # sys.exit()
#
# bfs()
# # print("gg")
# ans = 1
# for m in match:
#     if m > ans:
#         ans = m
#     if m == 0:
#         print(-1)
#         sys.exit()
# print(iriji, child)

print((toposo(n, iriji, child)))
# Original solution
import sys
read = sys.stdin.readline


def main():
    n = int(read())
    V = 1000000

    g = [[] for _ in range(V)]
    deg = [0] * V
    vlist = [False] * V

    for i in range(n):
        a = list([int(x) - 1 for x in read().rstrip().split()])
        for j in range(n - 2):
            v1 = min(i, a[j]) * 1000 + max(i, a[j])
            v2 = min(i, a[j + 1]) * 1000 + max(i, a[j + 1])
            vlist[v1] = True
            vlist[v2] = True
            g[v1].append(v2)
            deg[v2] += 1

    d = [0] * V
    check_cnt = 0
    q = []
    for v in range(V):
        if vlist[v] and deg[v] == 0:
            q.append(v)

    if len(q) == 0:
        print((-1))
        exit()

    for v in q:
        check_cnt += 1
        for nv in g[v]:
            d[nv] = max(d[nv], d[v] + 1)
            deg[nv] -= 1
            if deg[nv] == 0:
                q.append(nv)
    if check_cnt == n * (n - 1) // 2:
        print((max(d) + 1))
    else:
        print((-1))


if __name__ == '__main__':
    main()


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


def main():
    n = int(read())
    V = 1000000

    g = [[] for _ in range(V)]
    deg = [0] * V
    vlist = set()

    for i in range(n):
        a = list([int(x) - 1 for x in read().rstrip().split()])
        for j in range(n - 1):
            v1 = min(i, a[j]) * 1000 + max(i, a[j])
            vlist.add(v1)
            if j == n - 2:
                break
            v2 = min(i, a[j + 1]) * 1000 + max(i, a[j + 1])
            g[v1].append(v2)
            deg[v2] += 1

    d = [0] * V
    check_cnt = 0
    q = []
    for v in vlist:
        if deg[v] == 0:
            q.append(v)

    if len(q) == 0:
        print((-1))
        exit()

    for v in q:
        check_cnt += 1
        for nv in g[v]:
            d[nv] = max(d[nv], d[v] + 1)
            deg[nv] -= 1
            if deg[nv] == 0:
                q.append(nv)
    if check_cnt == n * (n - 1) // 2:
        print((max(d) + 1))
    else:
        print((-1))


if __name__ == '__main__':
    main()
# Original solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    idx = [0] * N
    d = 0
    while True:
        c = [False] * N
        for i in range(N):
            if idx[i] >= N - 1: continue
            if c[i]: continue
            m = A[i][idx[i]]
            if A[m][idx[m]] == i:
                c[i] = True
                c[m] = True
        f = False
        for i in range(N):
            if c[i]:
                idx[i] += 1
                f = True
        if not f:
            print((-1))
            return
        d += 1
        if all([idx[i] >= N - 1 for i in range(N)]):
            print(d)
            return

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(eval(input()))
    A = [list([int(x) - 1 for x in input().split()]) for _ in range(N)]
    main(N, A)


# Optimized solution
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    idx = [0] * N
    D = [[-1] * (N) for _ in range(N)]
    for j in range(N):
        D[j][0] = 0
    while True:
        f = True
        for i in range(N):
            if idx[i] >= N - 1: continue
            m = A[i][idx[i]]
            if A[m][idx[m]] == i:
                d = max(D[i][idx[i]], D[m][idx[m]])
                idx[i] += 1
                idx[m] += 1
                D[i][idx[i]] = d + 1
                D[m][idx[m]] = d + 1
                f = False
        if f: break
    ans = -1
    for i in range(N):
        ans = max(ans, D[i][N - 1])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(eval(input()))
    A = [list([int(x) - 1 for x in input().split()]) for _ in range(N)]
    main(N, A)
# Original solution
def main():
    N = int(eval(input()))
    A = [list(reversed(list([int(x) - 1 for x in input().split()]))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
        if not nxt:
            return -1
        for i in set(nxt):
            if A[i]:
                w[i] = A[i].pop()
            else:
                w[i] = -1
                r -= 1
        cur = nxt
    return d


print((main()))


# Optimized solution
def main():
    N = int(eval(input()))
    A = [list(reversed(list([int(x) - 1 for x in input().split()]))) for _ in range(N)]
    d = 0
    r = N
    cur = list(range(N))
    w = [a.pop() for a in A]
    while r:
        d += 1
        nxt = []
        for i in cur:
            o = w[i]
            if o == -1:
                continue
            if w[o] == i:
                nxt.append(i)
                nxt.append(o)
                w[i] = -1
                w[o] = -1
        if not nxt:
            return -1
        cur = []
        for i in nxt:
            if A[i]:
                w[i] = A[i].pop()
                cur.append(i)
            else:
                r -= 1
    return d


print((main()))
# Original solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(eval(input()))
    a = [list(map(int, input().split())) for _ in range(n)]
    b = [0]*n
    cnt = 0
    while True:
        f = 0
        f2 = 0
        sumi = [0]*n
        for i in range(n):
            if sumi[i] == 1 or b[i] == n-1:
                f2 += 1
                continue
            aite = a[i][b[i]] - 1
            if a[aite][b[aite]]-1 == i and sumi[aite]==0:
                f = 1
                b[i] += 1
                b[aite] += 1
                sumi[i] = 1
                sumi[aite] = 1
        if f2==n:
            break
        elif f:
            cnt += 1
        else:
            print((-1))
            exit()
    print(cnt)

if __name__ == '__main__':
    main()

# Optimized solution
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(eval(input()))
    a = []
    for _ in range(n):
        a.append(deque(list(map(int, input().split()))))
    
    siai = n*(n-1)
    d = [0]*n

    while siai:
        f = 0
        for i in range(n):
            while a[i] and a[a[i][0]-1][0] == i+1:
                f = 1
                day = max(d[i], d[a[i][0]-1])
                d[i] = day + 1
                d[a[i][0]-1] = day + 1
                siai -= 2
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if not f:
            print((-1))
            break
    else:
        print((max(d)))

if __name__ == '__main__':
    main()
# Original solution
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(eval(input()))
a = [[min(i,int(j)-1)+max(i,int(j)-1)*(max(i,int(j)-1)-1)//2 for j in readline().split()] for i in range(n)]

N =n*(n-1)//2

g = [[] for i in range(N)]
p = [[] for i in range(N)]

for i in range(n):
    for j in range(n-2):
        g[a[i][j]].append(a[i][j+1])
        p[a[i][j+1]].append(a[i][j])
        
#print(g)
#print(p)

ans = [0]*(N)

indegree = [len(v) for v in p] # 流入辺の数を数えた配列
Source = [i for i, c in enumerate(indegree) if c == 0] #流入辺0の点の集合
#L = [] #ソート結果をためておく配列
num = 0
while Source:
    node = Source.pop()
    #L.append(node)
    num += 1
    for child in g[node]:
        indegree[child] -= 1 #辺 node -> child を削除する
        if ans[child] < ans[node]+1: ans[child] = ans[node]+1     
        if indegree[child] == 0:
            Source.append(child)

#print(num)
if num != N:
    print((-1))
else:
    print((max(ans)+1))

#print(ans)
    


# Optimized solution
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n = int(eval(input()))
N =n*(n-1)//2

a = [[int(j)-1 for j in readline().split()] for _ in range(n)]
g = [[] for i in range(N)]
indegree = [0]*N

def encode(x,y):
    if x > y: x,y = y,x
    return y*(y-1)//2 + x

for i in range(n):
    for j in range(n-2):
        p,q = encode(i,a[i][j]), encode(i,a[i][j+1])
        g[p].append(q)
        indegree[q] += 1

"""
トポロジカルソート
q をheapq にしたりすると、辞書順にとりだしたりとかができる。
返り値：DAG ならトポソのひとつを返す。ループがあれば-1を返す
"""
"""
g: グラフの隣接行列
indegree: 流入辺の数を数えた配列
"""
def topological_sort_queue(g,indegree):
    q = [i for i,c in enumerate(indegree) if c == 0] #流入辺0の点の集合
    L = [] #ソート結果をためておく配列
    ans =[0]*len(g)
    a = 0
    while q:
        v = q.pop()
        L.append(v)
        for c in g[v]: #配る
            ans[c] = max(ans[c],ans[v]+1)
            a = max(a,ans[c])
            indegree[c] -= 1 #辺 node -> child を削除する
            if indegree[c] == 0:
                q.append(c)
    if len(L) != N: #print("サイクル検出")
        return -1
    else: #return(L)
        return(a+1)        

print((topological_sort_queue(g,indegree)))
# Original solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

N = int(eval(input()))

A = [0 for i in range(N)]
for i in range(N) :
    L = list(map(int,input().split()))
    for j in range(len(L)) :
        L[j] -= 1
    A[i] = deque(L)

#print(A)
ans = 0
flg = 0

zuru = 0

while flg == 0 :
    zuru += 1
    cnt = 0
    cnt2 = 0
    flg = 1

    if zuru >= 10**5 :
        ans = 499500
        print(ans)
        exit()
    
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1

print(ans)


# Optimized solution
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

N = int(eval(input()))

A = [0 for i in range(N)]
for i in range(N) :
    L = list(map(int,input().split()))
    for j in range(len(L)) :
        L[j] -= 1
    A[i] = deque(L)

#print(A)
ans = 0
flg = 0

zuru = 0

while flg == 0 :
    zuru += 1
    cnt = 0
    cnt2 = 0
    flg = 1

    if zuru >= 10**4 :
        ans = 499500
        print(ans)
        exit()
    
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1

print(ans)