CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

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

    adj = defaultdict(list)
    in_num = defaultdict(int)
    for i in range(N):
        for j in range(N-2):
            x1 = x2= i+1
            y1 = A[i][j]
            y2 = A[i][j+1]
            if x1 > y1:
                x1, y1 = y1, x1
            if x2 > y2:
                x2, y2 = y2, x2
            adj[(x1, y1)].append((x2, y2))
            in_num[(x2, y2)] += 1
    st = []
    ng = (N * (N - 1)) // 2
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if in_num[(i, j)] == 0:
                st.append((i, j))
                ng -= 1
    ans = 0
    while st:
        ans += 1
        st_new = []
        for par in st:
            for child in adj[par]:
                if in_num[child] == 1:
                    st_new.append(child)
                    ng -= 1
                in_num[child] -= 1
        if st_new:
            st = st_new
        else:
            break

    if ng:
        print((-1))
    else:
        print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.buffer.readline

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

    adj = defaultdict(list)
    in_num = defaultdict(int)
    for i in range(N):
        for j in range(N-2):
            x1 = x2 = i+1
            y1 = A[i][j]
            y2 = A[i][j+1]
            if x1 > y1:
                x1, y1 = y1, x1
            if x2 > y2:
                x2, y2 = y2, x2
            adj[x1*(N+1)+y1].append(x2*(N+1)+y2)
            in_num[x2*(N+1)+y2] += 1
    st = []
    ng = (N * (N - 1)) // 2
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if in_num[i*(N+1)+j] == 0:
                st.append(i*(N+1)+j)
                ng -= 1
    ans = 0
    while st:
        ans += 1
        st_new = []
        for par in st:
            for child in adj[par]:
                if in_num[child] == 1:
                    st_new.append(child)
                    ng -= 1
                in_num[child] -= 1
        if st_new:
            st = st_new
        else:
            break

    if ng:
        print((-1))
    else:
        print(ans)


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

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

adj = defaultdict(list)
in_deg = defaultdict(int)
for u, row in enumerate(a, 1):
    for v1, v2 in zip(row, row[1:]):
        uu1, vv1 = min(u, v1), max(u, v1)
        uu2, vv2 = min(u, v2), max(u, v2)
        adj[(uu1, vv1)].append((uu2, vv2))
        in_deg[(uu1, vv1)]
        in_deg[(uu2, vv2)] += 1

now = [tpl for tpl, val in list(in_deg.items()) if val == 0]
day = 0
while now:
    day += 1
    nxt = []
    for u in now:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt.append(v)

    now = nxt

if max(in_deg.values()) > 0:
    day = -1

print(day)


# Optimized solution
from collections import defaultdict

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

adj = defaultdict(list)
in_deg = defaultdict(int)
for u, row in enumerate(a, 1):
    for v1, v2 in zip(row, row[1:]):
        uu1, vv1 = min(u, v1), max(u, v1)
        uu2, vv2 = min(u, v2), max(u, v2)
        match1 = uu1 + vv1 * 1000
        match2 = uu2 + vv2 * 1000
        adj[match1].append(match2)
        in_deg[match1]
        in_deg[match2] += 1

now = [key for key, val in list(in_deg.items()) if val == 0]
day = 0
while now:
    day += 1
    nxt = []
    for u in now:
        for v in adj[u]:
            in_deg[v] -= 1
            if in_deg[v] == 0:
                nxt.append(v)

    now = nxt

if max(in_deg.values()) > 0:
    day = -1

print(day)
# Original solution
def resolve():
    n = int(eval(input()))
    am = []

    from collections import deque

    for i in range(n):
        am.append(deque(list([int(x) - 1 for x in input().split()])))

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

    day = 0
    while cnt > 0:
        day += 1
        match = 0
        done = {}
        for i in range(n):
            if i in done:
                continue
            if len(am[i]) == 0:
                continue
            j = am[i][0]
            if j < i:
                continue
            if j not in done and am[j][0] == i:
                am[i].popleft()
                am[j].popleft()
                done[i] = 1
                done[j] = 1
                match += 1

        if match == 0:
            print((-1))
            return
        else:
            cnt -= match

    print(day)
    
