Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()

for i in range(n*(n-1)//2):
    check(i)
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    dfs_path(i)
print(max(max(finish), 1))

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
A = []
M = [[-1 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        M[i][j] = cnt
        M[j][i] = cnt
        cnt += 1
ans = 0
nodes = []
adjacent_list = [[] for i in range(n*(n-1)//2)]
for i in range(n):
    tmp = list(map(int, input().split()))
    pre = tmp[0] - 1
    for j in tmp[1:]:
        adjacent_list[M[i][pre]].append(M[i][j-1])
        pre = j - 1
#まず、閉路検
seen = defaultdict(lambda: False)
visited = defaultdict(lambda: False)
def check(node):
    if visited[node]:
        return
    seen[node] = True
    for i in adjacent_list[node]:
        if seen[i] and (not visited[i]):
            print(-1)
            exit()
        check(i)
    visited[node] = True
def dfs_path(node):
    if not adjacent_list[node]:
        return 1
    if finish[node]:
        return finish[node]
    tmp = 0
    for i in adjacent_list[node]:
        tmp = max(tmp, dfs_path(i) + 1)
    finish[node] = tmp
    return finish[node]
finished = set()
finish = [0 for i in range(n*(n-1)//2)]
for i in range(n*(n-1)//2):
    check(i)
    dfs_path(i)
print(max(max(finish), 1))
### BUGGY CODE ###

n,a,b =map(int, input().split())
c=2**n-1
def kai(n,x):
    result=1
    for i in range(x,n+1):
        result=result*i
    return result
A=kai(n,n-a+1)
B=kai(b,1)
C=kai(b,a+1)
D=kai(n-a,n-b+1)
c=c-A*(C+D)//B
print(c)

### FIXED CODE ###

n, a, b = map(int, input().split())
 

def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunshi = bunshi%mod
        bunbo *= a-i
        bunbo = bunbo%mod
        
    return bunshi*pow(bunbo, mod-2, mod)%mod
        
        
mod = 1000000007
answer = pow(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
b.append(0)
c.append(0)
a.sort()
b.sort()
c.sort()

def isok(na , index , key):
    if na[index] >= key:
        return True
    else:
        return False
    
def bs(nar,key):
    left = -1
    right = len(nar)
    
    while (right - left) > 1:
        mid = left + (right - left) // 2
        
        if isok(nar , mid , key):
            right = mid
        else:
            left = mid
            
    return right

ans = 0
for i in a:
    q = bs(b,i+1)
    d = b[q:]
    
    for j in d:
        r = bs(c,j+1)
        f = c[r:]
        ans += len(f)
        
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()

def isok(na , index , key):
    if na[index] >= key:
        return True
    else:
        return False
    
def bs(nar,key):
    left = -1
    right = len(nar)
    
    while (right - left) > 1:
        mid = left + (right - left) // 2
        
        if isok(nar , mid , key):
            right = mid
        else:
            left = mid
            
    return right

ans = 0
for i in b:
    q = bs(a,i)
    r = bs(c,i+1)
    
    ans += q*(n-r)
print(ans)
### BUGGY CODE ###

#5_numpy で最後は計算
import numpy as np

int_n = int(input())
list_x = list(map(int, input().split()))
 

list_x_left = list_x
list_calc_minus = list()
 
while len(list_x_left) != 0:
  
  int_list_x_prosess_len = len(list_x_left) - list_x_left.index(max(list_x_left))
  int_max_list_x_prosess = max(list_x_left)
  list_x_left = list_x_left[:list_x_left.index(max(list_x_left))]
  
  [list_calc_minus.insert(0, int_max_list_x_prosess) for i in range(int_list_x_prosess_len)]
  
#print(sum([x - y for (x, y) in zip(list_calc_minus, list_x)]))

print((np.array(list_calc_minus) - np.array(list_x)).sum())
 

### FIXED CODE ###

int_n = int(input())
list_a = list(map(int, input().split()))

#print(int_n, list_a)

int_tmp_highet = 0
int_count = 0
for i in list_a:
  if i > int_tmp_highet:
    int_tmp_highet = i
  else:
    int_count = int_count + int_tmp_highet - i
  #print(int_count)

print(int_count)
### BUGGY CODE ###

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    edges[l-1].append((r-1, d))
    edges[r-1].append((l-1, -d))

visited = {}
# その人へのパスが複数あり、距離が異なる場合は矛盾
for i in range(N):
    if i in visited:
        continue

    # 連結グラフごとに相対的な距離を決定
    dist = [0 for _ in range(N)]
    q = deque([(i, 0)])
    while q:
        l, c = q.popleft()
        if l in visited:
            if visited[l] != c:
                print("No")
                sys.exit()
            continue
        
        visited[l] = c
        dist[l] = c

        for r, nd in edges[l]:
            q.append((r, c+nd))
    # print(dist)

print("Yes")

### FIXED CODE ###

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

edges = [[] for _ in range(N)]
for _ in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    edges[l-1].append((r-1, d))
    edges[r-1].append((l-1, -d))

visited = {}
# その人へのパスが複数あり、距離が異なる場合は矛盾
for i in range(N):
    if i in visited:
        continue

    # 連結グラフごとに相対的な距離を決定
    # dist = [0 for _ in range(N)]
    q = deque([(i, 0)])
    while q:
        l, c = q.popleft()
        if l in visited:
            if visited[l] != c:
                print("No")
                sys.exit()
            continue
        
        visited[l] = c
        # dist[l] = c

        for r, nd in edges[l]:
            q.append((r, c+nd))
    # print(dist)

print("Yes")
### BUGGY CODE ###

X = int(input())

ans = 0
loc = 0
while loc < X:
    ans += 1
    for i in range(ans):
        loc += 1
print(ans)

### FIXED CODE ###

X = int(input())

ans, loc = 0, 0

while loc < X:
    ans += 1
    loc = ans/2 * (ans+1)
print(ans)
### BUGGY CODE ###

from collections import Counter
s = input()
t = input()


def iter(string, dic):
    for i in range(len(string)):
        if string[i] in dic.keys():
            dic[string[i]] += 1
        else:
            dic[string[i]] = 1
    return dic


s_pattern = Counter(s)
t_pattern = Counter(t)


def check(string, original):
    count = 0
    length = len(string)
    flag = False
    while 1:
        if string == original:
            flag = True
            break
        if count == length:
            flag = False
            break
        last = string[-1]
        string = last + string[:-1]
    return flag


if s_pattern != t_pattern:
    print('No')
else:
    if check(s, t):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

from collections import Counter
s = input()
t = input()


s_pattern = Counter(s)
t_pattern = Counter(t)


def check(string, original):
    n = len(string)
    flag = False
    for i in range(n):
        if original == string[i:] + s[:i]:
            flag = True
            break
    return flag


if s_pattern != t_pattern:
    print('No')
else:
    if check(s, t):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from math import cos, sin, pi
from itertools import combinations
N, L = map(int, input().split())
T = [int(input()) for _ in range(N)]
PI2oL = 2*pi/L

csum, ssum = 0, 0
count = 0
for i, j in combinations(range(N), 2):
    count += 1
    mid1, num2 = (T[i] + T[j]) / 2, j - i - 1
    mid2, num1 = (mid1 + L/2) % L, N - num2 - 2
    csum += cos(PI2oL*mid1) * num1 + cos(PI2oL*mid2) * num2
    ssum += sin(PI2oL*mid1) * num1 + sin(PI2oL*mid2) * num2

print(csum/count/(N-2)*3, ssum/count/(N-2)*3)


### FIXED CODE ###

from math import cos, sin, pi
from itertools import combinations
N, L = map(int, input().split())
T = [int(input()) for _ in range(N)]
PI2oL = 2*pi/L

csum, ssum = 0, 0
count = 0
for i, j in combinations(range(N), 2):
    count += 1
    mid1, num2 = (T[i] + T[j]) / 2, j - i - 1
    mid2, num1 = (mid1 + L/2) % L, N - num2 - 2
    csum += cos(PI2oL*mid1) * num1 + cos(PI2oL*mid2) * num2
    ssum += sin(PI2oL*mid1) * num1 + sin(PI2oL*mid2) * num2

print(csum/count/(N-2)*3, ssum/count/(N-2)*3)
### BUGGY CODE ###

A,B,N = map(int,input().split())

max = 0
for i in range(1,N+1):
    m = int(A*i/B)-A*int(i/B)
    if m>max:
        # print('i:', i)
        # print('m:', m)
        max = m
# print(max)

if N<B: m=N
else: m=B-1



l = int(A*m/B)-A*int(m/B)
print(l)

### FIXED CODE ###

A,B,N = map(int,input().split())

if N<B: m=N
else: m=B-1

l = int(A*m/B)-A*int(m/B)
print(l)
### BUGGY CODE ###

n, k = map(int, input().split())
ls = list(map(int, input().split()))
m = [0 for l in range(0, k)]
for i in range(0,len(ls)):
    for j in range(0,len(m)):
        if m[j]<ls[i]:
            c = m[j:]
            m[j] = ls[i]
            m[j+1:] = c[:-1]
            break
print(sum(ls)-sum(m))

### FIXED CODE ###

n, k = map(int, input().split())
ls = list(map(int, input().split()))

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

ll = merge_sort(ls)
if n <= k:
    print(0)
else:
    print(sum(ll[:n-k]))
### BUGGY CODE ###

def sl_insert(vals:list, new_val):
    l = 0
    r = len(vals)
    while l < r:
        m = (l + r) // 2
        if vals[m] == new_val:
            vals.insert(m, new_val)
            return
        elif vals[m] < new_val:
            l = m + 1
        else:
            r = m
    vals.insert(l, new_val)
    return

n, q = map(int, input().split())
events = []

for i in range(n):
    s, t, x = map(int, input().split())
    if t >= x:
        events.append([t - x, 0, x])
        events.append([s - x, 1, x])
for i in range(q):
    d = int(input())
    events.append([d, 2, i])
events.sort()

dist = [-1] * q
walker = []
working = []
for t, kind, x in events:
    if kind == 0:
        working.remove(x)
    elif kind == 1:
        sl_insert(working, x)
    elif any(working):
        dist[x] = working[0]
    else:
        walker.append(x)

for d in dist:
    print(d)

### FIXED CODE ###

from heapq import heappush, heappop


n, q = map(int, input().split())
events = []

for i in range(n):
    s, t, x = map(int, input().split())
    if t >= x:
        events.append([t - x, 0, x])
        events.append([s - x, 1, x])
for i in range(q):
    d = int(input())
    events.append([d, 2, i])
events.sort()

dist = [-1] * q
walker = []
working = set()
heap = []
for t, kind, x in events:
    if kind == 0:
        working.remove(x)
    elif kind == 1:
        working.add(x)
        heappush(heap, x)
    elif working:
        while not heap[0] in working:
            heappop(heap)
        dist[x] = heap[0]

for d in dist:
    print(d)
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
set_a = set(a)
ans = 0

for ai in set_a:
  ai_count = a.count(ai)
  if ai_count >= ai:
  	ans += ai_count - ai  
  else:
    ans += ai_count

print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
a = [int(i) for i in input().split()]

cnt = Counter(a)
ans = 0

for ai, num in cnt.items():
  if num >= ai:
  	ans += num - ai  
  else:
    ans += num

print(ans)
### BUGGY CODE ###

def main():
    N, M  = [int(i) for i in input().split()]
    S  = [i == '1' for i in input()]
    cur = [(0, [])]
    while cur:
        nxt = []
        for loc, hist in cur:
            for i in range(1, M + 1):
                nloc = loc + i
                if nloc == N:
                    return ' '.join(str(j) for j in hist + [i])
                elif nloc > N:
                    continue
                elif S[nloc]:
                    continue
                S[nloc] = True
                nxt.append((nloc, hist + [i]))
        cur = nxt
    return '-1'


print(main())


### FIXED CODE ###

def main():
    N, M  = [int(i) for i in input().split()]
    S  = [int(i) for i in input()]
    loc = N
    a = []
    while loc:
        for i in range(min(loc, M), 0, -1):
            if S[loc - i] == 1:
                continue
            a.append(i)
            loc -= i
            break
        else:
            return '-1'
    return ' '.join(str(i) for i in reversed(a))


print(main())
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
  ans *= a[i]
if(ans > 1000000000000000000):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]
if(0 in a):
  print(0)
  exit()
  
for i in range(1, n):
  ans *= a[i]
  if(ans > 1000000000000000000):
    print(-1)
    exit()
  
print(ans)
### BUGGY CODE ###

from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

R, G, B, N = [int(x) for x in stdin.readline().rstrip().split()]

cnt = 0
RN = N // R + 1
GN = N // G + 1
BN = N // B + 1

for i in range(RN):
    for j in range(GN):
        for k in range(BN):
            num = R * i + G * j + B * k
            if num > N:
                break
            if num == N:
                cnt+=1

print(cnt)

### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

R, G, B, N = [int(x) for x in stdin.readline().rstrip().split()]

cnt = 0
R, G, B = sorted([R, G, B])
RN = N // R + 1
GN = N // G + 1
BN = N // B + 1

cnt = 0
for i in range(RN):
    tmpN = N - R*i
    if tmpN % G == 0:
        cnt += 1
    for j in range(GN):
        tmpN2 = tmpN - G*j
        if tmpN2 > 0 and tmpN2 % B == 0:
            cnt += 1
    

print(cnt)
### BUGGY CODE ###

import collections
import itertools
N = int(input())
S = [input() for _ in range(N)]
S_cnt = [collections.Counter(s) for s in S]

cnt=0
for i, j in itertools.combinations(S_cnt, 2):
    if i==j:
        cnt+=1
print(cnt)

### FIXED CODE ###

import itertools
import collections
N = int(input())
S = [[str(x) for x in input()] for _ in range(N)]
S = [''.join(sorted(x)) for x in S]

cnt=0
reg = collections.defaultdict(int)
for s in S:
    reg[s] += 1
    if reg[s] > 1:
        cnt += reg[s] - 1
print(cnt)
### BUGGY CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main(n,x):
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    ans=[]
    b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                ans.append(0)
            else:
                xx=( xmodm1 + (m-1) -b%(m-1) )%(m-1)
                ans.append(f(xx)+1)
        else:
            xx=( xmodp1 + b%(m+1) )%(m+1)
            ans.append(f(xx)+1)
        b=b//2
    return ans

if __name__=='__main__':
    n,x=readinput()
    ans=main(n,x)
    for a in ans:
        print(a)



### FIXED CODE ###

def readinput():
    n=int(input())
    x=input()
    return n,x

poptbl=[0]*(2*10**5+1)
def popcount(x):
    global poptbl
    if poptbl[x]!=0:
        return poptbl[x]
    
    poptbl[x]=bin(x).count('1')
    return poptbl[x]

ftbl=[0]*(2*10**5+1)
def f(x):
    global ftbl

    if ftbl[x]!=0:
        return ftbl[x]
    
    #print('f(x), x: {}'.format(x))
    if x==0:
        return 0
    else:
        ans=f(x%popcount(x))+1
        #print(ans)
        ftbl[x]=ans
        return ans    

def main():
    n=int(input())
    x=input()
    m=x.count('1')
    #print('m: {}'.format(m))
    xint=int(x,2)
    #print('xint: {}'.format(xint))
    if m!=1:
        xmodm1=xint%(m-1)
    else:
        xmodm1=1
    xmodp1=xint%(m+1)
    pow2mod1=[0]*n
    pow2mod2=[0]*n
    pow2mod1[0]=1
    pow2mod2[0]=1
    for i in range(1,n):
        if m!=1:
            pow2mod1[i]=pow2mod1[i-1]*2 % (m-1)
        pow2mod2[i]=pow2mod2[i-1]*2 % (m+1)

    ans=[]
    #b=2**(n-1)
    for i in range(n):
        if x[i]=='1':
            if m==1:
                a=0
                ans.append(a)
            else:
                xx=( xmodm1 + (m-1) -pow2mod1[n-i-1] )%(m-1)
                #ans.append(f(xx)+1)
                a=f(xx)+1
                ans.append(a)
        else:
            xx=( xmodp1 + pow2mod2[n-i-1] )%(m+1)
            #ans.append(f(xx)+1)
            a=f(xx)+1
            ans.append(a)
        #b=b//2
        print(a)
    return ans

if __name__=='__main__':
    #n,x=readinput()
    ans=main()
    #for a in ans:
    #    print(a)
### BUGGY CODE ###

N,K = map(int,input().split())
count = 0


for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            a = (i+j) % K
            b = (j+k) % K
            c = (k+i) % K
            if a == 0 and b == 0 and c == 0:
                count += 1
print(count)


### FIXED CODE ###

N, K = map(int,input().split())
count_0 = 0
count_2 = 0

for i in range(1,N+1):
    if i % K == 0:
        count_0 += 1
    if i % K == K / 2:
        count_2 += 1
if K % 2 == 0:
    print(count_0**3 + count_2**3)
else:
    print(count_0**3)
### BUGGY CODE ###

N, M = map(int, input().split())

g = [[] for _ in range(N)]

A, B = [0]*M, [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    g[A[i]-1].append(B[i]-1)
    g[B[i]-1].append(A[i]-1)

ans_list = [-1] * N

queue = [0]
seen = []

while queue:
    Q = len(queue)
    #print("now", queue, ans_list)
    for _ in range(Q):
        now = queue.pop(0)
        seen.append(now)
        for n in g[now]:
            if ans_list[n] == -1:
                ans_list[n] = now
            # キューに次の距離の要素を追加
            if n not in seen:
                queue.append(n)

print("Yes")
for ans in ans_list[1:]:
    print(ans+1)  # 1-index に直す


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    g = [[] for _ in range(N)]

    A, B = [0]*M, [0]*M
    for i in range(M):
        A[i], B[i] = map(int, input().split())
        g[A[i]-1].append(B[i]-1)
        g[B[i]-1].append(A[i]-1)

    ans_list = [-1] * N

    queue = [0]
    seen = [False]*N

    while queue:
        qi = queue.pop(0)
        # qi から 1 遠い頂点が gi
        for gi in g[qi]:
            if seen[gi] == False:
                queue.append(gi)
                if ans_list[gi] == -1:
                    ans_list[gi] = qi
                    seen[gi] = True

    print("Yes")
    for ans in ans_list[1:]:
        print(ans+1)  # 1-index に直す

if __name__ == "__main__":
    main()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
l=0; r=0; res=0; sum_=0; ans=[]
for _ in range(10**6):
    if l == N and r == N:
        break
    note = r
    for i in range(r,N):
        if res ^ A[i] == sum_ + A[i]:
            r += 1
            res += A[i]
            sum_ += A[i]
        else:
            break
    length = r - l
    f = note == r
    if f is False:
        for i in range(l,r+1):
            for j in range(i+1,r+1):
                ans.append((i,j))
    if length == 0:
        r += 1
    else:
        res -= A[l]
        sum_ -= A[l]
    l += 1
ans = len(list(set((ans))))
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
r = 0; sum_ = 0; res = 0; ans = 0
for l in range(N+1):
    for i in range(r,N):
        if res ^ A[i] == sum_ + A[i]:
            r += 1
            res += A[i]
            sum_ += A[i]
        else:
            break
    length = r - l
    ans += length
    if length == 0:
        r += 1
    else:
        res -= A[l]
        sum_ -= A[l]

print(ans)
### BUGGY CODE ###

N = int(input())
import math
n = math.floor(N**0.5)
P = []
for i in range(2,n+1):
    J = 1
    for j in range(len(P)):
        if i % P[j] != 0:
            J = 0
            break
    if J == 1:
        P.append(i)
A = [1]
for i in range(len(P)):
    p = P[i]
    x = 1
    j = 1
    while x**j <= N :
        if x**j <= N:
            A.append(x**j)
ans = max(A)
print(ans)

### FIXED CODE ###

N = int(input())
import math
n = math.floor(N**0.5)

A = [1]
for i in range(2,n+1):
    j = 2
    while i**j <= N :
        A.append(i**j)
        j += 1
ans = max(A)
print(ans)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline
def main():
	n = int(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()
			break
		ans += 1

		if count == n*(n-1)//2:
			break
		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()

### FIXED CODE ###

import sys
readline = sys.stdin.readline
def main():
	limit = 10 ** 4
	n = int(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()