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

D = []

def append(value):
    global D

    hashvalue = ""
    for letter in value:
        hashvalue += str(ord(letter))

    D.append(int(hashvalue))

def find(value):
    hashvalue = ""
    for letter in value:
        hashvalue += str(ord(letter))

    hashvalue = int(hashvalue)

    left = 0
    right = len(D) - 1

    while True:
        mid = (left + right) // 2

        if not 0 <= mid < len(D):
            print("no")
            return

        if D[mid] == hashvalue:
            print("yes")
            return
        elif D[mid] < hashvalue:
            left = mid + 1
        else:
            right = mid - 1

        if left > right:
            print("no")
            return


def main():
    global D

    N = int(input())
    finds = []

    for _ in range(N):
        command, value = [i for i in input().split()]

        if command == "insert":
            append(value)
            D.sort()
        else:
            find(value)

main()



### FIXED CODE ###

import sys
import collections

# Set max recursion limit
sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]


def main():
    N = int(input())
    C = [input().split() for _ in range(N)]

    D = collections.defaultdict(lambda: 0)

    for c in C:
        command, value = c

        if command == "insert":
            D[value] = 1
        else:
            if D[value] == 1:
                print("yes")
            else:
                print("no")


main()
### BUGGY CODE ###

import math

n = input()
a = input().split()
N = int(n)

ans_list = []
ann = []
for i in range(N):
    ana = 1
    ans = 0
    for j in range(i+1):
        ana = ana * int(a[j])
    ana = ana -1
    for k in range(i+1):
        ans += int(ana % int(a[k]))
    ans_list.append(ans)

ans_list.sort()
ans_list.reverse()
print(str(ans_list[0]))



### FIXED CODE ###

import math

n = input()
a = input().split()
N = int(n)

ans_list = []
ann = []
ana = 1
for j in range(N):
    ana = ana * int(a[j])
ana = ana -1
ans = 0
for k in range(N):
    ans += int(ana % int(a[k]))
ans_list.append(ans)

ans_list.sort()
ans_list.reverse()
print(str(ans_list[0]))
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0
for index,p in enumerate(P):
  if all(p <= pp for pp in P[:index]):
    ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0
min_num = P[0]
for i in range(len(P)):
  if P[i] <= min_num:
    ans += 1
    min_num = P[i]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    S = input()
    Q = II()
    
    direction = 1
    for i in range(Q):
        query = input()
        if query == '1':
            direction *= -1
        else:
            _, f, c = query.split()
            if direction == 1:
                if f == '1':
                    S = "".join([c,S])
                else:
                    S = "".join([S,c])
            else:
                if f == '1':
                    S = "".join([S,c])
                else:
                    S = "".join([c,S])
    if direction == 1:
        print(S)
    else:
        print(S[::-1])

main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    S = input()
    Q = II()
    
    direction = 1
    pre = []
    sur = []

    for i in range(Q):
        query = input()
        if query == '1':
            direction *= -1
        else:
            _, f, c = query.split()
            if direction == 1:
                if f == '1':
                    pre.append(c)
                else:
                    sur.append(c)
            else:
                if f == '1':
                    sur.append(c)
                else:
                    pre.append(c)

    if direction == 1:
        ans = "".join(pre[::-1]) + S + "".join(sur)
    else:
        ans = "".join(sur[::-1]) + "".join(S[::-1]) + "".join(pre)
    print(ans)

main()
### BUGGY CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]

    ans = ["@" for _ in range(gcd+2)]
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != "@" and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]
    t_set = set(t_idx)

    for idx in s_idx:
        if idx in t_set:
            if s[idx * n // gcd] != t[idx * m // gcd]:
                print(-1)
                exit(0)

    print(gcd)


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

n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:[x[0],-x[1]])+[[float('inf'),0]]
for i in range(n):l[i][0]-=1
w=[n]*m
for i in range(m):
    j=0
    while l[j][0]<=i:
        if l[j][1]>l[w[i]][1] and j not in w:
            w[i]=j
        j+=1
print(sum(l[w[i]][1] for i in range(m)))

### FIXED CODE ###

