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

n,k = map(int,input().split())
l = list(map(int,input().split()))
l_ans = [0,abs(l[1]-l[0])]
for i in range(2,n):
    tmp1=float("inf")
    for j in range(1,min(i+1,k+1)):
        tmp2=l_ans[i-j]+abs(l[i]-l[i-j])
        if tmp1>tmp2:tmp1=tmp2
    l_ans.append(tmp1)
print(l_ans[::-1][0])

### FIXED CODE ###

n,k = map(int,input().split())
l = list(map(int,input().split()))
l_ans = [0,abs(l[1]-l[0])]+[0]*(n-2)
for i in range(2,n):
    tmp1=float("inf")
    for j in range(1,min(i+1,k+1)):
        tmp2=l_ans[i-j]+abs(l[i]-l[i-j])
        if tmp1>tmp2:tmp1=tmp2
    l_ans[i]=tmp1
print(l_ans[::-1][0])
### BUGGY CODE ###

N = int(input())

line = list(map(int,input().split()))

count = 0
S = 0
while count <= N:
    for i in range(S,N):
        try:
            if line[i] == i + 1:
                S = i
            else:
                line.pop(i)
                break
        except:
            break
    count += 1


if len(line) == 0:
    print(-1)
else:
    print(N - len(line))

### FIXED CODE ###

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

checkNum = 1
howMany = 0

for j in range(N):
    if line[j] == checkNum:
        checkNum += 1
    else:
        howMany += 1

# print(line)
# print(checkNum)
# print(howMany)

if checkNum == 1:
    print("-1")
else:
    print(howMany)
### BUGGY CODE ###

# author:  Taichicchi
# created: 21.09.2020 20:00:43

import sys

S = input()

Q = int(input())

rev = 0

for q in range(Q):
    query = input().split()
    if query[0] == "1":
        rev = 1 - rev
    else:
        if ((rev == 0) & (query[1] == "1")) | ((rev == 1) & (query[1] == "2")):
            S = query[2] + S
        else:
            S = S + query[2]

if rev:
    print(S[::-1])
else:
    print(S)


### FIXED CODE ###

# author:  Taichicchi
# created: 21.09.2020 20:00:43

import sys

S = input()

Q = int(input())

rev = 0

front = []
end = []

for q in range(Q):
    query = input().split()
    if query[0] == "1":
        rev = 1 - rev
    else:
        if ((rev == 0) & (query[1] == "1")) | ((rev == 1) & (query[1] == "2")):
            front.append(query[2])
        else:
            end.append(query[2])

front = "".join(front)
end = "".join(end)


if rev:
    print(end[::-1] + S[::-1] + front)
else:
    print(front[::-1] + S + end)
### BUGGY CODE ###

N,W= map(int,input().split())  
wv = [tuple(map(int, input().split())) for i in range(0, N) ]   

def rec(n, uplimit_w):  
  ans = 0  
  if n == N:  
    return 0  

  # n番目の品物を使えない場合   
  elif wv[n][0] > uplimit_w:  
    return rec(n + 1, uplimit_w)  

  # n番目の品物が使える時  
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?  
  else:  
    ans = max(  
      rec(n + 1, uplimit_w),  
      rec(n + 1, uplimit_w - wv[n][0]) + wv[n][1]  
    )  
    return ans  

def solve():  
  print(rec(0, W))  

def main():  
  solve()  

if __name__ == "__main__":  
  main()

### FIXED CODE ###

def knap(N,W,weight,value):
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    #各nについて初期化　以下で各ｗについて0この時０とする
    for i in range(W+1):#w+1とは0~w
        dp[0][i]=0
    for i in range(N):#each n 0~N-1
        for w in range(W+1):#w 0~w
            if weight[i]<=w:#=を入れないとぎりぎりの時が困る
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i],dp[i][w])
            else:
                dp[i+1][w]=dp[i][w]
   # print(dp)
    return dp[N][W]


n,W=map(int,input().split())
w=[]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
print(knap(n,W,w,v))
### BUGGY CODE ###

from collections import defaultdict
n, m = list(map(int, input().split()))
d1 = defaultdict(list)
for i in range(m):
  u, v = list(map(int, input().split()))
  d1[u].append(v)
s, t = list(map(int, input().split()))
d2 = defaultdict(set)