resolve()

# Optimized solution
def resolve():
    n = int(eval(input()))
    a = []

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

    q = set()

    def check(i):
        if len(a[i]) == 0:
            return
        j = a[i][-1]
        if i == a[j][-1]:
            p = (i, j) if i < j else (j, i)
            q.add(p)

    for i in range(n):
        check(i)

    day = 0
    while len(q) > 0:
        day += 1
        prev_q, q = q, set()

        for p in prev_q:
            (i, j) = p
            a[i].pop()
            a[j].pop()

        for p in prev_q:
            (i, j) = p
            check(i)
            check(j)

    for i in range(n):
        if len(a[i]) != 0:
            print((-1))
            return
    print(day)
    
resolve()
# Original solution
from collections import deque
n=int(eval(input()))
a=[deque(list(map(int,input().split()))) for _ in range(n)] 
tcnt,ans=0,0
while tcnt<n*(n-1)//2:
    cnt=0
    chk=[]
    for i in range(n-1):
        if i in chk:
            continue
        else:
            if a[i]:
                b=a[i][0]-1
                if b in chk:
                    continue
                else:
                    if b>i and a[b][0]-1==i:
                        chk.append(a[i].popleft()-1)
                        a[b].popleft()
                        cnt+=1
    tcnt+=cnt
    ans+=1
    if cnt==0:
        ans=-1
        break
print(ans)

# Optimized solution
from collections import deque
n=int(eval(input()))
x=lambda i:int(i)-1
a=[deque(list(map(x,input().split()))+[-1]) for _ in range(n)] 
tcnt,ans=n*(n-1),0
chk=set(range(n))
while tcnt>0:
    chk_next=set()
    for i in chk:
        if a[a[i][0]][0]==i:
            chk_next.add(i)
    if len(chk_next)==0:
        ans=-1
        break
    tcnt-=len(chk_next)
    chk=set()
    for i in chk_next:
        a[i].popleft()
        chk.add(i)
        if a[i][0]!=-1:
            chk.add(a[i][0])
    ans+=1

print(ans)
# Original solution
import sys


def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    used = [False] * n
    game_count = 0
    total_game_count = n * (n-1) // 2
    while game_count != total_game_count:
        found = False
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        for i in range(n):
            used[i] = False
        ans += 1
        if not found:
            print((-1))
            return
    print(ans)


main()


# Optimized solution
import sys
import time

def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1.7):
            print('-1')
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print((-1))
            return
    print(ans)


main()
# Original solution
n = int(eval(input()))
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] #それぞれ何試合目か
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] #今日試合をするかどうか
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 # firstが対戦したい相手
            second_num = s[second] # #secondの対戦番号
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print((-1))
        exit()
print(ans)

