CodeEff/ECCO huggingface dataset:
# Original solution
import sys
import time
def solve(matrix):
    N = len(matrix)
    #print  matrix
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    start = time.time()
    while remaining:
        prev = remaining
        day+=1
        #print "day %d" % day
        #print "matrix: %r" % matrix
        #print "remaining:%d" % remaining
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                #print "%d and %d" % (x, y)
                #print "matrix: %r" % matrix
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                #print 'match: %r' % match
        if time.time() - start > 1.6:
            print(worst)
            return
        if remaining  == prev:
            print(-1)
            return
    print(day)



N = input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in input().split()])
solve(matrix)

# Optimized solution
import sys
import time
def solve(matrix):
    N = len(matrix)
    #print  matrix
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    start = time.time()
    while remaining:
        prev = remaining
        day+=1
        #print "day %d" % day
        #print "matrix: %r" % matrix
        #print "remaining:%d" % remaining
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                #print "%d and %d" % (x, y)
                #print "matrix: %r" % matrix
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                #print 'match: %r' % match
        if time.time() - start > 1.5:
            print(worst)
            return
        if remaining  == prev:
            print(-1)
            return
    print(day)



N = input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in input().split()])
solve(matrix)
# Original solution
import sys
from collections import deque

sys.setrecursionlimit(10000000)

n = int(sys.stdin.readline().rstrip())
a = [deque(list(map(int, sys.stdin.readline().split()))) for _ in range(n)]

def deepPop(x):
    global a
    global days
    target = a[x][0] -1
    if a[target][0] -1 == x:
        a[target].popleft()
        a[x].popleft()
        maxd = max(days[x] +1, days[target] +1)
        days[x] = maxd
        days[target] = maxd
        if len(a[x]) > 0:
            deepPop(x)
        if len(a[target]) > 0:
            deepPop(target)


day = 0
days = [0] * n
setn = set(range(n))
while True:
    popped = 0
    zeros = 0
    tmpns = list(setn)
    for i in tmpns:
        if len(a[i]) == 0:
            setn.remove(i)
            continue
        num = a[i][0] - 1
        if num < i:
            continue
        if a[num][0] - 1 == i:
            deepPop(i)
            popped += 1
    if popped == 0:
        if len(setn) == 0:
            break
        else:
            day = -1
            break

if day == -1:
    print(day)
else:
    print((max(days)))


# Optimized solution
import sys
from collections import deque

n = int(eval(input()))
a = [deque(list(map(int, sys.stdin.readline().rstrip().split()))) for _ in range(n)]

current = []

for i in range(n):
    target = a[i][0] -1
    if a[target][0] -1 == i and i < target:
        current.append([i, target])

day = 0
zc = 0
while True:
    popped = 0
    plist = set()
    zeros = 0
    tc = []
    for i in current:
        a[i[0]].popleft()
        a[i[1]].popleft()
        if len(a[i[0]]) > 0:
            plist.add(i[0])
        else:
            zc += 1
        if len(a[i[1]]) > 0:
            plist.add(i[1])
        else:
            zc += 1
    for i in plist:
        target = a[i][0] -1
        if a[target][0] -1 == i:
            if not target in plist or i < target:
                tc.append([i, target])
    day += 1
    if len(tc) == 0:
        break
    current = tc

if zc != n:
    day = -1

print(day)
# Original solution
import sys
import copy
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]

answer = 0
match = 0

candidate = list(range(N))
while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print((-1))
        exit()

print(answer)


# Optimized solution
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]
answer = 0
match = 0
candidate = list(range(N))
while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0] - 1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print((-1))
        exit()

print(answer)
# Original solution
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque([(i, x) for x in lr()]) for i in range(1, N+1)]
day = 0
candidate = set()
match = 0
for i in range(N):
    c = A[i].popleft()
    candidate.add(c)

while candidate:
    day += 1
    used = set()
    next = set()
    rmv = set()
    for a, b in candidate:
        if a in used or b in used:
            continue
        if (b, a) in candidate:
            rmv.add((a, b))
            rmv.add((b, a))
            match += 1
            if A[a-1]:
                x = A[a-1].popleft()
                next.add(x)
            if A[b-1]:
                y = A[b-1].popleft()
                next.add(y)
            used.add(a)
            used.add(b)
    candidate -= rmv
    if match == N * (N-1) // 2:
        break
    candidate |= next
    if not used:
        print((-1)); exit()

