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

from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())

if (N == 1):
    print("First")
    quit()

tree = defaultdict(list)
nodes_len = defaultdict(list)
for i in range(N):
    nodes_len[i+1] = [0, 0]

for i in range(N-1):
    a, b = tuple(map(int, input().split()))
    tree[a].append(b)
    tree[b].append(a)

while len(tree) > 1:
    del_nodes = []
    for from_node, to_nodes in tree.items():
        # dictのサイズが1なら
        if len(to_nodes) == 1:
            to_node = to_nodes[0]

            # そのノードが持つ隣接ノード長を追加する
            nodes_len[to_node].append(nodes_len[from_node][0]+1)

            # 長さが2以上のみ保持する
            nodes_len[to_node].sort(reverse=True)
            nodes_len[to_node] = nodes_len[to_node][:2]

            # treeのto_nodeの部分から削除する
            tree[to_node].remove(from_node)

            del_nodes.append(from_node)

    for node in del_nodes:
        del tree[node]

n = list(tree.keys())[0]
print("Second" if (nodes_len[n][0] + nodes_len[n][1]+1) % 3 == 2 else "First")


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline


N = int(input())
# 例外処理
if (N == 1):
    print("First")
    quit()

tree = defaultdict(set)
tree_main = defaultdict(set)
for i in range(N-1):
    a, b = tuple(map(int, input().split()))
    tree[a].add(b)
    tree[b].add(a)
    tree_main[a].add(b)
    tree_main[b].add(a)

def longest_path(tree, from_node=1):
    cnt = 1

    nearest_nodes = list(tree[from_node])
    while len(nearest_nodes) > 0:
        for one_step_node in nearest_nodes:
            for two_step_node in tree[one_step_node]:
                if two_step_node != from_node:
                    tree[two_step_node].remove(one_step_node)
                    tree[two_step_node].add(from_node)
                    tree[from_node].add(two_step_node)
            tree[from_node].remove(one_step_node)
        cnt += 1
        nearest_nodes = list(tree[from_node])

    return one_step_node, cnt


far, _ = longest_path(tree)
_, n = longest_path(tree_main, far)
print("Second" if n % 3 == 2 else "First")
### BUGGY CODE ###

