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

N = int(input())
A = list(map(int, input().split()))
gcd_list=[]
reverse_gcd_list = []


def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)

gcd_list.append(A[0])
reverse_gcd_list.append(A[-1])

for i in range(1,N):
    gcd_list.append(gcd(gcd_list[i-1], A[i]))
    reverse_gcd_list.insert(0,gcd(reverse_gcd_list[0], A[-1-i]))

num = [gcd_list[-2], reverse_gcd_list[1]]
for i in range(N-2):
    num.append(gcd(gcd_list[i], reverse_gcd_list[i+2]))

print(max(num))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
gcd_list=[]
reverse_gcd_list = []


def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)

gcd_list.append(A[0])
reverse_gcd_list.append(A[-1])

for i in range(1,N):
    gcd_list.append(gcd(gcd_list[i-1], A[i]))
    # reverse_gcd_list.insert(0,gcd(reverse_gcd_list[0], A[-1-i]))
    reverse_gcd_list.append(gcd(reverse_gcd_list[-1], A[-1-i]))

reverse_gcd_list.reverse()
num = [gcd_list[-2], reverse_gcd_list[1]]
for i in range(N-2):
    num.append(gcd(gcd_list[i], reverse_gcd_list[i+2]))

print(max(num))
### BUGGY CODE ###

s=input()
k=int(input())
ans=["zzzzzz"]*k
for i in range(len(s)):
  for j in range(i,len(s)):
    A=s[i:j+1]
    if A>ans[k-1]:
      continue
    if A in ans:
      continue
    for ii in range(k):
      if A<ans[ii]:
        break
    for jj in range(k-1,ii,-1):
      ans[jj]=ans[jj-1]
    ans[ii]=A
print(ans[-1])

### FIXED CODE ###

s=input()
k=int(input())
ans=["zzzzzz"]*k
for i in range(len(s)):
  for j in range(i,min(i+8,len(s))):
    A=s[i:j+1]
    if A>ans[k-1]:
      continue
    if A in ans:
      continue
    for ii in range(k):
      if A<ans[ii]:
        break
    for jj in range(k-1,ii,-1):
      ans[jj]=ans[jj-1]
    ans[ii]=A
print(ans[-1])
### BUGGY CODE ###

n,m,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
readable = 0
for rx in range(1,n+m+1):
  if readable == rx: break
  for ra in range(0,rx+1):
    rb = rx - ra
    rt = 0
    if ra <= len(a) and rb <= len(b):
      if ra>0 :
        for i in range(0,ra):
          rt += a[i]
      if rb>0 :
        for i in range(0,rb):
          rt += b[i]
      if rt <= k:
        readable = rx
        break
print(readable)


### FIXED CODE ###

n,m,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sa = [0] * (n+1)
sb = [0] * (m+1)
for i in range(n):
  sa[i+1] = sa[i] + a[i]
for i in range(m):
  sb[i+1] = sb[i] + b[i]
rx = 0
rb = m
for ra in range(0,n+1): 
  while (sb[rb] + sa[ra]) > k and rb>0 :
    rb-=1
  if (sb[rb] + sa[ra]) <= k:
    rx = max(rx,ra+rb)
print(rx)
### BUGGY CODE ###

n = int(input())

power = 1
for i in range(1, n+1):
  power *= i

print(power%(10**9+7))

### FIXED CODE ###

n = int(input())

power = 1
for i in range(1, n+1):
  power *= i
  power=power%(10**9+7)

print(power%(10**9+7))
### BUGGY CODE ###

s = str(input())

s = [_ for _ in s]
for i in range(0, len(s)-1):
    if i+2 <= len(s)-1:
        if s[i] == s[i+1]:
            s[i+1] = s[i+1] + s.pop(i+2)
            i = 0
    
if s[-1] == s[-2]:
    print(len(s) - 1)
else:
    print(len(s))

### FIXED CODE ###