from heapq import heappop, heappush

n,m=map(int,input().split())
a=[]
for i in range(n):
    heappush(a,list(map(int,input().split())))
heap=[]
s=0
for i in range(m):
    while 1:
        if len(a)==0:break
        else:
            if a[0][0]==i+1:heappush(heap,-heappop(a)[1])
            else:break
    if len(heap)>0:s+=-heappop(heap)
print(s)
### BUGGY CODE ###

N = int(input())
list = list(map(int,input().split()))
ans = 1
for i in list:
  ans *= i
  if ans == 0:
    break
if ans > 10**18:
  ans = -1
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
list = list(map(int,input().split()))
ans = np.prod(list)
if ans > 10**18 or ans == 0:
  ans = -1
if 0 in list:
  ans = 0
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
val = [0]*(W+1)
for i in range(N):
  w, v = map(int, input().split())
  for j in reversed(range(w,W+1)):
    val[j] = max(val[j], val[j-w] + v) 
print(val[W])

### FIXED CODE ###

N, W = map(int, input().split())
val = [0]*(W+1)
for i in range(N):
  w, v = map(int, input().split())
  for j in reversed(range(w,W+1)):
    val[j] = max(val[j], val[j-w] + v) 
print(val[W])
### BUGGY CODE ###

import numpy as np
N,W = map(int,input().split())
#N = int(input())
dp =[[0 for i in range(W+1)] for j in range(N+1)]
w = [0]*(N)
v = [0]*N
for i in range(N):
  w[i],v[i] =  map(int,input().split())
for i in range(N):
  for j in range(W+1):
    if (j >= w[i]):
      dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i])
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(dp[N][W])

### FIXED CODE ###

import numpy as np
N,W = map(int,input().split())
#N = int(input())
dp =[[0 for i in range(W+1)] for j in range(N+1)]
w = np.zeros(W+1)
v = [0]*N
ndp = np.zeros(W + 1, dtype=np.int64)
for i in range(N):
  w[i],v[i] =  map(int,input().split())
for i in range(N):
  ndp[w[i]:] = np.maximum(ndp[:-w[i]] + v[i], ndp[w[i]:])
print(ndp[W])
### BUGGY CODE ###

from numba import njit

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

@njit
def solution(A,N):
    mod = (10**9)+7
    res = 0
    for i in range(N-1):
        for j in range(i+1,N):
           res += ((A[i] % mod) * (A[j] % mod)) % mod
    return res
  
mod = (10**9)+7
res = solution(A,N)
print(res % mod)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
A_j = sum(A)
mod = (10**9)+7
res = 0
for i in range(N-1):
    A_j -= A[i]
    res += (A[i] * (A_j % mod)) % mod

print(res % mod)
### BUGGY CODE ###

def solve():
    N = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in a:
        check = a.count(i)
        check2 = a.count(i-1)
        check3 = a.count(i+1)
        if ans < check+check2+check3:
            ans = check+check2+check3

    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N = int(input())
    a = list(map(int, input().split()))
    count = [0]*100000

    for i in a:
        count[i] += 1

    print(max(map(sum,zip(count,count[1:],count[2:]))))


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

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

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

for i in range(n):
    for j in range(i,n):
        if s[i] !=s[j]:
            continue
        else:
            cnt = 0
            for k in range(min(n-j,j-i)):
                if s[i+k] ==s[j+k]:
                    cnt += 1
                else:
                    break
            dp[i][j] = cnt 
mx = 0
for i in range(n):
    mx = max(mx,max(dp[i]))

print(mx)
        

### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    
    from itertools import product
    for i,j in product(reversed(range(n)),repeat=2):###for を置き換え
        if j>i:
            continue
        if s[i]!=s[j]:
            dp[i][j] = 0 #continueではない	    
        else:
           	dp[i][j] = dp[i+1][j+1] +1
           	"""
            これでは結局ループしている
            cnt = 0
            for k in range(min(n-j,j-i)):
                if s[i+k] ==s[j+k]:
                    cnt += 1
                else:
                    break
            dp[i][j] = cnt
            """
    mx = 0
    #print(dp)
    for i in range(n):
      	for j in range(i):###
        	mx = max(mx,min(i-j,dp[i][j]))###i-jで抑える
    print(mx)

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

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, D, A = map(int, input().split())
    monster = {}
    X = []
    for _ in range(N):
        x, h = map(int, input().split())
        monster[x] = h
        X.append(x)

    X.sort()
    ans = 0
    for i in range(N):
        k = X[i]
        v = monster[k]
        if v <= 0:
            continue

        cnt = (v + A - 1) // A
        ans += cnt

        for j in range(i + 1, N):
            x = X[j]
            if k + 2 * D < x:
                break
            if monster[x] < 0:
                continue

            monster[x] -= A * cnt

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, D, A = map(int, input().split())
    monster = {}
    X = []
    for _ in range(N):
        x, h = map(int, input().split())
        monster[x] = h
        X.append(x)

    X.sort()

    # x, damage
    q = deque([])

    acc_damage = 0

    ans = 0
    for i in range(N):
        x = X[i]
        h = monster[x]

        while q and q[0][0] < x:
            p, damage = q.popleft()
            acc_damage -= damage

        if h - acc_damage <= 0:
            continue

        cnt = (h - acc_damage + A - 1) // A
        ans += cnt
        acc_damage += cnt * A

        q.append((x + 2 * D, cnt * A))

    print(ans)


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

s = input()
t = input()

table = [['' for j in range(len(t) + 1)] for i in range(len(s) + 1)]

for i, si in enumerate(s):
    table_pre = table[i]
    table_cur = table[i + 1]
    for j, tj in enumerate(t):
        if si == tj:
            table_cur[j + 1] = table_pre[j] + si
        else:
            x = table_cur[j]
            y = table_pre[j + 1]
            table_cur[j + 1] = x if len(x) > len(y) else y
print(table[-1][-1])


### FIXED CODE ###

s = input()
t = input()

table = [[0 for j in range(len(t) + 1)] for i in range(len(s) + 1)]

for i, si in enumerate(s):
    table_pre = table[i]
    table_cur = table[i + 1]
    for j, tj in enumerate(t):
        if si == tj:
            table_cur[j + 1] = table_pre[j] + 1
        else:
            table_cur[j + 1] = max(table_cur[j], table_pre[j + 1])

ls, lt = len(s), len(t)
ans = ''
while ls and lt:
    if table[ls][lt] == table[ls][lt - 1]:
        lt -= 1
    elif table[ls][lt] == table[ls - 1][lt]:
        ls -= 1
    else:
        ans = s[ls - 1] + ans
        ls -= 1
        lt -= 1
print(ans)
### BUGGY CODE ###


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

slink = []
glink = []

for i in range(M):

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

    if a == 1:
        slink.append(b)
    elif b == 1:
        slink.append(a)
    elif a == N:
        glink.append(b)
    elif b == N:
        glink.append(a)

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"

print (ans)

### FIXED CODE ###


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

slink = {}
glink = {}

for i in range(M):

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

    if a == 1:
        slink[b] = 1
    elif b == 1:
        slink[a] = 1
    elif a == N:
        glink[b] = 1
    elif b == N:
        glink[a] = 1

ans = "IMPOSSIBLE"
for i in slink:

    if i in glink:
        ans = "POSSIBLE"
        break

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

n = int(input())

a = list(map(int, input().split()))
m = 1
for i in range(n):
  m *= a[i]
if m > 10**18:
  print('-1')
else:
  print(m)

### FIXED CODE ###

n = int(input())
a = sorted(map(int, input().split()))
ans = 1
for i in a:
    ans *= i
    if ans > 10 ** 18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
l = nl()

l = sorted(l)[::-1]

ans = 0

for a in range(n):
    for b in range(a+1,n):
        for c in range(b+1,n):
            A = l[a]
            B = l[b]
            C = l[c]

            if A >= B + C:
                break

            if B < A + C and C < A + B:
                ans += 1

print(ans)

### FIXED CODE ###

import bisect

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
l = nl()

l = sorted(l)

