CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    r=[]
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        r+=i,
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print((-(len(r)<s)or m))
main()

# Optimized solution
def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    l=0
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        l+=1
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print((-(l<s)or m))
main()
# Original solution
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque,defaultdict



def solve():
  ## input
  N = int(eval(input()))
  An = [deque([i-1 for i in list(map(int, input().split()))]) for _ in range(N)]

  ## solve
  Pn = set([i for i in range(N)])
  count = 0
  while len(Pn) > 0:
    Qn = set([])
    dct = defaultdict(lambda:set([]))
    for i in Pn:
      if len(An[i]) == 0:
        continue
      j = An[i][0]
      if i in dct[j]:
        An[i].popleft()
        if len(An[i]) > 0:
          Qn = Qn | set([i,An[i][0]])        
        An[j].popleft()
        if len(An[j]) > 0:
          Qn = Qn | set([j,An[j][0]])        
      else:
        dct[i].add(j)
    Pn = Qn
    count += 1
  for i in range(N):
    if len(An[i]) > 0:
      return -1
  return count



print((solve()))

# Optimized solution
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque,defaultdict
from sys import stdin



def solve():
  ## input
  N = int(eval(input()))
  An = [deque([i-1 for i in list(map(int, stdin.readline().rstrip().split()))]) for _ in range(N)]

  ## solve
  Pn = set([i for i in range(N)])
  count = 0
  while len(Pn) > 0:
    Qn = set([])
    dct = defaultdict(lambda:set([]))
    for i in Pn:
      j = An[i][0]
      if i in dct[j]:
        An[i].popleft()
        if len(An[i]) > 0:
          Qn.add(i)
          Qn.add(An[i][0])
        An[j].popleft()
        if len(An[j]) > 0:
          Qn.add(j)
          Qn.add(An[j][0])
      else:
        dct[i].add(j)
    Pn = Qn
    count += 1
  for i in range(N):
    if len(An[i]) > 0:
      return -1
  return count



print((solve()))
# Original solution
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while True:
            if len(ql) != 0:
                d, ps = ql.popleft()
                if d == i:
                    if fq[ps]:
                        nw = a[ps][ls[ps]]
                        if fq[nw]:
                            rw = a[nw][ls[nw]]
                            if ps == rw:
                                ls[ps] += 1
                                ls[nw] += 1
                                if ls[ps] < n - 1:
                                    ql.append([d+1, ps])
                                if ls[nw] < n - 1:
                                    ql.append([d+1, nw])
                                fq[nw] = False
                                fq[ps] = False
                else:
                    ql.appendleft([d, ps])
                    break
            else:
                if sum(ls) == n * (n - 1):
                    print((i + 1))
                else:
                    print((-1))
                exit()


if __name__ == '__main__':
    solve()


# Optimized solution
import collections


def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    ad = [0] * n
    q = collections.deque([[0, i] for i in range(n)])
    for i in range(10 ** 20):
        fq = collections.defaultdict(list)
        while True:
            if len(q) != 0:
                d, p = q.popleft()
                if d == i:
                    if p not in fq:
                        tp = a[p][ad[p]]
                        if tp not in fq:
                            if p == a[tp][ad[tp]]:
                                fq[tp]
                                fq[p]
                                ad[tp] += 1
                                ad[p] += 1
                                if ad[tp] < n - 1:
                                    q.append([d+1, tp])
                                if ad[p] < n - 1:
                                    q.append([d+1, p])
                else:
                    q.appendleft([d, p])
                    break
            else:
                if sum(ad) == n * (n - 1):
                    print((i + 1))
                else:
                    print((-1))
                exit()


if __name__ == '__main__':
    slove()
