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

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


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[INF] * w for _ in range(h)]
    dist[i1][j1] = 0
    q = deque([(i1, j1)])
    while q:
        i, j = q.popleft()
        for di, dj in ((-1, 0),  (1, 0), (0, -1), (0, 1)):
            for length in range(1, k + 1):
                nxt_i = i + di * length
                nxt_j = j + dj * length
                if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                    break
                if c[nxt_i][nxt_j] == "@":
                    break
                if dist[i][j] + 1 < dist[nxt_i][nxt_j]:
                    dist[nxt_i][nxt_j] = dist[i][j] + 1
                    q.append((nxt_i, nxt_j))

    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = dist[x2][y2]

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


### FIXED CODE ###

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


def bfs(i1, j1) -> list:
    U, D, L, R = 0, 1, 2, 3
    INF = 10 ** 18
    dist = [[INF] * w for _ in range(h)]
    dist[i1][j1] = 0
    q = deque([(0, i1, j1)])
    while q:
        d, i, j = q.popleft()
        #if dist[i][j] < d:
        #    continue
        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            for length in range(1, k + 1):
                nxt_i = i + di * length
                nxt_j = j + dj * length
                if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                    break
                if c[nxt_i][nxt_j] == "@":
                    break
                if dist[i][j] + 1 > dist[nxt_i][nxt_j]:
                    break
                if dist[i][j] + 1 < dist[nxt_i][nxt_j]:
                    dist[nxt_i][nxt_j] = dist[i][j] + 1
                    q.append((dist[nxt_i][nxt_j], nxt_i, nxt_j))
    return dist


h, w, k = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
c = [input() for i in range(h)]


x1 -= 1
y1 -= 1
x2 -= 1
y2 -= 1
dist = bfs(x1, y1)
ans = dist[x2][y2]

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(h) for h in input().split()]
dp = [0]*N
dp[1] = abs(H[1]-H[0])
for i in range(2, N):
    dp[i] = min([dp[i-j]+abs(H[i]-H[i-j]) for j in range(1, min(K, i)+1)])
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(h) for h in input().split()]
dp = [0]*N
dp[1] = abs(H[1]-H[0])
for i in range(2, N):
    dp[i] = min([dp[i-j]+abs(H[i]-H[i-j]) for j in range(1, min(K, i)+1)])
print(dp[N-1])
### BUGGY CODE ###

import math
nmax = 40
abmax = 10
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = []
for i in range(N):
    Lst = [int(x) for x in input().split()]
    medichine.append(Lst)

dp = {}
#dp初期化
for i in range(N+1):
    for ca in range(nmax*abmax+1):
        for cb in range(nmax*abmax+1):
            dp[i,ca,cb] = INF
dp[0,0,0] = 0

for i in range(N):
    for ca in range(nmax*abmax+1):
        for cb in range(nmax*abmax+1):
            if dp[i,ca,cb] != INF:
                dp[i+1,ca,cb] = min(dp[i+1,ca,cb],dp[i,ca,cb])
                dp[i+1,ca+medichine[i][0],cb+medichine[i][1]] = min(dp[i+1,ca+medichine[i][0],cb+medichine[i][1]], dp[i,ca,cb]+medichine[i][2])

ans = INF
for ca in range(1,nmax*abmax+1):
        for cb in range(1,nmax*abmax+1):
            if ca*Mb == cb*Ma:
                ans = min(ans,dp[N,ca,cb])

if ans == INF:
    ans = -1
print(ans)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
### BUGGY CODE ###

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

ans = 1

for i in range(n):
    ans *= a[i]

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

### FIXED CODE ###

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

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

ans = 1

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

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

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  x, y, a, b, c = map(int, input().split())
  la = list(map(int, input().split()))
  la.sort(reverse=True)
  lb = list(map(int, input().split()))
  lb.sort(reverse=True)
  lc = list(map(int, input().split()))
  lc.sort(reverse=True)
  ca, cb, cc = 0, 0, 0,
  
  s = 0
  while True:
    if sum([ca, cb, cc]) == x+y:
      break
      
    a = la[0] if len(la) > 0 and ca < x else -1
    b = lb[0] if len(lb) > 0 and cb < y else -1
    c = lc[0] if len(lc) > 0            else -1
            
    if a >= b and a >= c:
      s += a
      la.pop(0)
      ca += 1
      continue
      
    if b >= a and b >= c:
      s += b
      lb.pop(0)
      cb += 1
      continue
      
    if c >= b and c >= a:
      s += c
      lc.pop(0)
      cc += 1
  print(s)