s = str(input())

j = 0
count = len(s)

s = [_ for _ in s]
for i in range(0, len(s)-1):
    if j+1 <= len(s)-1:
        if s[j] == s[j+1]:
            j = j + 3
            count -= 1
        else:
            j = j + 1
            continue

print(count)
### BUGGY CODE ###

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

r=0

if(N<K):
  if(abs(N-K)<N):
    r=abs(N-K)
  else:
    r=N

elif(K==1):
   r=0

elif(K<N):
  while(0<N):
    r=abs(N-K)
    N=N-K

print(r)

### FIXED CODE ###

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

r=0

if(N<K):
  if(abs(N-K)<N):
    r=abs(N-K)
  else:
    r=N

elif(K==1):
   r=0

elif(K<N):
  a=N//K
  N=N-K*a
  while(0<N):
    r=abs(N-K)
    N=N-K

print(r)
### BUGGY CODE ###

N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] for i in goods])
dp = [float("inf") for i in range(v_sum + 1)]
dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        dp[j] = min(dp[j - goods[i][1]] + goods[i][0], dp[j])

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        break


### FIXED CODE ###

N, W = map(int, input().split())
goods = [list(map(int, input().split())) for i in range(N)]
v_sum = sum([i[1] for i in goods])
dp = [float("inf") for i in range(v_sum + 1)]
dp[0] = 0
for i in range(N):
    for j in range(v_sum, -1, -1):
        dp[j] = min(dp[j - goods[i][1]] + goods[i][0], dp[j])

for i in range(v_sum, -1, -1):
    if dp[i] <= W:
        print(i)
        break
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,n=LI()
  w=[]
  v=[]
  for _ in range(n):
    _w,_v=LI()
    w.append(_w)
    v.append(_v)

  dp=[[inf]*(h+10**4+1) for _ in range(n+1)]
  dp[0][0]=0
  for i in range(n):
    for j in range(h+10**4):
      if j<w[i]:
        dp[i+1][j]=dp[i][j]
      else:
        dp[i+1][j]=min(dp[i][j],dp[i+1][j-w[i]]+v[i])
  ans=inf
  for i in range(n+1):
    for j in range(h,h+10**4):
      ans=min(ans,dp[i][j])

  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,n=LI()
  w=[]
  v=[]
  max_w=0
  for _ in range(n):
    _w,_v=LI()
    w.append(_w)
    v.append(_v)
    max_w=max(max_w,_w)

  dp=[[inf]*(h+10**4+1) for _ in range(n+1)]
  dp[0][0]=0
  for i in range(n):
    for j in range(h+max_w):
      if j<w[i]:
        dp[i+1][j]=dp[i][j]
      else:
        dp[i+1][j]=min(dp[i][j],dp[i+1][j-w[i]]+v[i])
  ans=inf
  for i in range(n+1):
    for j in range(h,h+max_w):
      ans=min(ans,dp[i][j])

  return ans

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

#高速化heapqダイクストラ
from collections import *
from heapq import*
import sys
input=lambda:sys.stdin.readline()


def BFS(point,d):
    cost=[1e7]*(n+1)
    cost[point]=0
    Q=deque([(0,point)])
    
    while Q:
        c,p = Q.popleft()
        for np in d[p]:
            if cost[np]==1e7:
                cost[np]=c+1
                Q.append((c+1,np))
    return cost

n=int(input())
d={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a].append(b)
    else:
        d[a]=[b]
    if b in d.keys():
        d[b].append(a)
    else:
        d[b]=[a]
        
x=BFS(1,d)[1:]
y=BFS(n,d)[1:]

#print(x,y)

F=0
S=0

for s,t in zip(x,y):
    if s<=t:
        F+=1
    else:
        S+=1

if F<=S:
    print("Snuke")
else:
    print("Fennec")


### FIXED CODE ###