print(day)
# 10


# Optimized solution
import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque([(i, x) for x in lr()]) for i in range(1, N+1)]
day = 0
candidate = set()
match = 0
for i in range(N):
    c = A[i][0]
    candidate.add(c)

while candidate:
    day += 1
    used = set()
    next = set()
    for a, b in candidate:
        if a in used or b in used:
            continue
        if A[b-1][0] == (b, a):
            match += 1
            A[a-1].popleft()
            A[b-1].popleft()
            if A[a-1]:                
                next.add(A[a-1][0])
            if A[b-1]:
                next.add(A[b-1][0])
            used.add(a)
            used.add(b)
    if match == N * (N-1) // 2:
        break
    candidate = next
    if not used:
        print((-1)); exit()

print(day)
# 10
# Original solution
from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(eval(input()))
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            if target < i:
                continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if len(Q) != 0:
                print((-1))
                return
            else:
                raise ValueError("test")
        for i in pool:
            A[i].pop()
            if len(A[i]) == 0:
                Q.remove(i)

        count += 1
        if len(Q) == 0:
            print(count)
            return


if __name__ == '__main__':
    main()


# Optimized solution
from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(eval(input()))
    # A, B = [int(a) for a in input().split()]
    # H = [int(a) for a in input().split()]
    A = {
        i: list(reversed([int(a) - 1 for a in input().split()]))
        for i in range(N)
    }

    Q = set(range(N))

    count = 0
    while True:
        pool = []
        for i in Q:
            ai = A[i]
            if len(ai) == 0:
                continue
            target = ai[-1]
            # if target < i:
            #     continue
            target_q = A[target]
            if target_q[-1] == i:
                # print(i,target)
                pool.append(i)
                pool.append(target)

        if len(pool) == 0:
            if len(Q) != 0:
                print((-1))
                return
            else:
                raise ValueError("test")

        qq = []
        for i in set(pool):
            A[i].pop()
            if len(A[i]) != 0:
                qq.append(i)
        Q = set(qq)

        count += 1
        if len(Q) == 0:
            print(count)
            return


if __name__ == '__main__':
    main()
# Original solution
import sys
input = sys.stdin.readline

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

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
for _ in range(max_pairs // 2):
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print((-1))
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print((-1))
        quit()

    cnt += 1

print(cnt)

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

import sys
input = sys.stdin.readline

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

cur = [0] * N

max_pairs = N * (N - 1)

pairs = 0
cnt = 1
for _ in range(max_pairs // 2):
    visited = [False] * N
    for i, a in enumerate(A):
        if cur[i] >= N - 1:
            continue
        p = a[cur[i]]
        if A[p][cur[p]] == i:
            # print(cnt, p + 1, A[p][cur[p]] + 1, i + 1)
            visited[i] = True
            visited[a[cur[i]]] = True
            pairs += 1

    # print(pairs)
    if pairs == max_pairs:
        break
    if pairs > max_pairs:
        print((-1))
        quit()

    update = False
    for i, v in enumerate(visited):
        if v:
            cur[i] += 1
            update = True

    if not update:
        print((-1))
        quit()

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

    cnt += 1

print(cnt)
# Original solution
import sys
from collections import deque
input = sys.stdin.readline

n = int(eval(input()))

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]

day_count = 0
remained_battles = (n * (n - 1)) // 2

while remained_battles:
    battled_today = set()

    no_battle_today = True
    for player in range(n):
        if not to_battle_with[player]:
            continue

        next_opponent = to_battle_with[player][0]
        if player in battled_today or next_opponent in battled_today:
            continue

        if not to_battle_with[next_opponent]:
            continue

        if to_battle_with[next_opponent][0] == player:
            battled_today.add(next_opponent)
            battled_today.add(player)
            to_battle_with[player].popleft()
            to_battle_with[next_opponent].popleft()
            remained_battles -= 1
            no_battle_today = False
    if no_battle_today:
        print((-1))
        break
    day_count += 1

if not no_battle_today:
    print(day_count)


# Optimized solution
import sys
from collections import deque

input = sys.stdin.readline

n = int(eval(input()))

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]


def update_battle(player, battle_set, to_battle_with):
    if not to_battle_with[player]:
        return
    next_opponent = to_battle_with[player][0]
    if not to_battle_with[next_opponent]:
        return
    if to_battle_with[next_opponent][0] == player:
        if player > next_opponent:
            player, next_opponent = next_opponent, player
        battle_set.add((player, next_opponent))