# Original solution
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = [list([int(x) - 1 for x in input().rstrip('\n').split()]) for _ in range(n)]
    ps = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])
    for i in range(10 ** 10):
        fq = collections.defaultdict(int)
        while ql:
            d, p = ql.popleft()
            if d == i:
                if ps[p] < n - 1:
                    np = a[p][ps[p]]
                    if ps[np] < n - 1:
                        rp = a[np][ps[np]]
                        if p == rp:
                            if p not in fq and np not in fq:
                                fq[p]
                                fq[np]
                                ps[p] += 1
                                if ps[p] < n - 1:
                                    ql.append([d+1, p])
                                ps[np] += 1
                                if ps[np] < n - 1:
                                    ql.append([d+1, np])
            else:
                ql.appendleft([d, p])
                break
        else:
            print((i + 1 if sum(ps) == n * (n - 1) else -1))
            exit()


if __name__ == '__main__':
    solve()


# Optimized solution
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list([int(x) - 1 for x in readline().split()]) for _ in range(n)]
    ls = [0] * n
    ql = [[0, i] for i in range(n)]
    ql = collections.deque(ql)
    for i in range(10 ** 10):
        fq = collections.defaultdict(int)
        while ql:
            d, p = ql.popleft()
            if d == i:
                if ls[p] < n - 1:
                    rp = a[p][ls[p]]
                    if ls[rp] < n - 1:
                        rrp = a[rp][ls[rp]]
                        if p == rrp:
                            if p not in fq and rp not in fq:
                                fq[p]
                                fq[rp]
                                if ls[p] + 1 < n:
                                    ls[p] += 1
                                    ql.append([d+1, p])
                                if ls[rp] + 1 < n:
                                    ls[rp] += 1
                                    ql.append([d+1, rp])
            elif d > i:
                ql.appendleft([d, p])
                break
        if len(ql) == 0:
            print((i if sum(ls) == (n - 1) * n else -1))
            exit()


if __name__ == '__main__':
    solve()
# Original solution
import sys
input = sys.stdin.readline
from collections import deque

def main():
  n = int(eval(input()))
  U = n**2
  G = [[] for _ in range(U)]
  parent = [0]*U
  for i in range(n):
    A = list([int(x)-1 for x in input().split()])
    for j in range(n-2):
      a = A[j]
      b = A[j+1]
      G[min(i, a)*n+max(i, a)].append(min(i, b)*n+max(i, b))
      parent[min(i, b)*n+max(i, b)] += 1

  que = deque([(i*n+j, 1) for i in range(n-1) for j in range(i+1, n) if not parent[i*n+j]])
  ans = 1
  cnt = 0
  while que:
    v, t = que.pop()
    ans = max(ans, t)
    cnt += 1
    for nv in G[v]:
      parent[nv] -= 1
      if not parent[nv]:
        que.appendleft((nv, t+1))
  if cnt == n*(n-1)//2:
    print(ans)
  else:
    print((-1))
    
if __name__ == "__main__":
  main()

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

n = int(eval(input()))
U = n**2
G = [[] for _ in range(U)]
parent = [0]*U
for i in range(n):
  A = list([int(x)-1 for x in input().split()])
  for j in range(n-2):
    a = A[j]
    b = A[j+1]
    G[min(i, a)*n+max(i, a)].append(min(i, b)*n+max(i, b))
    parent[min(i, b)*n+max(i, b)] += 1

que = deque([(i*n+j, 1) for i in range(n-1) for j in range(i+1, n) if not parent[i*n+j]])
ans = 1
cnt = 0
while que:
  v, t = que.pop()
  ans = max(ans, t)
  cnt += 1
  for nv in G[v]:
    parent[nv] -= 1
    if not parent[nv]:
      que.appendleft((nv, t+1))
if cnt == n*(n-1)//2:
  print(ans)
else:
  print((-1))
# Original solution
n = int(eval(input()))
xss = [[int(x)-1 for x in input().split()] for _ in range(n)]

class Stack:
    def __init__(xs):
        self.__list = list(reversed(xs))

    def peak(self):
        return self.__list[-1]

    def pop(self):
        return self.pop()