#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = MI_()
        edge[a].append(b)
        edge[b].append(a)

    set_A = set()
    set_B = set()
    a_stack = [0]
    b_stack = [N - 1]
    for _ in range(N - 1):
        tmp_a = []
        tmp_b = []
        while a_stack:
            from_ = a_stack.pop()
            for to in edge[from_]:
                if to not in set_A and to not in set_B:
                    tmp_a.append(to)
                    set_A.add(to)
        while b_stack:
            from_ = b_stack.pop()
            for to in edge[from_]:
                if to not in set_A and to not in set_B:
                    tmp_b.append(to)
                    set_B.add(to)
        a_stack = tmp_a
        b_stack = tmp_b
    if len(set_A) > len(set_B):
        print("Fennec")
    else:
        print("Snuke")


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

# your code goes here
a=int(input())
if a%2 == 0:
	k = a
else:
	k = a + 1
while k>0:
	if k %2== 0 and k % a ==0:
		print(k)
		quit()
	k = k + a

### FIXED CODE ###

a=int(input())
if a%2 == 0:
	print(a)
else:
	print(a*2)
### BUGGY CODE ###

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

baseline = sum(A)
seq = ''.join(str(n) for n in A)

for i in range(Q):
    b, c = input().split()
    n = seq.count(b)
    diff = int(c) - int(b)
    baseline += n * diff
    seq = seq.replace(b, c)

    print(baseline)

### FIXED CODE ###

from collections import Counter

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

counter = Counter(A)

baseline = sum(k*v for k, v in counter.items())
#print(baseline)

for i in range(Q):
    b, c = map(int, input().split())
    n = counter.pop(b, 0)
    baseline += n * (c - b)
    counter[c] += n
    print(baseline)
### BUGGY CODE ###

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

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

if __name__ == '__main__':
    dots = XY[:]

    import sys
    INT_MAX = sys.maxsize

    x_dots = [(x, y) for x, y in dots]
    x_dots = sorted(x_dots)
    y_dots = [(x, y) for x, y in dots]
    y_dots = sorted(y_dots, key=lambda x: x[1])

    ans = INT_MAX
    for i in range(N):
        for j in range(i+1, N):
            sub_x_dots = set(x_dots[i:j+1])
            xl = x_dots[i:j+1][0][0]
            xr = x_dots[i:j+1][-1][0]
            for k in range(N):
                for l in range(k+1, N):
                    sub_y_dots = set(y_dots[k:l+1])
                    #print("----")
                    #print(x_dots[i:j+1])
                    #print(y_dots[k:l+1])
                    intersection = sub_x_dots & sub_y_dots
                    if len(intersection) >= K:
                        yl = y_dots[k:l+1][0][1]
                        yr = y_dots[k:l+1][-1][1]
                        area = (xl-xr) * (yl-yr)

                        ans = min(ans, area)
    print(ans)
                
                

### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

from itertools import combinations

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

comb = list(combinations(l, 3))

ans = 0
for i in comb:
    a = i[0]
    b = i[1]
    c = i[2]
    if (a < b + c) and (b < c + a) and (c < a + b):
        ans += 1
print(ans)



### FIXED CODE ###

from bisect import bisect_left

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

ans = 0
l.sort()

for i in range(n):
    for j in range(i + 1, n):
        a = l[i]
        b = l[j]
        idx = bisect_left(l, a + b)
        # print(a, b, idx)

        ans += idx - (j + 1)


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

n, l, t = map(int, input().split())
ants = [tuple(map(int, input().split())) for _ in range(n)]
place = []
clock = []
anticlock = []
for i, (x, w) in enumerate(ants):
    if w == 1:
        place.append((x + t) % l)
        clock.append((i, x))
    else:
        place.append((x - t) % l)
        anticlock.append((i, x))

def dist(x, y):
    if x < y: return y - x
    else: return y - x + l