def dfs (x, nx, cnt):
  if cnt==3:
    d2[x].add(nx)
  elif cnt>3:
    return

  for nnx in d1[nx]:
    dfs(x, nnx, cnt+1)

for i in range(1, n+1):
  dfs(i, i, 0)

from heapq import heappop, heappush
prev = [-1 for _ in range(n+1)]
def dijkstra(s, graph):
  d = [float("INF") for _ in range(n+1)]
  d[s] = 0
  q = []
  heappush(q, [0, s])

  while q:
    dt, v = heappop(q)
    if d[v] < dt:
      continue
    for to in graph[v]:
      if d[to] > dt+1:
        d[to] = dt+1
        prev[to] = v
        heappush(q, [d[to], to])
  return d
dd = dijkstra(s, d2)
if dd[t]==float("INF"):
  print(-1)
else:
  print(dd[t])

### FIXED CODE ###

from collections import defaultdict, deque
n, m = list(map(int, input().split()))
graph = defaultdict(list)
for i in range(m):
  u, v = list(map(int, input().split()))
  graph[u].append(v+n)
  graph[u+n].append(v+2*n)
  graph[u+2*n].append(v)
s, t = list(map(int, input().split()))
dist = [-1 for i in range(3*n+10)]

def bfs():
  que = deque([s])
  dist[s] = 0
  while len(que) > 0:
    cur = que.popleft()
    for to in graph[cur]:
      if dist[to] == -1:
        dist[to] = dist[cur]+1
        que.append(to)