ans = 0

for a in range(n):
    fl = 0
    A = l[a]
    for b in range(a+1,n):
        B = l[b]

        idx = bisect.bisect_left(l, A+B)
        ans += max(0,idx-b-1)

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

s=input()
t=input()

dp=[[-1]*(3001) for x in range(3001)]
arr = ""
# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)


for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            if s[i] == t[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)

### FIXED CODE ###

s=input()
t=input()

dp=[[-1]*(len(t)+1) for x in range(len(s)+1)]
arr = ""
for i in range(len(s),-1,-1):
    for j in range(len(t),-1,-1):
        if i>=(len(s)) or j>=(len(t)):
            dp[i][j] = 0
        else:
            if s[i] == t[j]:
                dp[i][j] = dp[i+1][j+1] + 1
            else:
                dp[i][j] = max(dp[i+1][j],dp[i][j+1])

l=dp[0][0]
i,j=0,0
while len(arr)!=l:
    if s[i] == t[j]:
        arr=arr+s[i]
        i+=1
        j+=1
    else:
        if dp[i+1][j]>=dp[i][j+1]:
            i+=1
        else:
            j+=1

print(arr)



# def func(i,j):
    # if i>=(len(s)) or j>=(len(t)):
    #     return 0
    # if dp[i][j]!=-1:
    #     return dp[i][j]
    # if s[i]==t[j]:
    #     dp[i][j] = func(i+1,j+1)+1
    #     return dp[i][j]
    # if s[i]!=t[j]:
    #     dp[i][j] = max(func(i+1,j),func(i,j+1))
    #     return dp[i][j]
# l=func(0,0)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

def resolve():
    def rec(i, j, k):
        if dp[i][j][k] >= 0:
            return dp[i][j][k]
        if i == 0 and j == 0 and k == 0:
            return 0.0

        res = 0.0
        if i > 0:
            res += rec(i - 1, j, k) * i
        if j > 0:
            res += rec(i + 1, j - 1, k) * j
        if k > 0:
            res += rec(i, j + 1, k - 1) * k
        res += N
        res *= 1.0 / (i + j + k)
        dp[i][j][k] = res

        return dp[i][j][k]

    N = int(input())
    A = list(map(int, input().split()))
    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 0.0
    print(rec(one, two, three))


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for sushi in range(1, N + 1):
        for k in range(sushi + 1):
            for j in range(0, sushi - k + 1):
                i = sushi - k - j
                if i != 0:
                    dp[i][j][k] += dp[i - 1][j][k] * i / sushi
                if j != 0:
                    dp[i][j][k] += dp[i + 1][j - 1][k] * j / sushi
                if k != 0:
                    dp[i][j][k] += dp[i][j + 1][k - 1] * k / sushi
                dp[i][j][k] += N / sushi
    print(dp[one][two][three])


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

import numpy as np

N, W = map(int, input().split())
w = np.zeros(N, dtype=int)
v = np.zeros(N, dtype=int)
dp = np.zeros((N+1, W+1),dtype=int)

for i in range(N):
    w[i], v[i] = map(int, input().split())
    for j in range(W+1):
        if w[i] > j:
            dp[i+1, j] = dp[i, j]
        else:
            dp[i+1, j] = max(dp[i, j], dp[i, j-w[i]] + v[i])

print(dp[N,W])

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
dp = np.zeros((W+1),dtype=int)

for _ in range(N):
    w, v = map(int, input().split())
    dp[w:] = np.maximum(dp[w:], dp[:-w] + v)

print(dp.max())
### BUGGY CODE ###

from collections import deque

def sum_to(n):
    return (n+1)*int((n/2))+(n%2)*((n+1)/2)

def expected(n):
    return sum_to(n) / n

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

max_sum = 0
select = deque()
c = 0
for i in P:
    e_val = expected(i)
    select.append(e_val)
    if len(select) == K:
        s = sum(select)
        if s > max_sum:
            max_sum = s
        select.popleft()

print(max_sum)

### FIXED CODE ###

from collections import deque

def sum_to(n):
    return (n+1)*int((n/2))+(n%2)*((n+1)/2)