swap = []
for i, x in clock:
    for j, y in anticlock:
        tmp = t * 2
        d = dist(x, y)
        if tmp > d:
            tmp -= d
            swap.append((d, i, j))
            for c in range(1, tmp // l):
                swap.append((d + c * l, i, j))

swap.sort(reverse=True)
for d, i, j in swap:
    place[i], place[j] = place[j], place[i]
for p in place:
    print(p)

### FIXED CODE ###

n, l, t = map(int, input().split())
ants = [tuple(map(int, input().split())) for _ in range(n)]

def dist(x, y, sign_0):
    if sign_0 == -1:
        x, y = y, x
    if x < y: return y - x
    else: return y - x + l

place = []
for i, (x, w) in enumerate(ants):
    sign = 1 if w == 1 else -1
    place.append((x + t * sign) % l)
    if i == 0:
        num = 0
        x_0 = x
        sign_0 = sign
    elif sign_0 * sign == -1:
        length = 2 * t
        d = dist(x_0, x, sign_0)
        if length > d or (length == d and sign_0 == -1):
            num = (num + sign_0) % n
            length -= d
            num = (num + (length // l) * sign_0) % n
            if length % l == 0 and sign_0 == 1:
                num = (num - 1) % n
    else: continue

place.sort()
i_0 = (place.index((x_0 + t * sign_0) % l) - num) % n
place.count((x_0 + t * sign_0) % l)

for i in range(i_0, n + i_0):
    i = i % n
    print(place[i])
### BUGGY CODE ###


import copy

class MyClass():

    maxSum = 0

    def do(self, baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if nokoriSousaCount < 0:
            return

        sum = 0
        minNum = 0

        for each in _temochi:
            sum += each
            if each < 0 and each < minNum:
                minNum = each

        if self.maxSum < sum:
            self.maxSum = sum

        if leftIndex <= rightIndex:
            temochi = copy.copy(_temochi)
            temochi.append(baseList[leftIndex])
            self.do(baseList, temochi, leftIndex + 1, rightIndex, nokoriSousaCount - 1)

            temochi = copy.copy(_temochi)
            temochi.append(baseList[rightIndex])
            self.do(baseList, temochi, leftIndex, rightIndex - 1, nokoriSousaCount - 1)
            
        self.removeMin(_temochi, minNum, leftIndex, rightIndex, nokoriSousaCount - 1)

    def removeMin(self, _temochi, minNum, leftIndex, rightIndex, nokoriSousaCount):
        if minNum < 0 and len(_temochi) > 0 and nokoriSousaCount > 0:
            #minNum = min(_temochi)
            #if minNum < 0:
                #temochi = copy.copy(_temochi)
            _temochi.remove(minNum)
            self.do(baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount)


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

doClass = MyClass()
doClass.do(baseList, [], 0, count - 1, opeCount)

print(doClass.maxSum)




### FIXED CODE ###

class MyClass():
    maxNumber = 0

    def roop(self, baseList, opeCount):
        listCount = len(baseList)
        roopMax = listCount if listCount < opeCount else opeCount
        for leftCount in range(0, roopMax):
            self.getMax(baseList[0: leftCount + 1], opeCount - leftCount - 1)

            for rightCount in range(1, roopMax - leftCount + 1):
                leftList = baseList[0: leftCount]
                rightList = baseList[listCount - rightCount : listCount]
                handList = leftList + rightList

                self.getMax(handList, opeCount - leftCount - rightCount)

                

    def getMax(self, handList, remainOpeCount):
        if len(handList) < 1:
            return

        maxVal = 0
        removeCount = 0

        if remainOpeCount > 0:
            handList.sort()
            for each in handList:
                if each < 0:
                    removeCount += 1
                    remainOpeCount -= 1
                    if remainOpeCount < 1:
                        break
        
        maxVal = sum(handList[removeCount:])
        self.maxNumber = max([maxVal, self.maxNumber])


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

my = MyClass()
my.roop(baseList, opeCount)
print(my.maxNumber)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
max_a = a[n-1]
a.remove(max_a)
for i in range(max_a // 2, -1, -1):
    if i in a:
        print(max_a, i)
        break
    if max_a - i in a:
        print(max_a, max_a - i)
        break


### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
max_a = a[-1]
print(max_a, min(a, key=lambda x: abs(max_a - 2*x)))
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
miss = 0

for i in range(n):
    s = p[0:i]
    if not s:
        continue
    if p[i] > p[i-1]:
        miss += 1
        continue

    #if p[i] > max(s):
    #    miss += 1
    #    continue
 
    s = sorted(s,reverse=True)
    for j in range(i):
        if p[i] > s[j]:
            miss += 1
            break

print(n-miss)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
cnt = 0
t = p[0]

for i in range(n):
    if t >= p[i]:
        cnt += 1
        t = p[i]


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

n = int(input())
s = list(map(int , input().split()))
count = 0
for i in range(n):
  if s[i] == min(s[:i + 1]):
    count += 1

print(count)

### FIXED CODE ###

n = int(input())
s = list(map(int , input().split()))
count = 0
mini = s[0]
for i in range(n):
  mini = min(mini , s[i])
  if s[i] == mini:
    count += 1

print(count)
### BUGGY CODE ###

#coding: utf-8
m,n = map(int,input().split())
# div = [0]
div = [1]
flg = 0

if m % 2 == 0 and n % 2 == 0:
    div.append(2)

# while i < 0:
    # if m 
for i in range(3,m,2):
    if m % i == 0 and n % i == 0 and i % 2 == 1:
        # ans += 1
        # m = m / i
        # n = n / i
        for j in range(1,len(div)):
            if i % div[j] == 0:
                flg = 1
                break
        if flg == 0:
            div.append(i)
        else:
            flg = 1
    

    # print(student[i]-1)
    # toukou[student[i]-1] = i+1
# print(" ".join(map(str,div)))
print(len(div))


### FIXED CODE ###

#coding: utf-8
from fractions import gcd
import math

# GCDの約数を素因数分解する
def primeFactor(n):
    flg = 0
    count = 0
    tmp = math.sqrt(n)
    i = 2

    if n == 1:
        return 1

    while i <= tmp:
        # print(str(i)+str(',')+str(gcd_cnt))
        if n % i == 0:
            if flg == 0:
                flg = 1
                count += 1
            n = n // i
        else:
            flg = 0
            i += 1
    # if flg == 1:
    #     count += 1
    # print(str('素数=')+str(count)+str(' n=')+str(n)+str(' i=')+str(i))
    if n > 1:
        count += 1
    # 1を足す
    count += 1
    return count


# # print(len(div))
m,n = map(int,input().split())
p = gcd(m,n)
# print(str('gcd=')+ str(p))
ans = primeFactor(p)
print(ans)
### BUGGY CODE ###

l,r = map(int,input().split())
r = min(r,l+4038)
ans = 2018

for i in range(l,r+1):
    for j in range(i+1,r+1):
        ans = min(i*j%2019,ans)
print(ans)

### FIXED CODE ###

l,r = map(int,input().split())
r = min(r,l+678)
ans = 2018

for i in range(l,r+1):
    for j in range(i+1,r+1):
        ans = min(i*j%2019,ans)
print(ans)
### BUGGY CODE ###

from fractions import gcd

a,b = map(int,input().split())
c = gcd(a,b)

ans = 0
i = 2
check = False
while c != 1:
    while c % i == 0:
        c = c // i
        check = True
    i = i + 1
    if check:
        ans += 1
    check = False
print(ans + 1)

### FIXED CODE ###

from fractions import gcd

a,b = map(int,input().split())
c = gcd(a,b)

ans = 0
i = 2
check = False
while c != 1:
    #print(c,i)
    while c % i == 0:
        #print('a')
        c = c // i
        check = True
    i = i + 1
    if check:
        ans += 1
    check = False
    if i > 1000000:
        print(ans+2)
        exit()
print(ans + 1)
### BUGGY CODE ###

n, m = map(int, input().split())
l = list(list(map(int, input().split())) for _ in range(m))
c = []
for i in range(m):
  if l[i][0] == n:
    c.append(l[i][1])
  elif l[i][1] == n:
    c.append(l[i][0])

for i in l:
  for j in c:
    if i == [1, j] or i == [j, 1]:
      d = 1
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n, m = map(int, input().split())
c = [[] for _ in range(n+1)]
for i in range(m):
  a, b = map(int, input().split())
  c[a].append(b)
  c[b].append(a)

for i in c[1]:
  if n in c[i]:
    print('POSSIBLE')
    exit()

print('IMPOSSIBLE')
### BUGGY CODE ###

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

dp = [float('inf')] * (h+1)
dp[0] = 0

for i in range(h + 1):
    for a, b in ab:
        dp[i] = min(dp[i], dp[max(i - a, 0)] + b)
print(dp[h])


### FIXED CODE ###

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

dp = [float('inf')] * (h+1)
dp[0] = 0

for i in range(h + 1):
    for a, b in ab:
        dp[i] = min(dp[i], dp[max(i - a, 0)] + b)
print(dp[h])
### BUGGY CODE ###

n, t = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(n)]

m, d = 0, [0] * t
for a, b in sorted(ab):
  m = max(m, b+d[t-1])
  for l in range(t-1,a-1,-1):
    if(b+d[l-a] > d[l]):
      d[l] = b+d[l-a]
print(m)

### FIXED CODE ###

n, t = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
  a[i], b[i] = map(int, input().split())

dp = [[[0] * (t+1) for i in range(n+1)] for j in range(2)]
for i in range(n):
  for d in range(2):
    for l in range(1,t+1):
      if(l < a[i]):
        dp[d][i+1][l] = max(dp[d][i][l], d*(b[i]+dp[0][i][l-1]))
      else:
        dp[d][i+1][l] = max(dp[d][i][l], b[i]+dp[d][i][l-a[i]], d*(b[i]+dp[0][i][l-1]))

print(dp[1][n][t])
### BUGGY CODE ###

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

k2 = k // 2
bet = [210000] * (n - 1) + [0] * 1
for i in range(n):
    for j in range(n):
        if i != j:
            if (0 <= a[i] < 10) and (10 < a[j] < 20):
                bet[i] = min(bet[i], abs(a[i]) - (a[j] - k))
            elif (0 <= a[j] < 10) and (10 < a[i] < 20):
                bet[i] = min(bet[i], abs(a[j]) - (a[i] - k))
            else:
                bet[i] = min(bet[i], abs(a[i] - a[j]))
#print(bet)
print(sum(bet))


### FIXED CODE ###

k,n = map(int, input().split())
a = list(map(int,input().split()))
max_dist = 0
for i in range(n):
    nxt = (i + 1) %n
    distance = a[nxt] - a[i]
    if distance < 0:
        distance += k
    max_dist = max(max_dist, distance)
print(k - max_dist)
### BUGGY CODE ###

n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))
ans=0
for i in T:
    if i in S:
        ans += 1
        S.remove(i)
print(ans)

### FIXED CODE ###

input()
a=set(input().split())
input()
b=set(input().split())

print(len(a&b))
### BUGGY CODE ###

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

dp = [float("inf")]*len(h)
dp[0] = 0

for i in range(len(h)):
    for j in range(1,min(i+1,K+1)):
        dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]), dp[i])
        
print(dp[N-1])




### FIXED CODE ###

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

dp = [float("inf")]*len(h)
dp[0] = 0

for i in range(len(h)):
    for j in range(1,min(i+1,K+1)):
        dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]), dp[i])
        
print(dp[N-1])