bfs()
print(dist[t]//3)
### BUGGY CODE ###

n = int(input())
L = list(map(int,input().split()))
L = sorted(L,reverse=True)
total = 0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if L[j] + L[k] > L[i]:
                total += 1
print(total)


### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int,input().split()))
L = sorted(L)
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        limit = L[i]+L[j]
        ans += bisect.bisect_left(L,limit) - (j+1)

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

N , K = map(int,input().split())
D = list(map(int,input().split()))

maxValue = 0
actList = [0]*K

for i in range(5**K):
    act = i
    valList = []
    V = D.copy()

    for j in range(K):
        actList[j] = (act % 5)
        act = int(act / 5)

    for j in actList:
        if(j == 0): # 操作 A
            if(len(V) == 0):
                continue
            valList.append(V.pop(0))
        elif(j == 1): # B
            if(len(V) == 0):
                continue
            valList.append(V.pop())
        elif(j == 2): # C
            if(len(valList) == 0):
                continue
            V.insert(0,valList.pop(0))
        elif(j == 3): # D
            if(len(valList) == 0):
                continue
            V.append(valList.pop(0))
        valList.sort()

    val = sum(valList)
    if maxValue < val:
        maxValue = val

print(maxValue)



### FIXED CODE ###

N , K = map(int,input().split())
D = list(map(int,input().split()))

maxValue = 0

for i in range(min(N,K)+1):
    for j in range(min(N,K)-i+1):
        left = D[:i]
        right = D[N-j:]
        merge = (left + right + [0])
        merge.sort()

        index = 0

        for k in range(K-i-j):
            if (merge[index] < 0):
                index += 1
            else:
                break

        val = sum(merge[index:])
        if(maxValue < val):
            maxValue = val

print(maxValue)
### BUGGY CODE ###

import sys 
input = sys.stdin.readline
MOD = 10**9 +7
INF = 10**9

def main():
    n = int(input())
    a = list(map(int,input().split()))
    
    dp = [[0] * (n + 2)  for _ in range(n + 2)]
    
    for l in range(1,n + 1):
        for i in range(n - l + 1):
            j = i + l
            if (n - l)%2 == 0:
                dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
    
    print(dp[0][n])

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys 
input = sys.stdin.readline
MOD = 10**9 +7
INF = 10**9

def main():
    n = int(input())
    a = list(map(int,input().split()))
    
    dp = [[0] * (n + 2)  for _ in range(n + 2)]
    
    for l in range(1,n + 1):
        for i in range(n - l + 1):
            j = i + l
            if (n - l)%2 == 0:
                dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
    
    print(dp[0][n])

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

# B - Greedy Takahashi
a,b,k = map(int,input().split())
for i in range(k):
    if a >= 1:
        a -= 1
    else:
        b -= 1
print(a,b)

### FIXED CODE ###

# B - Greedy Takahashi
a,b,k = map(int,input().split())
if a < k:
    k -= a
    a = 0  
    if b < k:
        b = 0
        print(a,b)
    else:
        print(a,b-k)
else:
    print(a-k,b)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
n, q = map(int, input().split())
#隣接リスト
G = defaultdict(lambda:[])
#################################
for _ in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
    
#################################

#深さ優先探索でトポロジカル順序を決める
#右奥から調べていく
parent = [0]*n #p[i]:頂点iの親
order = [] #トポロジカル順序
def dfs():
    parent[0] = -1
    stack = []
    u = 0
    stack.append(u)
    while stack:
        x = stack.pop()
        order.append(x)
        for v in G[x]:
            if v == parent[x]:
                continue
            parent[v] = x
            stack.append(v)

dfs()
################################
point = [0]*n
def f(p, x):
    p -=1
    ind = order.index(p)
    order1 = order[ind:]
    order2 = order[:ind]
    order2.append(-1)
    for i in order1:
        if i == p:
            point[i] += x
        else:
            if parent[i] not in order2:
                point[i] += x
            else:
                break
    
for i in range(q):
    p, x = map(int, input().split())
    f(p, x)

print(*point)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
from collections import deque, defaultdict
n, q = map(int, input().split())
#隣接リスト
G = defaultdict(lambda:[])
#################################
for _ in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    G[a].append(b)
    G[b].append(a)
    
#################################

#深さ優先探索でトポロジカル順序を決める
#右奥から調べていく
parent = [0]*n #p[i]:頂点iの親
order = [] #トポロジカル順序
def dfs():
    parent[0] = -1
    stack = []
    u = 0
    stack.append(u)
    while stack:
        x = stack.pop()
        order.append(x)
        for v in G[x]:
            if v == parent[x]:
                continue
            parent[v] = x
            stack.append(v)

dfs()
################################
point = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    p -=1
    point[p] += x

for i in order:
    if parent[i] != -1:
        point[i] += point[parent[i]]

print(*point)
### BUGGY CODE ###

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

cnt = 0
for a in A:
    for b in B:
        if b <= a:
            pass
        else:
            for c in C:
                if c <= b:
                    pass
                else:
                    cnt += 1

print(cnt)

### FIXED CODE ###

import numpy as np

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

An = np.array(A)
Bn = np.array(B)
Cn = np.array(C)

An.sort()
Bn.sort()
Cn = -Cn
Cn.sort()

AB = np.searchsorted(An,Bn,side='left')
CB = np.searchsorted(Cn,-Bn,side='left')

print((AB*CB).sum())
### BUGGY CODE ###

from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(input())


def sinput():
    return input().split()


def intsput():
    return map(int, sinput())


n, k = intsput()

a = list(intsput())
f = list(intsput())

a.sort()
f.sort(reverse=True)
p = [a[i] * f[i] for i in range(n)]
scrap = [0] * n

start = 0
end = max(p)
target = (start + end) // 2
while start != end:
    cnt = 0
    for i in range(n):
        fix = 0
        if p[i] > target:
            fix = (p[i] - target + f[i] - 1) // f[i]
            cnt += fix
        #scrap[i] = a[i] - fix
        if cnt > k:
            start = target + 1
            target = (start + end) // 2
            break
    else:
        end = target
        target = (start + end) // 2

print(start)


### FIXED CODE ###

from sys import stdin


def input():
    return stdin.readline()[:-1]


def intput():
    return int(input())


def sinput():
    return input().split()


def intsput():
    return map(int, sinput())


n, k = intsput()

a = list(intsput())
f = list(intsput())

a.sort()
f.sort(reverse=True)
p = [a[i] * f[i] for i in range(n)]
scrap = [0] * n

start = 0
end = max(p)
target = (start + end) // 2
while start != end:
    cnt = 0
    for i in range(n):
        fix = 0
        if p[i] > target:
            fix = (p[i] - target + f[i] - 1) // f[i]
            cnt += fix
        #scrap[i] = a[i] - fix
        if cnt > k:
            start = target + 1
            target = (start + end) // 2
            break
    else:
        end = target
        target = (start + end) // 2

print(start)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
i = 0
ans = 0
while i < n:
    if a[i] >= k:
        ans += 1
        i += 1
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
i = 0
ans = 0
for i in range(n):
    if h[i] >= k:
        ans+=1
print(ans)
### BUGGY CODE ###

s=list(input())
q=int(input())
for i in range(q):
    t=list(input().split())
    if t[0]=="1":
        s.reverse()
    else:
        if t[1]=="1":
            s.insert(0,t[2])
        else:
            s.append(t[2])
print("".join(s))

### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
rev=0
for i in range(q):
    t=list(input().split())
    if t[0]=="1":
        rev=rev+1
    else:
        if t[1]=="1":
            if rev%2==0:
                s.appendleft(t[2])
            else:
                s.append(t[2])
        else:
            if rev%2==0:
                s.append(t[2])
            else:
                s.appendleft(t[2])
if rev%2==0:
    print("".join(s))
else:
    s.reverse()
    print("".join(s))
### BUGGY CODE ###

def main():
    N, K = map(int, raw_input().split())
    Points = []
    for i in range(N):
        x, y = map(int, raw_input().split())
        Points.append([x, y])

    ans = float('inf')
    for u in range(N):
        for r in range(N):
            for d in range(N):
                for l in range(N):
                    x1, x2 = min(Points[l][0], Points[r][0]), max(Points[l][0], Points[r][0])
                    y1, y2 = min(Points[d][1], Points[u][1]), max(Points[d][1], Points[u][1])
                    tmp = 0
                    for x, y in Points:
                        if (x1 <= x <= x2) and (y1 <= y <= y2):
                            tmp += 1
                    if tmp >= K:
                        ans = min(ans,  (x2 - x1) * (y2 - y1))

    print(ans)


main()


### FIXED CODE ###

N, K = map(int, input().split())
XY = []
YX = []
for i in range(N):
    x, y = map(int, input().split())
    XY.append([x, y, i])
    YX.append([y, x, i])
XY.sort()
YX.sort()

x_order = {}
for xo, p in enumerate(XY):
    x, y, i = p
    x_order[i] = xo

cums = [[0 for j in range(N+1)] for i in range(N+1)]
for i in range(N):
    y, x, pi = YX[i]
    xo = x_order[pi]
    for j in range(N + 1):
        cums[i + 1][j] = cums[i][j] + (1 if j > xo else 0)

ans = float('inf')

for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N-1):
            for l in range(k+1, N):
                if cums[l+1][j+1] - cums[l+1][i] - cums[k][j+1] + cums[k][i] >= K:
                        ans = min(ans, (XY[j][0]-XY[i][0]) * (YX[l][0]-YX[k][0]))

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

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