# Optimized solution
import time
start = time.time()
n = int(eval(input()))
a = [list(map(int,input().split())) for _ in range(n)]
s = [0 for i in range(n)] #それぞれ何試合目か
ans = 0
need = n*(n-1)//2
while need:
    c = [0 for i in range(n)] #今日試合をするかどうか
    ans += 1
    for first in range(n):
        if c[first] == 0 and s[first] < n-1:
            second = a[first][s[first]]-1 # firstが対戦したい相手
            second_num = s[second] # #secondの対戦番号
            if c[second] == 0 and a[second][second_num]-1 == first:
                c[first] = 1
                c[second] = 1
                s[first] += 1
                s[second] += 1
                need -= 1
    if sum(c) == 0:
        print((-1))
        exit()
    now = time.time()-start
    if now > 1.8:
        print((n*(n-1)//2))
        exit()
print(ans)
# Original solution
import copy
n = int(eval(input()))
# 隣接リスト
graph = {i+1000*j:set() for i in range(n) for j in range(i+1,n)}
# 入次数を管理
st = {i+1000*j:0 for i in range(n) for j in range(i+1,n)}

#たどったかどうかチェック
check = {i+1000*j:True for i in range(n) for j in range(i+1,n)}

# 入次数が0の頂点の集まり
szero = []

#ソートされたやつたち
ans = []

for i in range(n):
    ls = list(map(int,input().split()))
    f = -1
    for p in ls:
        v = min(i,p-1) + 1000*(max(i,p-1))
        if f != -1:
            graph[f].add(v)
            st[v] += 1
        f = v

for v in list(st.keys()):
    if st[v] == 0:szero.append(v)
count = 0
next_szero = []
while True:
    count += 1
    for i in szero:
        ans.append(i)
        for v in graph[i]:
            #if check[v]:check[v] = False
            #else:continue
            st[v] -= 1
            if st[v] == 0:
                next_szero.append(v)
    if len(next_szero) == 0:break
    szero = copy.deepcopy(next_szero)
    next_szero = []

if len(ans) != n*(n-1)//2:
    print((-1))
else:
    print(count)

# Optimized solution
n = int(eval(input()))
# 隣接リスト
graph = {i+1000*j:[] for i in range(n) for j in range(i+1,n)}
# 入次数を管理
st = {i+1000*j:0 for i in range(n) for j in range(i+1,n)}


# 入次数が0の頂点の集まり
szero = []

#ソートされたやつたち
ans = []

for i in range(n):
    ls = list(map(int,input().split()))
    f = -1
    for p in ls:
        v = min(i,p-1) + 1000*(max(i,p-1))
        if f != -1:
            graph[f].append(v)
            st[v] += 1
        f = v

for v in list(st.keys()):
    if st[v] == 0:szero.append(v)
count = 0
next_szero = []
while True:
    count += 1
    for i in szero:
        ans.append(i)
        for v in graph[i]:
            st[v] -= 1
            if st[v] == 0:
                next_szero.append(v)
    if len(next_szero) == 0:break
    szero = next_szero
    next_szero = []

if len(ans) != n*(n-1)//2:
    print((-1))
else:
    print(count)
# Original solution
import sys
input = sys.stdin.readline

N = int(eval(input()))
A = [list([int(n)-1 for n in input().split()]) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print((-1))


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

N = int(eval(input()))
A = [list([int(n)-1 for n in input().split()]) for i in range(N)]
cur = [0 for i in range(N)]
que = [i for i in range(N)]
ans = 0
while len(que) > 0:
    done = {}
    que2 = []
    for n in que:
        if done.get(n):
            continue
        pair = A[n][cur[n]]
        if done.get(pair):
            continue
        if n == A[pair][cur[pair]]:
            cur[n] += 1
            cur[pair] += 1
            done[n] = True
            done[pair] = True
            if cur[n] < N-1:
                que2.append(n)
            if cur[pair] < N-1:
                que2.append(pair)
    if len(done) > 0:
        ans += 1
    que = que2
ok = True
for i in range(N):
    if cur[i] < N-1:
        ok = False
if ok:
    print(ans)
else:
    print((-1))
# Original solution
import sys
sys.setrecursionlimit(10**7)
def dfs(v,s):
    global c
    seen[v]=True
    for nv in G[v]:
        if seen[nv]:
            if nv in s:
                c=True
            continue
        dfs(nv,s|{v})
    srted.append(v)
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(eval(input()))
A=[list([int(x)-1 for x in input().split()]) for i in range(N)]
P=setID()
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
c=False
seen=[False]*P
srted=[]
for i in range(P):
    if not seen[i]:
        dfs(i,set())
if c:
    print((-1))
    exit()
dp=[1]*P
for v in reversed(srted):
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print((max(dp)))

# Optimized solution
import sys
sys.setrecursionlimit(10**7)
def dfs(v,s):
    global c
    if c:
        return
    seen[v]=True
    for nv in G[v]:
        if seen[nv]:
            if nv in s:
                c=True
                return
            continue
        dfs(nv,s|{v})
    srted.append(v)
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(eval(input()))
A=[list([int(x)-1 for x in input().split()]) for i in range(N)]
P=setID()
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
c=False
seen=[False]*P
srted=[]
for i in range(P):
    if not seen[i]:
        dfs(i,set())
if c:
    print((-1))
    exit()
dp=[1]*P
for v in reversed(srted):
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print((max(dp)))
# Original solution
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(eval(input()))

    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    matchs = []
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            matchs.append((i,j))

    edges = {}
    for match in matchs:
        edges[match] = []
        i,j = match
        if reverseMemo[i][j] != N-1:
            nx = A[i][reverseMemo[i][j]+1]
            edges[match].append((min(i,nx),max(i,nx)))
        if reverseMemo[j][i] != N-1:
            nx = A[j][reverseMemo[j][i]+1]
            edges[match].append((min(j,nx),max(j,nx)))

    stepMemo = {}
    def dfs(i,j,cnt):
        if cnt > N*N:
            print((-1))
            exit()
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,cnt+1)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j,1))
    print(ans)