def solve(n, xss):
    yss = [[-1] + list(reversed(xs)) for xs in xss]
    ans = 0
    while True:
        ms = list(matches(yss))
        if len(ms) == 0:
            if all(len(ys)==1 for ys in yss):
                return ans
            else:
                return -1
            return ans
        ans += 1
        for x, y in ms:
            yss[x].pop()
            yss[y].pop()

    for i in range(n):
        while len(yss[i]) > 0:
            match = find_first_match(yss, i)
            if match is None:
                return [-1]
            x, y = match
            ans

def matches(yss):
    firsts = [ys[-1] for ys in yss]
    for x, y in enumerate(firsts):
        if y!=-1 and x < y and firsts[y]==x:
            yield y, firsts[y]

print((solve(n, xss)))


# Optimized solution
n = int(eval(input()))
xss = [[int(x)-1 for x in input().split()] for _ in range(n)]

def solve(n, xss):
    yss = [[-1] + list(reversed(xs)) for xs in xss]
    ans = 0
    candidates = list(range(n))
    while True:
        #print(" ".join(map(str, candidates)))
        ms = list(matches(yss, candidates))
        if len(ms) == 0:
            if all(len(ys)==1 for ys in yss):
                return ans
            else:
                return -1
        ans += 1
        candidates = []
        #print(" ".join(map(str, ms)))
        for x, y in ms:
            yss[x].pop()
            yss[y].pop()
            candidates.append(x)
            candidates.append(y)

def matches(yss, candidates):
    firsts = [yss[i][-1] for i in candidates]
    ans = set()
    for x, y in zip(candidates, firsts):
        if y!=-1 and yss[y][-1] ==x:
            ans.add((min(x, y), max(x, y)))
    return ans

print((solve(n, xss)))
# Original solution
#E
import sys
input=sys.stdin.readline
from collections import defaultdict,deque
n=int(eval(input()))
v=n**2
A=[list([int(x)-1 for x in input().split()]) for _ in range(n)]
Edges=set()
for i in range(n):
    l=len(A[i])
    for j in range(l-1):
        a=A[i][j]
        b=A[i][j+1]
        fr_i,fr_j=min(i,a),max(i,a)
        to_i,to_j=min(i,b),max(i,b)
        Edges.add((fr_i*n+fr_j,to_i*n+to_j))
outs = defaultdict(list)
ins = defaultdict(int)
for v1, v2 in Edges:
    outs[v1].append(v2)
    ins[v2] += 1