if __name__=='__main__':
  main()



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-


def main():
  x, y, na, nb, nc = map(int, input().split())
  la = list(map(int, input().split()))
  la.sort(reverse=True)
  lb = list(map(int, input().split()))
  lb.sort(reverse=True)
  lc = list(map(int, input().split()))
  lc.sort(reverse=True)
  ca, cb, cc = 0, 0, 0
  
  lx = la[:x] + lb[:y] + lc
  lx.sort(reverse=True)
  print(sum(lx[:x+y]))

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

n,m = map(int,input().split())
while n*2 < m:
  n += 1
  m -=2

print(min(n,m//2))

### FIXED CODE ###

n,m = map(int,input().split())
if n*2 <= m:
  x = (m-2*n)//4
  print(min(n+x,(m-2*x)//2))
else:
  print(m//2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jun 20 20:19:33 2017

@author: syaga
"""

if __name__ == "__main__":
    n, q = map(int, input().split())
    a = []
    for i in range(n):
        b = input().split()
        b[1] = int(b[1])
        a.append(b)
    ans = []
    time = 0
    flag = 0
    while True:
        if flag == 1:
            break
        for i in range(len(a)):
            if a[i] == []:
                continue
            if a[i][1] <= q:
                time += a[i][1]
                ans.append([a[i][0], time])
                a[i] = []
                if len(ans) == len(a):
                    flag = 1
                    break
            else:
                a[i][1] -= q
                time += q
    for i in ans:
        print(" ".join(map(str, i)))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jun 20 20:19:33 2017

@author: syaga
"""

if __name__ == "__main__":
    n, q = map(int, input().split())
    a = []
    for i in range(n):
        b = input().split()
        b[1] = int(b[1])
        a.append(b)
    ans = []
    time = 0
    while len(a) != 0:
        x = a.pop(0)
        if x[1] <= q:
            time += x[1]
            ans.append([x[0], time])
        else:
            x[1] -= q
            time += q
            a.append(x)
    for i in ans:
        print(" ".join(map(str, i)))
### BUGGY CODE ###

from collections import deque
d = deque()
for _ in range(int(input())):
  a = input().split()
  if "insert" in a: d.appendleft(int(a[1]))
  elif "deleteFirst" in a: d.popleft()
  elif "deleteLast" in a: d.pop()
  else:
    try: d.remove(int(a[1]))
    except: pass
print(*d)


### FIXED CODE ###

from collections import deque
d = deque()
for _ in range(int(input())):
  a = input()
  if "i" == a[0]: d.appendleft(int(a[7:]))
  elif "F" == a[6]: d.popleft()
  elif "L" == a[6]: d.pop()
  else:
    try: d.remove(int(a[7:]))
    except: pass
print(*d)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans = 0
    a_time = [0]
    b_time = [0]
    for i in range(1, len(a) + 1):
        a_time.append(a_time[i - 1] + a[i - 1])
    for i in range(1, len(b) + 1):
        b_time.append(b_time[i - 1] + b[i - 1])

    for i in range(len(a_time)):
        if a_time[i] > k:
            break
        for j in range(len(b_time)):
            if a_time[i] + b_time[j] > k:
                break
            else:
                ans = max(ans, i + j)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans = 0
    a_time = [0]
    b_time = [0]
    for i in range(1, len(a) + 1):
        a_time.append(a_time[i - 1] + a[i - 1])
    for i in range(1, len(b) + 1):
        b_time.append(b_time[i - 1] + b[i - 1])

    a_max = 0
    b_max = 0
    for i in range(len(a_time)):
        if a_time[i] > k:
            break
        else:
            a_max = i
    for i in range(len(b_time)):
        if b_time[i] > k:
            break
        else:
            b_max = i

    for i in range(len(b_time)):
        if a_time[a_max] + b_time[i] <= k:
            ans = max(ans, a_max + i)
        else:
            if a_max > 0:
                a_max -= 1
    for i in range(len(a_time)):
        if b_time[b_max] + a_time[i] <= k:
            ans = max(ans, b_max + i)
        else:
            if b_max > 0:
                b_max -= 1

    print(ans)

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

def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return

  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  s = ''.join(s)
  for r in range(n):
    remains[-(r+1)] = int(s[n - r - 1:n]) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10) % p
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)


if __name__=='__main__':
  main()


### FIXED CODE ###

n, p = map(int, input().split())
s = list(map(int, list(input())))[::-1]

sum = 0
cnt = [0] * p
cnt[0] = 1

ans = 0
if p in [2, 5]:
    if p == 2:
        ok_list = [0, 2, 4, 6, 8]
    if p == 5:
        ok_list = [0, 5]

    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n - i

else:
    for i in range(n):
        d = s[i] * pow(10, i, p)
        sum = (sum + d) % p
        cnt[sum] += 1
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1) // 2
print(ans)
### BUGGY CODE ###

s=input()
k=int(input())
n=len(s)
d=set()
#d={s[i:j+1] for j in range(i,n) for i in range(n)}
#d={s[i:j+1] for i in range(n) for j in range(i,n)}
for i in range(n):
    for j in range(i,max(n,i+5)):
        d.add(s[i:j+1])
ans=sorted(list(d))
print(ans[k-1])


### FIXED CODE ###

s=input()
k=int(input())
n=len(s)
d=set()
#d={s[i:j+1] for j in range(i,n) for i in range(n)}
#d={s[i:j+1] for i in range(n) for j in range(i,n)}
for i in range(n):
    for j in range(i,min(n,i+5)):
        d.add(s[i:j+1])
ans=sorted(list(d))
print(ans[k-1])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
op = [list(map(int, input().split())) for _ in range(m)]
op.sort(key=lambda x: x[1], reverse=True)
a.sort()

idx = 0
for b, c in op:
    for i in range(b):
        if idx < n and a[idx] < c:
            a[idx] = c
            idx += 1

print(sum(a))


### FIXED CODE ###

from operator import itemgetter
n, m = map(int, input().split())
a = list(map(int, input().split()))
op = [list(map(int, input().split())) for _ in range(m)]
op.sort(key=itemgetter(1), reverse=True)
a.sort()

idx = 0
ans = 0
for i in range(n):
    if idx < m and op[idx][1] > a[i]:
        ans += op[idx][1]
    else:
        ans += a[i]

    if idx < m and op[idx][0] > 1:
        op[idx][0] -= 1
    else:
        idx += 1


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

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    S[u-1].append(v-1)
St,T = map(int,input().split())

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
hoge = [0]*N
for i in range(1,N*3+3):
    l = 0
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > D[q][(i-1)%3]:
                D[s][i%3] = D[q][(i-1)%3]+1
                if not s in hoge[:l]:
                    hoge[l] = s
                    l += 1
    queue = hoge[:l]
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = [[]for i in range(N)]
for i in range(M):
    u,v = map(int,input().split())
    S[u-1].append(v-1)
St,T = map(int,input().split())

D = [[float('inf')]*3 for i in range(N)]
D[St-1][0] = 0
queue = [St-1]
i = 0
while queue != []:
    i += 1
    hoge = []
    for q in queue:
        for s in S[q]:
            if D[s][i%3] > i:
                D[s][i%3] = i
                if not s in hoge:
                    hoge.append(s)
    queue = hoge[:]
    if D[T-1][0] != float('inf'):
        break
if D[T-1][0] == float('inf'):
    print(-1)
else:
    print(D[T-1][0]//3)
### BUGGY CODE ###

import sys 
N=int(input())
L=list(map(int,sys.stdin.readline().split()))
counter=0
L.sort()
for i,A in enumerate(L[:-2]):
    for j,B in enumerate(L[i+1:-1],i+1):
        l=j
        r=len(L)-1
        c=(r+l)//2
        while abs(r-l)>1:    
            if A>abs(L[c]-B):
                b=c
                c=(r+c)//2
                l=b
            else:
                b=c
                c=(c+l)//2
                r=b
        if A-abs(L[l]-B)>0 and A-abs(L[r]-B)>0:
            c=r
        elif A-abs(L[l]-B)>0 and A-abs(L[r]-B)<0:
            c=l
        if A>abs(L[c]-B):
            counter+=c-j
print(counter)
    



### FIXED CODE ###


N=int(input())
L=list(map(int,input().split()))
counter=0
L.sort()
for i in range(N-2):
    k=i+2
    for j in range(i+1,N-1):    
        while k < N and L[k] < L[i] + L[j]:
            k += 1
        counter += k - j -1
print(counter)
### BUGGY CODE ###

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

paths = set()
for _ in range(M):
    a, b = map(int, input().split())
    paths.add((a-1, b-1))

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    kick_list = []
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for path in paths:
            if key_room in path:
                else_room = path[0]
                if else_room == key_room:
                    else_room = path[1]
                kick_list.append(path)
                if rooms[else_room] == -1:
                    rooms[else_room] = step
                    next_key_rooms.add(else_room)
                    marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)
    for kick in kick_list:
        if kick in paths:
            paths.remove(kick)

flag = True
for room in rooms[1:]:
    if room == -1:
        flag = False
        print('No')
        break

if flag:
    print('Yes')
    for i in marks:
        print(i+1)


### FIXED CODE ###

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

paths = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    paths[a].add(b)
    paths[b].add(a)

rooms = [-1] * N
rooms[0] = 0
marks = [-1] * (N-1)
key_rooms = [[0]]
for step in range(1, N):
    next_key_rooms = set()
    for key_room in key_rooms[-1]:
        for else_room in paths[key_room]:
            if rooms[else_room] == -1:
                rooms[else_room] = step
                next_key_rooms.add(else_room)
                marks[else_room-1] = key_room
    key_rooms.append(next_key_rooms)

print('Yes')
for i in marks:
    print(i+1)
### BUGGY CODE ###

import heapq
def dijkstra(graph, size, start):
    distance = [float('inf')] * size
    distance[start] = 0
    que = []
    heapq.heappush(que, (0, start))
    while len(que):
        _, u = heapq.heappop(que)
        for length, vi in graph[u]:
            if distance[vi] > distance[u] + length:
                distance[vi] = distance[u] + length
                heapq.heappush(que, (distance[vi], vi))
    return distance

import sys
f = sys.stdin

import collections

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    d = [collections.defaultdict(list), collections.defaultdict(list)]
    
    for ai, bi, cost, time in abct:
        d[0][ai].append((cost, bi))
        d[0][bi].append((cost, ai))
        d[1][ai].append((time, bi))
        d[1][bi].append((time, ai))
        
    k = int(f.readline())
    
    dist = {}
    for i in range(k):
        p, q, r = map(int, f.readline().split())
        
        if (q,r) in dist:
            p, q = q, p
        elif (p,r) not in dist:
            dist[(p,r)] = dijkstra(d[r], m + 1, p)
        print(dist[(p,r)][q])

### FIXED CODE ###

import heapq
import sys
from collections import defaultdict

def dijkstra(graph, size, start):
    d = [float('inf')] * size
    d[start] = 0
    q = [(0, start)]
    while len(q):
        du, u = heapq.heappop(q)
        for length, v in graph[u]:
            if d[v] > du + length:
                d[v] = du + length
                heapq.heappush(q, (d[v], v))
    return d

f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [map(int, f.readline().split()) for _ in range(n)]
    d = [defaultdict(list), defaultdict(list)]
    
    for ai, bi, ci, ti in abct:
        ai -= 1
        bi -= 1
        d[0][ai].append((ci, bi))
        d[0][bi].append((ci, ai))
        d[1][ai].append((ti, bi))
        d[1][bi].append((ti, ai))
    
    dist = {}
    for i in range(int(f.readline())):
        p, q, r = map(int, f.readline().split())
        p -= 1
        q -= 1
        try:
            print(dist[(q,r)][p])
        except KeyError:
            try:
                print(dist[(p,r)][q])
            except:
                dist[(p,r)] = dijkstra(d[r], m, p)
                print(dist[(p,r)][q])
### BUGGY CODE ###

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

def print_map(mp):
    for r in mp:
        print(['{:2d}'.format(n) for n in r])

H, W = map(int, input().split())
mp = [[0 for w in range(W)] for h in range(H)]
mp_row = [[0 for w in range(W)] for h in range(H)]
mp_col = [[0 for w in range(W)] for h in range(H)]
mp_sum = [[0 for w in range(W)] for h in range(H)]

# 0 = なし、 -1 = 障害物、 1=光
for h in range(H):
    s = input()
    for w in range(W):
        if s[w] == ".":
            mp[h][w] = 0
        else:
            mp[h][w] = -1

# 全探索はO(HWHW)となって爆発。
# 縦横でまずカウントするのがよさげ。

## 横のパネル数
for h in range(H):
    st = 0
    cnt = 0
    for w in range(W):
        if mp[h][w] == -1:
            for i in range(st, w):
                mp_row[h][i] = cnt
            cnt = 0
            st = w+1
        elif w == W-1:
            cnt += 1
            for i in range(st, W):
                mp_row[h][i] = cnt
        else:
            cnt += 1

## 縦のパネル数
for w in range(W):
    st = 0
    cnt = 0
    for h in range(H):
        if mp[h][w] == -1:
            for i in range(st, h):
                mp_col[i][w] = cnt
            cnt = 0
            st = h+1
        elif h == H-1:
            cnt += 1
            for i in range(st, H):
                mp_col[i][w] = cnt
        else:
            cnt += 1

#print_map(mp_row)
#print()
#print_map(mp_col)

mx = 0
for h in range(H):
    for w in range(W):
        mx = max(mx, mp_row[h][w]+mp_col[h][w]-1)
print(mx)


### FIXED CODE ###

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

# def print_map(mp):
#     for r in mp:
#         print(['{:2d}'.format(n) for n in r])

H, W = map(int, input().split())
mp = [[] for h in range(H)]
mp_row = [[0 for w in range(W)] for h in range(H)]
mp_col = [[0 for w in range(W)] for h in range(H)]

# True = なし、 False = 障害物
for h in range(H):
    mp[h] = [True if c == "." else False for c in input()]

# 全探索はO(HWHW)となって爆発。
# 縦横でまずカウントするのがよさげ。
# このプログラムはO(HW)だがTLE: カウントしたものの書き込みでO(HHW+HWW)あたりになっている？
# これpythonのforの遅さでTLEしてないか…？

## 横のパネル数
for h in range(H):
    st = 0
    cnt = 0
    for w in range(W):
        if mp[h][w] is False:
            for i in range(st, w):
                mp_row[h][i] = cnt
            cnt = 0
            st = w+1
        elif w == W-1:
            cnt += 1
            for i in range(st, W):
                mp_row[h][i] = cnt
        else:
            cnt += 1

## 縦のパネル数
for w in range(W):
    st = 0
    cnt = 0
    for h in range(H):
        if mp[h][w] is False:
            for i in range(st, h):
                mp_col[i][w] = cnt
            cnt = 0
            st = h+1
        elif h == H-1:
            cnt += 1
            for i in range(st, H):
                mp_col[i][w] = cnt
        else:
            cnt += 1

#print_map(mp_row)
#print()
#print_map(mp_col)

mx = 0
for h in range(H):
    for w in range(W):
        # 重なっている中央を引くのを忘れずに
        mx = max(mx, mp_row[h][w]+mp_col[h][w]-1)
print(mx)
### BUGGY CODE ###

def takahasi(n , m , a):

    ans = "IMPOSSIBLE"
    list1 = []
    listn = []

    for i in range(m):
        if a[i][0] == 1:
            list1.append(a[i][1])
        elif a[i][1] == n:
            listn.append(a[i][0])
    
    for i in range(len(list1)):
        if listn.count(list1[i]) != 0:
            ans = "POSSIBLE"

    return ans

def main():
    n , m = map(int , input().split())
    a = [list(map(int,input().split())) for i in range(m)]
    print(takahasi(n , m , a))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def takahasi(n , m , a):

    ans = "IMPOSSIBLE"
    list1n = []

    for i in range(m):
        if a[i][0] == 1 or a[i][1] == n:
            list1n.append(a[i][1] if a[i][0] == 1 else a[i][0])

    if len(list1n) != len(set(list1n)):
        ans = "POSSIBLE"

    return ans

def main():
    n , m = map(int , input().split())
    a = [list(map(int,input().split())) for i in range(m)]
    print(takahasi(n , m , a))

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

N, K = map(int,input().split())
p = list(map(int,input().split()))
mx = 0
for i in range(N - K + 1):
    mx = max(mx, sum(p[i:i+K]))
print((K + mx)/2)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
mx,it = sum(p[:K]), sum(p[:K])
for i in range(N - K):
    it = it - p[i] + p[i + K]
    mx = max(mx, it)
print((K + mx)/2)
### BUGGY CODE ###

n, k = map(int, input().split())
p = map(int, input().split())
p_e = list(map(lambda x: (x + 1)* 0.5, p))

max_e = -1
for i in range(n - k + 1):
    v = sum([p_e_j for p_e_j in p_e[i:i+k]])
    if max_e < v:
        max_e = v
print(max_e)

### FIXED CODE ###

n, k = map(int, input().split())
p = map(int, input().split())

p_e = [0] + [ (x + 1) * 0.5 for x in p]
p_p = [0]

for i in range(1, n+1):
    p_p.append(p_p[i-1] + p_e[i])

e_sum = [p_p[i] - p_p[i - k] for i in range(k, n+1)]
print(max(e_sum))