def expected(n):
    return sum_to(n) / n

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

max_sum = 0
cur_sum = 0
select = deque()
c = 0
for i in P:
    e_val = expected(i)
    select.append(e_val)
    cur_sum += e_val
    if len(select) == K:
        if cur_sum > max_sum:
            max_sum = cur_sum
        cur_sum -= select.popleft()

print(max_sum)
### BUGGY CODE ###

import numpy as np


def is_input(node, path):
    for i in range(len(path)):
        if path[i][node]:
            return True
    return False


def topological_sort(path):
    S = []
    path = path.copy()
    for i in range(len(path[0])):
        if any(path[:, i]):
            pass
        else:
            S.append(i)
    res = []
    while len(S) > 0:
        now = S.pop()
        res.append(now)
        for i, f in enumerate(path[now]):
            if f:
                path[now][i] = False
                if not is_input(i, path):
                    S.append(i)
    return res


N, M = map(int, input().split(" "))
path = np.array([[False for i in range(N)] for i in range(N)])


for i in range(N+M-1):
    a, b = map(int, input().split(" "))
    path[a-1][b-1] = True

sorted_nodes = topological_sort(path)
dict_sorted_nodes = {}
for i, v in enumerate(sorted_nodes):
    dict_sorted_nodes[v] = i


for line in path.T:
    input_nodes = []
    for j, f in enumerate(line):
        if f:
            input_nodes.append(j)

    if len(input_nodes) == 0:
        print(0)
        continue
    if len(input_nodes) == 1:
        print(input_nodes[0]+1)
        continue
    temp_i = 0
    for j in input_nodes:
        temp_i = max(temp_i, dict_sorted_nodes[j])

    print(sorted_nodes[temp_i]+1)



### FIXED CODE ###

from collections import deque
from operator import itemgetter


def topolo():
    q = deque(v1 for v1 in range(N) if ins[v1] == 0)
    res = []
    popleft, append = q.popleft, q.append
    res_append = res.append
    while q:
        v1 = popleft()
        res_append(v1)
        for v2 in edges[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                append(v2)
    return res


N, M = map(int, input().split(" "))
edges = [[] for _ in [0]*N]
rev = [[] for _ in [0]*N]

ins = [0]*N

for a, b in (map(int, input().split(" ")) for _ in [0]*(N+M-1)):
    edges[a-1].append(b-1)
    rev[b-1].append(a-1)
    ins[b-1] += 1

sorted_nodes = topolo()
order = [i for i, v in sorted(enumerate(sorted_nodes), key=itemgetter(1))]

for input_nodes in rev:
    l = len(input_nodes)
    if l == 0:
        print(0)
        continue
    elif l == 1:
        print(input_nodes[0] + 1)
        continue
    temp = 0
    for node in input_nodes:
        temp = max(temp, order[node])
    print(sorted_nodes[temp] + 1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main(N,M,islands):
    queue = []
    flag = False
    islands_s = sorted(islands, key=lambda x: x[0])
    islands_t = sorted(islands, key=lambda x: x[1], reverse=True)
    for a,b in islands_s:
        if(a==1):
            queue.append(b)
        else:
            break
    for a,b in islands_t:
        if(b!=N):
            break
        elif(a in queue and b==N):
            flag = True
            
    print("POSSIBLE") if flag else print("IMPOSSIBLE")

if __name__ == '__main__':
    N, M = map(int, input().split())
    islands = []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1 or b==N):
            islands.append([a,b])
    main(N,M,islands)

### FIXED CODE ###

# -*- coding: utf-8 -*-

def main(N,M,visited,queue):
    ans = "IMPOSSIBLE"

    for i in queue:
        if visited[i-1] == True:
            ans = "POSSIBLE"
            break
            
    print(ans)

if __name__ == '__main__':
    N, M = map(int, input().split())
    visited,queue = [False]*N, []
    for i in range(M):
        a, b = map(int, input().split())
        if(a==1):
            visited[b-1] = True
        elif(b==N):
            queue.append(a)
    main(N,M,visited,queue)