[a.extend([bc[i][1]]*bc[i][0]) for i in range(m)]

print(sum(sorted(a,reverse=True)[:n]))


### FIXED CODE ###

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

sorted_ab=sorted(bc, reverse=True, key=lambda x: x[1])
new_ab=[]
ans=[]

for i in range(m):
    if len(new_ab)<=n:
        tmp_l=[sorted_ab[i][1]]*sorted_ab[i][0]
        new_ab+=tmp_l
    else:
        break

final_list=a+new_ab
final_list.sort(reverse=True)

print(sum(final_list[:n]))
### BUGGY CODE ###

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

hyouten = [0] * (N)

# 評点計算
for i in range(K-1, N):
    tmp = A[i]
    for j in range(1,K):
        tmp *= A[i-j]
    hyouten[i] = tmp

for i in range(K, N):
    if hyouten[i] > hyouten[i-1]:
        print('Yes')
    else:
        print("No")
        

### FIXED CODE ###

import sys
N, K = map(int, input().split())

def input():
    return sys.stdin.readline()[:-1]
A = list(map(int, input().split()))


for i in range(K, N):
    if A[i-K] < A[i]:
        print('Yes')
    else:
        print("No")
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

N = int(readline())

digit_total = 0

while N >= 1:
    pop = N % 10
    N //= 10
    digit_total += pop

ans = 'Yes' if digit_total % 9 == 0 else 'No'

print(ans)


### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

N = int(readline())
ans = 'Yes' if N%9 == 0 else 'No'

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

from itertools import permutations
n, m, r = [int(item) for item in input().split()]
rs = [int(item) for item in input().split()]
abc = [[int(item) for item in input().split()] for _ in range(m)]

INF = 10**6
path = [[INF] * n for _ in range(n)]
short_path = [[INF] * n for _ in range(n)]
for i in range(n):
    path[i][i] = 0
for a, b, c in abc:
    path[a-1][b-1] = path[b-1][a-1] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            short_path[i][j] = min(short_path[i][j], path[i][k] + path[k][j])