battles_today = set()
for player in range(n):
    update_battle(player, battles_today, to_battle_with)

day_count = 0
battle_count = 0
num_all_battles = (n * (n - 1)) // 2

while battles_today:
    battles_tomorrow = set()
    for p1, p2 in battles_today:
        battle_count += 1
        to_battle_with[p1].popleft()
        to_battle_with[p2].popleft()
        for p in [p1, p2]:
            update_battle(p, battles_tomorrow, to_battle_with)
    battles_today = battles_tomorrow
    day_count += 1

if battle_count == num_all_battles:
    print(day_count)
else:
    print((-1))
# Original solution
import sys 
input=sys.stdin.readline

def main():
    N=int(eval(input()))
    L=[[]]
    
    for i in range(N):
        a=list(map(int,input().split()))
        L.append(a)
    #print(L)
    Z=[0 for i in range(N+1)]
    day=0
    cnt=0
    for i in range(10**6+5):
        if cnt==N*(N-1)/2:
            break
        D=dict()
        CNT=0
        for j in range(1,N+1):
            if Z[j]==N-1 or j in D:
                continue
            elif L[L[j][Z[j]]][Z[L[j][Z[j]]]]==j and L[j][Z[j]] not in D:
                D[j]=1
                D[L[j][Z[j]]]=1
                X=L[j][Z[j]]
                Z[j]+=1
                Z[X]+=1
                CNT+=1
        if CNT==0:
            print((-1))
            exit()
        cnt+=CNT
        day+=1
    #print(L)
    #print(cnt)
    print(day)
if __name__ == '__main__':
    main()

# Optimized solution
N=int(eval(input()))
A=[[0]]
for i in range(N):
    a=list(map(int,input().split()))
    a+=[0]
    A.append(a)
    
#print(A)
B=[0 for i in range(N+1)]
C=[a for a in range(1,N+1)]
cnt=0
for i in range(10**6):
    D=[]
    F=0
    for j in C:
        if A[A[j][B[j]]][B[A[j][B[j]]]]==j and j not in D and A[j][B[j]] not in D:
            D.append(j)
            D.append(A[j][B[j]])
            B[A[j][B[j]]]+=1
            B[j]+=1
            F=1
            cnt+=1
            #print("A",i,B,D)
            #print(A[j][B[j]],B,D)
    if F==0:
        break
    D.sort()
    C=D
    
if cnt==N*(N-1)//2:
    print(i)
else:
    print((-1))
# Original solution
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return list(map(int,input().split()))
def I():
    return int(eval(input()))
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
k=0
ans=0
MacthNum=0
yet=set(range(n))
n_yet=set(range(n))
while flg and MacthNum<n*(n-1)//2:
    ans+=1
    IsMatch=False
    done=set()
    #print('Day',ans,IsMatch,nx)
    for i in yet:
        if (i in done) or (nx[i] in done) or nx[i]==n:
            continue
        c1=i
        c2=nx[i]
        if c1==nx[c2]:
            IsMatch=True
            MacthNum+=1
            #print('Day',ans,'Match',c1,'vs',c2)
            if t[c1]:
                n_i=t[c1].pop()
            else:
                n_i=n
                n_yet.remove(c1)
            if t[c2]:
                n_n_i=t[c2].pop()
            else:
                n_n_i=n
                n_yet.remove(c2)
            #print(i,nx[i],nx)
            nx[nx[i]],nx[i]=n_n_i,n_i
            done.add(c1)
            done.add(c2)
            #print('i,t,d',i,t,'done=',done,'nx=',nx,n_i,n_n_i)
    yet=[i for i in n_yet]
    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

print(ans)


# Optimized solution
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
import time
ts=time.time()
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return list(map(int,input().split()))
def I():
    return int(eval(input()))
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
ans=0
MacthNum=0
yet=set(range(n))
n_yet=set(range(n))
while flg and MacthNum<n*(n-1)//2:
    elp=time.time()-ts
    if elp>1.8:
        ans=n*(n-1)//2
        break
    ans+=1
    IsMatch=False
    done=set()
    for i in yet:
        if (i in done) or (nx[i] in done) or nx[i]==n:
            continue
        c1=i
        c2=nx[i]
        if c1==nx[c2]:
            IsMatch=True
            MacthNum+=1
            if t[c1]:
                n_i=t[c1].pop()
            else:
                n_i=n
                n_yet.remove(c1)
            if t[c2]:
                n_n_i=t[c2].pop()
            else:
                n_n_i=n
                n_yet.remove(c2)
            nx[nx[i]],nx[i]=n_n_i,n_i
            done.add(c1)
            done.add(c2)
    yet=[i for i in n_yet]
    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