q = deque((v1,1) for v1 in range(v) if ins[v1] == 0 and outs[v1])
res = []
while q:
    v1,d = q.popleft()
    res.append((v1,d))
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append((v2,d+1))
print((res[-1][1] if len(res)==n*(n-1)//2 else -1))

# Optimized solution
import sys
input=sys.stdin.readline
from collections import defaultdict,deque
def conv(n,a,b):
    return a*(2*n-a-1)//2+b-a-1

n=int(eval(input()))
v=n*(n-1)//2
A=[list([int(x)-1 for x in input().split()]) for _ in range(n)]
Edges=[]
for i in range(n):
    l=len(A[i])
    for j in range(l-1):
        a=A[i][j]
        b=A[i][j+1]
        fr_i,fr_j=min(i,a),max(i,a)
        to_i,to_j=min(i,b),max(i,b)
        Edges.append((conv(n,fr_i,fr_j),conv(n,to_i,to_j)))
Outs=defaultdict(list)
In_cnt=defaultdict(int)
for v1,v2 in Edges:
    Outs[v1].append(v2)
    In_cnt[v2]+=1
q=deque((v0,1) for v0 in range(v) if In_cnt[v0]==0)
TopologicalSort=[]
while q:
    v1,d=q.popleft()
    TopologicalSort.append((v1,d))
    for v2 in Outs[v1]:
        In_cnt[v2]-=1
        if In_cnt[v2]==0:
            q.append((v2,d+1))
print((TopologicalSort[-1][1] if len(TopologicalSort)==n*(n-1)//2 else -1))
# Original solution
import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 5
	n = int(eval(input()))
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print((-1))
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print((-1))
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print((-1))
	else:
		print(ans)
if __name__ == '__main__':
	main()

# Optimized solution
import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 4
	n = int(eval(input()))
	a = []
	for _ in range(n):
		a.append(tuple(map(int,input().split())))
	a = tuple(a)

	play = [0 for _ in range(n)]
	flag = [True for _ in range(n)]
	count = 0
	ans = 0
	while True:
		break_flag = True
		for i in range(n):
			if flag[i]:
				num = a[i][play[i]]-1
				if flag[num] and a[num][play[num]]-1 == i:
					play[num] += 1
					play[i] += 1
					flag[num] = False
					flag[i] = False
					break_flag = False
					count += 1
		if break_flag:
			print((-1))
			sys.exit()
		ans += 1

		if count == n*(n-1)//2:
			break
		if ans > limit:
			print((n*(n-1)//2))
			sys.exit()
		for i in range(n):
			if play[i] < n-1:
				flag[i] = True
			else:
				flag[i] = False

	if ans == 0:
		print((-1))
	else:
		print(ans)
if __name__ == '__main__':
	main()
# Original solution
n=int(eval(input()))
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  print((-1))

# Optimized solution
n=int(eval(input()))
import time
T=time.time()
data_set=[0 for i in range(n)]
for i in range(n):
    a=list(map(int,input().split()))
    a.append(-1)
    data_set[i]=a
index=[0 for i in range(n)]
ans=-1
flag=True
semi=False
now=[data_set[i][index[i]] for i in range(n)]
finished=[False for i in range(n)]
while flag:
    visited=[False for i in range(n)]
    sub=False
    for i in range(n):
        #nowリストのうち日ありからi+1番目のものについての一致条件の確認
        K=now[i]
        if now[K-1]==i+1 and not(visited[i] or visited[K-1]) and not(finished[i] or finished[K-1]):
                    visited[i]=True
                    visited[K-1]=True
                    index[i]+=1
                    index[K-1]+=1
                    sub=True
                    if index[i]==n-1:
                        finished[i]=True             
                    now[i]=data_set[i][index[i]]
                    if index[K-1]==n-1:
                        finished[K-1]=True                   
                    now[K-1]=data_set[K-1][index[K-1]]
    if not sub:
        flag=False
    if time.time()-T>1.5:
        flag=False
        semi=True
    ans+=1
judge=True
for i in range(n):
  if finished[i]==False:
    judge=False
    break
if judge:
  print(ans)
else:
  if not semi:
    print((-1))
  if semi:
    print((499500))
# Original solution
# atcoder problems solving
# League
from collections import deque
import sys
input = sys.stdin.readline
def main():
    N = int(eval(input()))
    graph = {(i, j): [] for i in range(1, N+1) for j in range(i+1, N+1)}
    indegree = {(i, j): 0 for i in range(1, N+1) for j in range(i+1, N+1)}

    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N-2):
            x, y = a[j], a[j+1]
            z, w = i+1, i+1
            graph[(min(z, x), max(z, x))].append((min(w, y), max(w, y)))
            indegree[(min(w, y), max(w, y))] += 1

    d = deque()
    e = deque()
    visited = {(i, j): False for i in range(1, N+1) for j in range(i+1, N+1)}

    cnt = 1
    match = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if indegree[(i, j)] == 0:
                d.append((i, j))
                visited[(i, j)] = True
                match += 1

    while d:
        while d:
            x = d.popleft()
            for node in graph[x]:
                indegree[node] -= 1
                if indegree[node] == 0:
                    e.append(node)
                    visited[node] = True
                    match += 1
        if e:
            d = e
            e = deque()
            cnt += 1

    if match == N*(N-1)//2:
        print(cnt)
    else:
        print((-1))
if __name__=="__main__":
    main()


# Optimized solution
# 休憩review
# League
from collections import deque
N = int(eval(input()))
G = [[] for i in range(N**2+1)]
for i in range(N):
    a = list(map(int, input().split()))
    for j in range(1, N-1):
        _from, _to = a[j-1], a[j]
        G[N*min(i+1, _from)-N+max(i+1, _from)
          ].append(N*min(i+1, _to)-N+max(i+1, _to))


In = [0 for i in range(N**2+1)]  # In[node] = node に入る入次数
for i in range(1, N**2+1):
    for node in G[i]:
        In[node] += 1


stack = deque()
for i in range(1, N**2+1):
    if In[i] == 0:
        stack.append(i)  # stack := 入次数が0になった点を入れておく


Removed = [False for i in range(N**2+1)]  # 考慮されたか
cnt = [1 for i in range(N**2+1)]


while stack:
    x = stack.popleft()
    Removed[x] = True
    for node in G[x]:
        In[node] -= 1
        if In[node] == 0:
            cnt[node] += cnt[x]
            stack.append(node)


all_checked = all(Removed[node] == True for node in range(1, N**2+1))
if all_checked:
    answer = max(cnt)
    print(answer)
    exit()
print((-1))
# Original solution
import sys

N = int(eval(input()))
A = [list([int(x) - 1 for x in input().split(" ")]) for i in range(N)]

canUse = set(range(N))

ans = 0
while any([len(i) > 0 for i in A]):
    # print("\nDay", ans)
    ans += 1
    canUseNew = set()
    for n in canUse:
        if not A[n]:
            continue

        first = A[n][-1]
        if first in canUseNew or n in canUseNew:
            continue

        if A[first][-1] == n:
            # print("Do", n + 1, first + 1)
            A[n].pop()
            A[first].pop()
            canUseNew.add(n)
            canUseNew.add(first)

    if len(canUseNew) == 0:
        print((-1))
        sys.exit(0)
    canUse = canUseNew

print(ans)


# Optimized solution
import sys

N = int(eval(input()))
A = [list([int(x) - 1 for x in input().split(" ")]) for i in range(N)]

canUse = set(range(N))

ans = 0
done = 0
while done < N:
    ans += 1
    canUseNew = set()
    # print("LC", len(canUse))
    for n in canUse:
        if not A[n]:
            continue

        first = A[n][-1]
        if first in canUseNew or n in canUseNew:
            continue

        if A[first][-1] == n:
            # print("Do", n + 1, first + 1)
            A[n].pop()
            if len(A[n]) == 0:
                done += 1
            A[first].pop()
            if len(A[first]) == 0:
                done += 1
            canUseNew.add(n)
            canUseNew.add(first)

    if len(canUseNew) == 0:
        print((-1))
        sys.exit(0)
    canUse = canUseNew

print(ans)
# Original solution
N = int(eval(input()))
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list([N-a for a in As])))
  A.append(As)
A.reverse()
#print(A)
d = 0
n = 0
while True:
  gs = []
  for i in range(N):
    if A[i] == []:
      continue
    j = A[i][-1]
    if j < i:
      continue
    if A[j] == []:
      continue
    if A[j][-1] == i:
      n += 1
      gs.append((i, j))
  if gs == []:
    if n == N*(N-1)//2:
      break
    print((-1))
    exit()
  for i, j in gs:
    A[i].pop()
    A[j].pop()
  d += 1
print(d)


# Optimized solution
N = int(eval(input()))
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list([a-1 for a in As])))
  A.append(As)
#print(A)
d = 0
n = 0
l = list(range(N))
while True:
  n2 = 0
  l2 = []
  s2 = set()
  for i in l:
    if A[i] == []:
      continue
    j = A[i][-1]
    if A[j] == []:
      continue
    if i in s2 or j in s2:
      continue
    if A[j][-1] == i:
      n += 1
      n2 += 1
      s2.add(i)
      s2.add(j)
      l2.append(i)
      l2.append(j)
      A[i].pop()
      A[j].pop()
  if n2 == 0:
    if n == N*(N-1)//2:
      break
    print((-1))
    exit()
  l = l2
  d += 1
print(d)