ans = INF
for pattern in permutations(rs):
    distance = 0
    for i in range(1,r):
        distance += short_path[pattern[i-1]-1][pattern[i]-1]
    ans = min(ans, distance)
print(ans)

### FIXED CODE ###

import heapq
from itertools import permutations
n, m, r = [int(item) for item in input().split()]
rs = [int(item) for item in input().split()]
abc = [[int(item) for item in input().split()] for _ in range(m)]
INF = 10**9

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def reset(self):
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start, goal=None):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest in range(self.num):
                cost = self.adj[src][dest]
                if cost != INF and self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        if goal is not None:
            return self.get_path(goal)
        else:
            return self.dist

    def get_path(self, goal):
        path = [goal]
        dest = goal

        while self.prev[dest] != INF:
            path.append(self.prev[dest])
            dest = self.prev[dest]
        return list(reversed(path))

path = [[INF] * n for _ in range(n)]
short_path = [[INF] * n for _ in range(n)]
for i in range(n):
    path[i][i] = 0
for a, b, c in abc:
    path[a-1][b-1] = path[b-1][a-1] = c

dij = Dijkstra(path)
for item in rs:
    for i in range(n):
        short_path[item-1][i] = dij.calc(item-1)[i]
    dij.reset()

ans = INF
for pattern in permutations(rs):
    distance = 0
    for i in range(1,r):
        distance += short_path[pattern[i-1]-1][pattern[i]-1]
    ans = min(ans, distance)
print(ans)
### BUGGY CODE ###

from functools import reduce
input()
src = list(map(lambda x: 1 if x=="#" else 0, input()))
s = sum(src)
l = len(src)
ans = s
for i in range(len(src)):
  ans = min(ans, 2*sum(src[:i]) + l - i - s)
  if ans==0:
    break
print(ans)

### FIXED CODE ###

from functools import reduce
l = int(input())
src = list(map(lambda x: 1 if x=="." else 0, input()))
left_black = 0
right_white = sum(src)
ans = right_white
for i in range(l):
  if src[i]==0:
    left_black+=1
  else:
    right_white-=1
  ans = min(ans, left_black + right_white)
  if ans==0:
    break
print(ans)
### BUGGY CODE ###

def Greedy(X):
    L=[0]
    while L:
        L=[]
        for i in range(len(X)):
            if X[i:i+2]=="ST":
                L.append(i)

        for i in L[::-1]:
            X=X[:i]+X[i+2:]

    return len(X)

X=input()
print(Greedy(X))

### FIXED CODE ###

def Solver(X):
    K=0
    P=0

    for s in X:
        if s=="S":
            P+=1
        elif P>0:
            P-=1
        else:
            K+=1

    return 2*K
#================================================
X=input()
print(Solver(X))
### BUGGY CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
cleared_num=0
new_search_index=set(range(1,N+1))
for answer in range(1,N**3):
  matched_flag=[False]*(N+1)
  unchanged=True

  search_index=new_search_index;
  new_search_index=set()
  for i in search_index:
    if matched_flag[i]:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      if len(amat[i])==0:
        cleared_num+=1
      else:
        new_search_index.add(i)  
      if len(amat[ai_next])==0:
        cleared_num+=1
      else:
        new_search_index.add(ai_next)
      unchanged=False
      
  if unchanged:
    print(-1)
    sys.exit()
  elif cleared_num==N:
    print(answer)
    sys.exit()

### FIXED CODE ###

import sys

N=int(input())
amat=[[-1]]
for i in range(N):
  alist=list(map(int,input().split()))
  amat.append(list(reversed(alist)))
  
#print(amat)
answer=0
matched_flag=[False]*(N+1)
for answer in range(1,N**3):
  if N>900 and answer>3000:
    print(N*(N-1)//2)
    sys.exit()
  
  matched_flag=[False]*(N+1)
  unchanged=True
  
  for i in range(1,N+1):
    if matched_flag[i] or len(amat[i]) == 0:
      continue
      
    ai_next = amat[i][-1]
    if amat[ai_next][-1]==i and not matched_flag[ai_next]:
      #print(i,ai_next,answer)
      matched_flag[amat[i].pop()]=True
      matched_flag[amat[ai_next].pop()]=True
      unchanged=False
  
  if unchanged:
    print(-1)
    sys.exit()
  else:
    for i in range(1,N+1):
      if len(amat[i])>0:
        break
    else:
      print(answer)
      sys.exit()