print(ans)
# Original solution
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
import time
ts=time.time()
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return list(map(int,input().split()))
def I():
    return int(eval(input()))
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
ans=0
MacthNum=0
yet=set(range(n))
n_yet=set(range(n))
while flg and MacthNum<n*(n-1)//2:
    elp=time.time()-ts
    if elp>1.8:
        ans=n*(n-1)//2
        break
    ans+=1
    IsMatch=False
    done=set()
    for i in yet:
        if (i in done) or (nx[i] in done) or nx[i]==n:
            continue
        c1=i
        c2=nx[i]
        if c1==nx[c2]:
            IsMatch=True
            MacthNum+=1
            if t[c1]:
                n_i=t[c1].pop()
            else:
                n_i=n
                n_yet.remove(c1)
            if t[c2]:
                n_n_i=t[c2].pop()
            else:
                n_n_i=n
                n_yet.remove(c2)
            nx[nx[i]],nx[i]=n_n_i,n_i
            done.add(c1)
            done.add(c2)
    yet=[i for i in n_yet]
    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

print(ans)


# Optimized solution
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
import time
ts=time.time()
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return list(map(int,input().split()))
def I():
    return int(eval(input()))
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
t=[]
d=[]
nx=[0]*n
for i in range(n):
    a=[i-1 for i in LI()[::-1]]
    nx[i]=a.pop()
    t.append(a)
    d.append([-1]*(n))

flg=True
ans=0
MacthNum=0
yet=set(range(n))
n_yet=set(range(n))
while flg and MacthNum<n*(n-1)//2:
    elp=time.time()-ts
    if elp>1.8:
        ans=0#n*(n-1)//2
        break
    ans+=1
    IsMatch=False
    done=set()
    n_yet=[]
    #print('Day',ans,IsMatch,nx)
    for i in yet:
        if (i in done) or (nx[i] in done) or nx[i]==n:
            continue
        c1=i
        c2=nx[i]
        if c1==nx[c2]:
            IsMatch=True
            MacthNum+=1
            #print('Day',ans,'Match',c1,'vs',c2)
            if t[c1]:
                n_i=t[c1].pop()
                n_yet.append(c1)
            else:
                n_i=n
            if t[c2]:
                n_n_i=t[c2].pop()
                n_yet.append(c2)
            else:
                n_n_i=n
            #print(i,nx[i],nx)
            nx[nx[i]],nx[i]=n_n_i,n_i
            done.add(c1)
            done.add(c2)
            #print('i,t,d',i,t,'done=',done,'nx=',nx,n_i,n_n_i)
    yet=[i for i in n_yet]
    ans=ans if IsMatch else -1
    flg=True if IsMatch else False

print(ans)
# Original solution
N = int(eval(input()))
aaa = []
for i in range(N):
  aaa.append(list(reversed(list(map(int, input().split())))))

for i in range(0, N*N+1):
  done = [False] * N
  empty = True
  played = False
  for j, aa in enumerate(aaa):
    if len(aa) > 0:
      empty = False
      l = aa[-1]-1
      if (not (done[j] or done[l])) and len(aaa[l]) > 0 and aaa[l][-1] == j+1:
          aa.pop()
          aaa[l].pop()
          done[j], done[l] = True, True
          played = True
  if empty:
    print(i)
    break
  elif not played:
    print((-1))
    break

# Optimized solution
N = int(eval(input()))
aaa = []
for i in range(N):
  aaa.append(list(reversed(list(map(int, input().split())))))

cs = set(range(N))
for i in range(0, N*N+1):
  empty = True
  played = False
  ncs = set()
  for j in cs:
    aa = aaa[j]
    if len(aa) > 0:
      empty = False
      l = aa[-1]-1
      if j not in ncs and l not in ncs and len(aaa[l]) > 0 and aaa[l][-1] == j+1:
          aa.pop()
          aaa[l].pop()
          played = True
          ncs.add(j)
          ncs.add(l)
  cs = ncs
  if empty:
    print(i)
    break
  elif not played:
    print((-1))
    break