n = int(input())
v = list(map(int, input().split()))
odd = [0 for _ in range(n // 2)]
odd_num = [0 for _ in range(n // 2)]
even = [0 for _ in range(n // 2)]
even_num = [0 for _ in range(n // 2)]
for i in range(n):
    if i % 2 == 0:
        if v[i] in odd:
            odd_num[odd.index(v[i])] += 1
        else:
            odd_num[i // 2] = 1 
        odd[i // 2] = v[i]
    else:
        if v[i] in even:
            even_num[even.index(v[i])] += 1
        else:
            even_num[i // 2] = 1 
        even[i // 2] = v[i]

odd_sort = sorted(odd_num, reverse = True)
o = odd[odd_num.index(odd_sort[0])]
even_sort = sorted(even_num, reverse = True)
e = even[even_num.index(even_sort[0])]
if o != e:
    ans = n - odd_sort[0] - even_sort[0]
else:
    if odd_sort[1] < even_sort[1]:
        ans = n - odd_sort[0] - even_sort[1]
    else:
        ans = n - odd_sort[1] - even_sort[0]

print(ans)


### FIXED CODE ###

import collections
n = int(input())
v = list(map(int, input().split()))
o = [v[i] for i in range(n) if i % 2 == 0]
e = [v[i] for i in range(n) if i % 2 == 1]
odd = collections.Counter(o)
even = collections.Counter(e)
odd_num = odd.most_common(2)
even_num = even.most_common(2)
odd_num.append(('', 0))
even_num.append(('', 0))
if odd_num[0][0] == even_num[0][0]:
    print(n - max(odd_num[0][1] + even_num[1][1], odd_num[1][1] + even_num[0][1]))
else:
    print(n - odd_num[0][1] - even_num[0][1])
### BUGGY CODE ###

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

list = []
for x in a_n:
    if list == []:
        list.append([x,1])
    else:
        counter = 0
        for y in list:
            if y[0] == x:
                y[1] += 1
                counter = 1220
        if counter == 0:
            list.append([x,1])

counter = 0
for y in list:
    if y[0] > y[1]:
        counter += y[1]
    elif y[0] < y[1]:
        counter += y[1] - y[0]
print(counter)

### FIXED CODE ###

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

dict = {}
for i in range(N):
    if a_n[i] in dict:
        dict[a_n[i]] += 1
    else:
        dict[a_n[i]] = 1

cnt = 0
for i in dict:
    if dict[i] > i:
        cnt += dict[i] - i
    elif dict[i] < i:
        cnt += dict[i]
print(cnt)
### BUGGY CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
ans = 0

C = list(set(A))
M = len(C)
t = []
t1 = []
t2 = []
for i in range(M):
  #t.append(A.count(C[i]))
  temp = A.count(C[i])
  if temp >=3:
    t1.append(math.factorial(temp-1)/(math.factorial(temp-3)*2))
    t2.append(math.factorial(temp)/(math.factorial(temp-2)*2))    
  elif temp == 2:
    t1.append(0)
    t2.append(math.factorial(temp)/(math.factorial(temp-2)*2))
  else:
    t1.append(0)
    t2.append(0)

#print(t,t1,t2)


s = []  
for i in range(M):
  ans = 0
  for j in range(M):
    if i == j:
      ans += t1[j]
    else:
      ans += t2[j]
  s.append(int(ans))

jisyo = dict(zip(C,s))
#print(jisyo[1])
for i in range(N):
  print(jisyo[A[i]])

### FIXED CODE ###

import math

N = int(input())
A = list(map(int, input().split()))
ans = 0

C = list(set(A))
M = len(C)
t = []
anst = 0
dic = {}
for i in A:
  if not i in dic:
    dic[i] = 0
  dic[i] += 1

jisyo = {}
for i in range(M):
  temp = dic[C[i]]
  jisyo[C[i]] = temp
  #t.append(A.count(C[i]))
  if temp >=2:
    anst += temp*(temp-1)/2

#jisyo = dict(zip(C, t))
#print(jisyo)   
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-jisyo[A[i]]+1))
### BUGGY CODE ###

class SegTree:
    def __init__(self, N):
        self.N = N
        self._N = 1<<((N-1).bit_length())
        self.node = [10**15]*(2*self._N-1)
        self.node[self._N-1] = 0

    def eval(self,p):
        i = p + self._N-1
        cur = self.node[i]
        while i:
            i = (i-1) // 2
            if cur > self.node[i]:
                cur = self.node[i]
        self.node[p+self._N-1] = cur
        return cur

    def update(self,x,p,q,idx=0,a=0,b=None):
        if not idx:
            x += self.eval(p)
        if x >= 10**15:
            return
        if b is None:
            b = self._N
        if q <= p or b <= p or q <= a:
            return
        elif p <= a and b <= q:
            if x < self.node[idx]:
                self.node[idx] = x
            return
        else:
            self.update(x,p,q,idx*2+1,a,(a+b)//2)
            self.update(x,p,q,idx*2+2,(a+b)//2,b)
            return


n,m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]
edge.sort()
tr = SegTree(n)
for s,t,c in edge:
    tr.update(c,s-1,t)
ans = tr.eval(n-1)
if ans >= 10**15:
    ans = -1
print(ans)


### FIXED CODE ###

class SegTree:
    def __init__(self, N):
        self.N = N
        self._N = 1<<((N-1).bit_length())
        self.node = [10**15]*(2*self._N-1)
        self.node[self._N-1] = 0

    def eval(self,p):
        i = p + self._N-1
        cur = self.node[i]
        while i:
            i = (i-1) // 2
            if cur > self.node[i]:
                cur = self.node[i]
        self.node[p+self._N-1] = cur
        return cur

    def update(self,x,p,q,idx=0,a=0,b=None):
        if not idx:
            x += self.eval(p)
        if x >= 10**15:
            return
        if b is None:
            b = self._N
        if q <= p or b <= p or q <= a:
            return
        elif p <= a and b <= q:
            if x < self.node[idx]:
                self.node[idx] = x
            return
        else:
            self.update(x,p,q,idx*2+1,a,(a+b)//2)
            self.update(x,p,q,idx*2+2,(a+b)//2,b)
            return


n,m = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(m)]
edge.sort()
tr = SegTree(n)
for s,t,c in edge:
    tr.update(c,s-1,t)
ans = tr.eval(n-1)
if ans >= 10**15:
    ans = -1
print(ans)
### BUGGY CODE ###

def judge(k, N, A):
    t = 0
    s = N
    for i in A:
        for j in reversed(range(s)):
            if A[j] + i >= k:
                s = j + 1
                t += j + 1
                break
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    t = A[0] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in range(N):
        tmp += A[i]
        B.append(tmp)
    r = 0
    tot = 0
    s = N
    for i in A:
        for j in reversed(range(s)):
            if i + A[j] >= X:
                tot += j + 1
                s = j + 1
                r += i * (j + 1) + B[j]
                break
    return r - (tot - M) * X
print(main())


### FIXED CODE ###

import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())
### BUGGY CODE ###

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

ans = ""
for i in range(1, N + 1):
  ans += str(A.index(i) + 1) + " "
print(ans)

### FIXED CODE ###

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

ans = [0] * N
for i, j in enumerate(A, 1):
  ans[j - 1] = i
print(" ".join(map(str, ans)))
### BUGGY CODE ###

n, m = map(int,input().split())
l = list(map(int,input().split()))

dp = [0 for i in range(n)]

for i in range(1,n):
    if i <= m-1:
        dp[i] = abs(l[0]-l[i])
    
    else:
        mini = 10**9
        for j in range(1,m+1):
            mini = min(mini, abs(l[i]-l[i-j])+dp[i-j])
        
        dp[i] = mini

print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf')]*n
dp[0] = 0
for i in range(1,k+1):
    dp[i] = abs(l[0]-l[i])
    
    if i == n-1:
        break

for i in range(k+1,n):
    dp_min = float('inf')
    for j in range(1,k+1):
        tmp = dp[i-j] + abs(l[i] - l[i-j])
        dp_min = min(dp_min, tmp)
    
    dp[i] = dp_min
    
print(dp[n-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import fractions


#def tri_gcd(p, q, r):
#    tmp_gcd = fractions.gcd(p, q)
#    return fractions.gcd(tmp_gcd, r)


k = int(input())
res = 0
for a in range(1, k+1):
    for b in range(a, k+1):
        tmp_gcd = fractions.gcd(a, b)
        for c in range(b, k+1):
            tk = fractions.gcd(tmp_gcd, c)
            if a == b:
                if b == c:
                    res += tk
                else:
                    res += tk * 3
            else:
                if b == c:
                    res += tk*3
                else:
                    res += tk*6

print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import fractions
gcd_map = [[0 for i in range(401)] for i in range(401)]


def mem_gcd(p, q):
    if gcd_map[p][q] == 0:
        gcd_map[p][q] = fractions.gcd(p, q)
    return gcd_map[p][q]


k = int(input())
res = 0
for a in range(1, k+1):
    for b in range(a, k+1):
        tmp_gcd = mem_gcd(a, b)
        for c in range(b, k+1):
            tk = mem_gcd(tmp_gcd, c)
            if a == b:
                if b == c:
                    res += tk
                else:
                    res += tk * 3
            else:
                if b == c:
                    res += tk*3
                else:
                    res += tk*6

print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
count=0

for i in range(1,n+1):
  if len(a)>=1 and i==a[0]:
    for j in a:
      if i==j:
        count+=1
      else:
        break
    del a[:count]
        
  print(count)
  count=0

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ls=[0]*n

for i in a:
  ls[i-1]+=1
for i in ls:
  print(i)
### BUGGY CODE ###

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

# ni - nj = ai + aj (i>j)
# ai - ni = - aj - nj

a1 = [a[i] - (i+1) for i in range(n)]
a2 = [- a[i] - (i+1) for i in range(n)]
ans = 0
for i in range(n):
    ans += a2.count(a1[i])
print(ans)

### FIXED CODE ###

import bisect

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

# ni - nj = ai + aj (i>j)
# ai - ni = - aj - nj

a1 = sorted([a[i] - (i+1) for i in range(n)])
a2 = sorted([- a[i] - (i+1) for i in range(n)])
ans = 0
for i in range(n):
    left = bisect.bisect_left(a2, a1[i])
    right = bisect.bisect_right(a2, a1[i])
    ans += (right - left)
print(ans)
### BUGGY CODE ###

s_list = list(input().split()[0])
count_list = [0] * len(s_list)

# 最初がRだった子は、Rが連続する限り右へ行く。最初にLが出た瞬間が打ち止め
# 最初がLだった子は、Lが連続する限り左へ行く。最初にRが出た瞬間が打ち止め
for child_i, start_s in enumerate(s_list):
    # print(count_list)
    # print('{}人目'.format(child_i))
    # 明らかにこれは計算時間がかかりすぎる
    count = 0
    stop_s = 'L' if start_s == 'R' else 'R'
    if start_s == 'R':
        # 時間が足りないので、一番近いRLを探した方がよい
        copy_list = s_list[child_i:]
        target_str = ''.join([str(x) for x in copy_list])
        step = target_str.find('RL') + 1
        now_index = child_i + step
        if step % 2 == 0:
            count_list[now_index] += 1
        else:
            count_list[now_index-1] += 1

    if start_s == 'L':
        copy_list = reversed(s_list[:child_i+1])
        # 時間が足りないので、一番近いRLを探した方がよい
        target_str = ''.join([str(x) for x in copy_list])
        step = target_str.find('LR') + 1
        now_index = child_i - step
        if step % 2 == 0:
            count_list[now_index] += 1
        else:
            count_list[now_index+1] += 1
    # print('now_index = {}'.format(now_index))

ans = ' '.join([str(x) for x in count_list])
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc136/tasks/abc136_d
# D - Gathering Children
import math
# 一番近いRLはどこか？

s_list = list(input().split()[0])
count_list = [0] * len(s_list)

# 最初がRだった子は、Rが連続する限り右へ行く。最初にLが出た瞬間が打ち止め
# 最初がLだった子は、Lが連続する限り左へ行く。最初にRが出た瞬間が打ち止め
rrl_list = ''.join(s_list).split('LR')
count_index = 0

for i, rrl in enumerate(rrl_list):
    if i != 0:
        rrl = 'R' + rrl
    if i != len(rrl_list) - 1:
        rrl = rrl + 'L'
    rl_r_index = rrl.find('RL')
    # rl_r_indexから偶数歩離れているマス目の数は
    # 左側
    r_count = math.floor(rl_r_index / 2)
    # print('左側：{}'.format(r_count))
    # 右側
    # print('右側: {}'.format(math.floor((len(rrl) - (rl_r_index+1)) / 2) + 1))
    r_count += math.floor((len(rrl) - (rl_r_index+1)) / 2) + 1

    l_count = len(rrl) - r_count
    count_list[count_index + rl_r_index] = r_count
    count_list[count_index + rl_r_index + 1] = l_count
    count_index += len(rrl)
    # print(rrl)
    # print(count_list)

ans = ' '.join([str(x) for x in count_list])
print(ans)
### BUGGY CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

n = int(input())
s = input()

ans = 0
for t in range(1000):
    q = str(int(t/100))
    if not q in s:
        continue
    z = s.index(q) + 1
    p = deque([int((t%100 - t%10)/10), t%10, -1])
    q = p.popleft()
    for x in s[z:]:
        if q == -1:
            ans += 1
            break
        if q == int(x):
            q = p.popleft()
    else:
        if q == -1:
            ans += 1
print(ans)


### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
# map(int, input().split())
# int(input())
# input().split()
# mojiretu = ','.join(str_list)
# sorted(input())

n = int(input())
s = input()
cnt = 0
q = s[0]
t = s[0]
for x in s[1:]:
    if x == q:
        cnt += 1
        if cnt < 3:
            t += x
    else:
        cnt = 0
        t += x
        q = x
ans = 0
for i in range(10):
    x = t.find(str(i)) + 1
    if not x: continue
    for j in range(10):
        y = t[x:].find(str(j)) + 1
        if not y: continue
        for k in range(10):
            z = t[x + y:].find(str(k)) + 1
            if not z: continue
            #print(i,j,k, ':', x,y,z)
            ans += 1
print(ans)
### BUGGY CODE ###

n,q=map(int,raw_input().split())
ans=[0]*n
for i in range(q):
    a,v=map(int,raw_input().split())
    ans[a-1]+=v
    t=ans.index(max(ans))
    print t+1,ans[t]
exit()

### FIXED CODE ###

n,q=map(int,raw_input().split())
ans=[0]*n
key=value=0
for i in range(q):
    a,v=map(int,raw_input().split())
    a-=1
    ans[a]+=v
    if a==key and v<0:
        value=max(ans)
        key=ans.index(value)
    elif ans[a]>value:
        key=a
        value=ans[a]
    elif ans[a]==value and a<key:
        key=a
    print key+1,value
### BUGGY CODE ###

def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

def lcm(m, n):
    return m//gcd(m, n)*n
MOD = 10**9+7
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1,n):
    l = lcm(a[i], l)
ans = 0
for x in a:
    ans = (ans + l//x)%MOD
print(ans)

### FIXED CODE ###

def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

def lcm(m, n):
    return m//gcd(m, n)*n
MOD = 10**9+7
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for x in a:
    l = lcm(x, l)
ans = 0
for x in a:
    ans += l*pow(x, MOD-2, MOD)%MOD
print(ans%MOD)
### BUGGY CODE ###

n=int(input())
a=[int(x) for x in input().split()]

def func1(a):
    a.sort()
    cnt=0
    chker=[]
    for i in a:
        candiv=False
        if a.count(i)>1:
            candiv=True
        else:
            for j in chker:
                if j*2>i:
                    break
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
        chker.append(i)
    print(cnt)
func1(a)


### FIXED CODE ###

n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        dp[a[i]]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

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

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
	ans = ans * a[i]

if ans > 10**18:
	print(-1)
else:
	print(ans)


### FIXED CODE ###

import sys
n = int(input())
a = list(map(int,input().split()))
ans = 1

if 0 in a:
	print(0)
	sys.exit()

for i in range(n):
	ans = ans * a[i]
	if ans > 1000000000000000000:
		print(-1)
		sys.exit()

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

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
for i in range(n):
  ans+=l//a[i]
  ans%=mod
print(ans)

### FIXED CODE ###

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
l%=mod
for i in range(n):
  ans+=l*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

import numpy as np
R, C, K = map(int, input().split())
dp = np.array([[[0 for i in range(4)] for j in range(C+1)]
               for k in range(R+1)])
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = np.array([[0 for i in range(C+1)] for j in range(R+1)])

for i in range(K):
    r, c, v = map(int, input().split())
    D[r][c] = v

for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[i-1][j])
            dp[i][j][0] = max(dp[i][j-1][0], M)
            dp[i][j][1] = max(dp[i][j-1][0]+v, dp[i][j-1][1], M+v)
            dp[i][j][2] = max(dp[i][j-1][1]+v, dp[i][j-1][2])
            dp[i][j][3] = max(dp[i][j-1][2]+v, dp[i][j-1][3])

        else:
            M = max(dp[i-1][j])
            dp[i][j][0] = max(dp[i][j-1][0], M)
            dp[i][j][1] = dp[i][j-1][1]
            dp[i][j][2] = dp[i][j-1][2]
            dp[i][j][3] = dp[i][j-1][3]

ans = 0
for i in range(4):
    ans = max(ans, dp[-1][-1][i])
print(ans)

### FIXED CODE ###

R, C,K = map(int, input().split())
dp = [[[0]*(C+1) for k in range(R+1)] for _ in range(4)]
# dp[r][c][j] :=r index c columns already j cnt
dp[0][0][0] = 0
D = [[0 for i in range(C+1)] for j in range(R+1)]
import random
for i in range(K):
    r, c, v = map(int,input().split())
    D[r][c] = v

for i in range(R+1):
    for j in range(C+1):
        if D[i][j] > 0:
            v = D[i][j]
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = max(dp[0][i][j-1]+v, dp[1][i][j-1], M+v)
            dp[2][i][j] = max(dp[1][i][j-1]+v, dp[2][i][j-1])
            dp[3][i][j] = max(dp[2][i][j-1]+v, dp[3][i][j-1])

        else:
            M = max(dp[k][i-1][j] for k in range(4))
            dp[0][i][j] = max(dp[0][i][j-1], M)
            dp[1][i][j] = dp[1][i][j-1]
            dp[2][i][j] = dp[2][i][j-1]
            dp[3][i][j] = dp[3][i][j-1]

ans = 0
for i in range(4):
    ans = max(ans, dp[i][-1][-1])
print(ans)
### BUGGY CODE ###


import sys
input = sys.stdin.readline

N=int(input())
A = [list(map(lambda x:int(x)-1,input().split()))[::-1] for _ in [0]*N]

ans = 0
match = [True]
while 1:
    match = []
    done = [False]*N
    for i in range(N):
        if done[i] : continue
        if not A[i] : continue
        j = A[i][-1]
        if A[j][-1] == i:
            done[i] = True
            done[j] = True
            match.append((i,j))
    for i in range(N):
        if done[i] : A[i].pop()
    if not match: break
    ans += 1
if sum(len(B) for B in A)>0: ans = -1
print(ans)

### FIXED CODE ###

#"""
import sys
input = sys.stdin.readline
#"""
def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()