main()




# Optimized solution
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(eval(input()))

    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    matchs = []
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            matchs.append((i,j))

    edges = {}
    for match in matchs:
        edges[match] = []
        i,j = match
        if reverseMemo[i][j] != N-1:
            nx = A[i][reverseMemo[i][j]+1]
            edges[match].append((min(i,nx),max(i,nx)))
        if reverseMemo[j][i] != N-1:
            nx = A[j][reverseMemo[j][i]+1]
            edges[match].append((min(j,nx),max(j,nx)))

    stepMemo = {}
    def dfs(i,j,cnt):
        if cnt > len(matchs):
            print((-1))
            exit()
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,cnt+1)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j,1))
    print(ans)
main()
# Original solution
def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(eval(input()))
    A = [[]]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))

    #AR[i][j] => iにとって選手jとの試合が何番目か
    AR = [[]]
    for i in range(1,N+1):
        AR.append([0]*(N+1))
        for j in range(1,N):
            b = A[i][j]
            AR[i][b] = j

    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            edges[(i,j)] = []
            jForI = AR[i][j]
            if jForI < N-1:
                nxForI = A[i][jForI+1]
                edges[(i,j)].append((min(i,nxForI),max(i,nxForI)))
            iForJ = AR[j][i]
            if iForJ < N-1:
                nxForJ = A[j][iForJ+1]
                edges[(i,j)].append((min(j,nxForJ),max(j,nxForJ)))

    steps = {}
    def dfs(i,j):
        #iとjの試合を1日目とし、試合終了まで何日かかるかを返す。
        if (i,j) not in steps:
            steps[(i,j)] = 0
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b)+1)
            steps[(i,j)] = res
        elif steps[(i,j)] == 0:
            print((-1))
            exit()
        return steps[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j))
    print(ans)
main()

# Optimized solution
def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(eval(input()))
    A = [[]]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))

    #AR[i][j] => iにとって選手jとの試合が何番目か
    AR = [[]]
    for i in range(1,N+1):
        AR.append([0]*(N+1))
        for j in range(1,N):
            b = A[i][j]
            AR[i][b] = j

    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            edges[(i,j)] = []
            jForI = AR[i][j]
            if jForI < N-1:
                nxForI = A[i][jForI+1]
                edges[(i,j)].append((min(i,nxForI),max(i,nxForI)))
            iForJ = AR[j][i]
            if iForJ < N-1:
                nxForJ = A[j][iForJ+1]
                edges[(i,j)].append((min(j,nxForJ),max(j,nxForJ)))
    del A
    del AR

    steps = {}
    def dfs(i,j):
        #iとjの試合を1日目とし、試合終了まで何日かかるかを返す。
        if (i,j) not in steps:
            steps[(i,j)] = 0
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b)+1)
            steps[(i,j)] = res
        elif steps[(i,j)] == 0:
            print((-1))
            exit()
        return steps[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j))
    print(ans)
main()
# Original solution
N=int(eval(input()))
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
from collections import deque
q=deque()

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
  q=sorted(q)
  prevQ=q.copy()
  q=deque()
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print((-1))
    break
else:
  print(day)

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

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print((-1))
    break
else:
  print(day)