Problem:
 Score : 300 points    Problem Statement In Takahashi Kingdom, there is an archipelago of N islands, called Takahashi Islands.
For convenience, we will call them Island 1 , Island 2 , ..., Island N .  There are M kinds of regular boat services between these islands.
Each service connects two islands. The i -th service connects Island a_i and Island b_i .  Cat Snuke is on Island 1 now, and wants to go to Island N .
However, it turned out that there is no boat service from Island 1 to Island N , so he wants to know whether it is possible to go to Island N by using two boat services.  Help him.      Constraints  3 ≤ N ≤ 200  000  1 ≤ M ≤ 200  000  1 ≤ a_i < b_i ≤ N  (a_i, b_i) \neq (1, N)  If i \neq j , (a_i, b_i) \neq (a_j, b_j) .         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2 : a_M  b_M       Output If it is possible to go to Island N by using two boat services, print POSSIBLE ; otherwise, print IMPOSSIBLE .        Sample Input 1 3 2
1 2
2 3      Sample Output 1 POSSIBLE       Sample Input 2 4 3
1 2
2 3
3 4      Sample Output 2 IMPOSSIBLE  You have to use three boat services to get to Island 4 .       Sample Input 3 100000 1
1 99999      Sample Output 3 IMPOSSIBLE       Sample Input 4 5 5
1 3
4 5
2 3
2 4
1 4      Sample Output 4 POSSIBLE  You can get to Island 5 by using two boat services: Island 1 -> Island 4 -> Island 5 .

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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

N, M = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

que = deque()
que.append((1, 0))
ok = False
seen = [[False] * (N + 1), [False] * (N + 1)]
while que:
    v, d = que.popleft()
    if v == N and d == 2:
        ok = True
        break
    if d >= 2:
        continue
    for u in graph[v]:
        if not seen[d][u]:
            seen[d][u] = True
            que.append((u, d + 1))
if ok:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
from heapq import heappush, heappop
def dijkstra(graph: list, node: int, start: int) -> list:
    
    inf = float('inf')
    dist = [inf] * node

    dist[start] = 0
    heap = [(0, start)]
    while heap:
        cost, thisNode = heappop(heap)
        for NextCost, NextNode in graph[thisNode]:
            dist_cand = dist[thisNode] + NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode], NextNode))
    return dist
    

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

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

dist = dijkstra(edge, n, 0)
if dist[n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
seta = set()
setb = set()
for i in range(M):
    a, b, =map(int, input().split())
    if a == 1: setb.add(b)
    if b == N: seta.add(a)
if len(seta&setb) == 0: print("IMPOSSIBLE")
else:   print("POSSIBLE")

Solution (Python):
n,m = map(int,input().split())
ll = [list(map(int,input().split())) for _ in [0]*m]
to=set()
nfrom=set()
for l in ll:
  if l[0]==1:
    to.add(l[1])
  if l[1]==n:
    nfrom.add(l[0])
if len(to&nfrom)>0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
ab = [(lambda x, y:(x, y))(*map(int, input().split())) for _ in range(m)]
d = {}
for x in ab:
  if x[0] in d.keys():
    d[x[0]].append(x[1])
  else:
    d[x[0]] = [x[1]]
moyo = []
for z in d[1]:
  if z in d.keys():
    moyo += d[z]
for z in moyo:
  if z == n:
    exit(print('POSSIBLE'))
print('IMPOSSIBLE')

Solution (Python):

n, m = [int(x) for x in input().split()]
transitions = [list(map(int,input().split())) for _ in range(m)]
one_roots = set()
second_roots = set()
for transition in transitions:
    if transition[0] == 1:
        one_roots.add(transition[1])
    if transition[1] == n:
        second_roots.add(transition[0])

print('POSSIBLE' if len(one_roots.intersection(second_roots)) > 0 else 'IMPOSSIBLE')

Solution (Python):
from collections import deque


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



from collections import deque


def dfs(path, start):
    que = deque([(start, 0)])
    dist = [float('inf')] * n
    while que:
        cur, c = que.popleft()
        c += 1
        for nxt in path[cur]:
            if c < dist[nxt]:
                dist[nxt] = c
                que.append((nxt, c))
    return dist



dist = dfs(path, 0)
if dist[-1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())

A = []
for i in range(M):
  A.append(list(map(int, input().split())))

D1 = set(A[i][1] for i in range(M) if A[i][0] == 1)
D2 = set(A[i][0] for i in range(M) if A[i][1] == N)

if len(D1 & D2) != 0:
  print ("POSSIBLE")
else:
  print ("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
l1 = [0]*n
l2 = [0]*n

for i in range(m):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  if a == 0:
    l1[b] = 1
  elif b == n-1:
    l2[a] = 1
  else:
    continue

for j in range(n):
  if l1[j] == 1 and l2[j] == 1:
    print('POSSIBLE')
    exit()
else:
  print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
g = [[] for _ in range(n)]

for i in range(m):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].append(b)
  g[b].append(a)
  
from collections import deque
queue = deque([])
queue.append(0)

visited = [-1]*n
visited[0] = 0

while queue:
  x = queue.popleft()
  for new_x in g[x]:
    if visited[new_x] == -1:
      if new_x == n-1 and visited[x]+1 == 2:
        print('POSSIBLE')
        exit()
      else:
        visited[new_x] = visited[x]+1
        queue.append(new_x)
    else:
      continue
print('IMPOSSIBLE')

Solution (Python):
import heapq
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
ls = []
heapq.heapify(ls)
for i in range(m):
    if ab[i][0] == 1:
        heapq.heappush(ls, ab[i][1])
    else:
        while True:
            if len(ls) != 0:
                p = heapq.heappop(ls)
                if p == ab[i][0]:
                    if ab[i][1] == n:
                        print("POSSIBLE")
                        exit()
                    else:
                        heapq.heappush(ls, p)
                        break
                elif p > ab[i][0]:
                    heapq.heappush(ls, p)
                    break
            else:
                print("IMPOSSIBLE")
                exit()
print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict
N,M=map(int,input().split())
B=[list(map(int,input().split())) for _ in range(M)]
dic=defaultdict(list)
ans="IMPOSSIBLE"
for i,j in B:
  dic[i].append(j)
O=dic.get(1)
if N in O:
    ans="POSSIBLE"
for o in O:
  T=dic.get(o)
  try:
    if N in T:
      ans="POSSIBLE"
  except:
    pass
print(ans)

Solution (Python):
from collections import deque

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

edges = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

def dfs(start, end):
    minDist = [-1 for _ in range(N)]
    minDist[start] = 0

    que = deque([])
    que.append((start, 0))

    while que:
        now, dist = que.popleft()

        minDist[now] = dist
        if now == end:
            return dist

        for to in edges[now]:
            if minDist[to] >= 0:
                continue
            que.append((to, dist + 1))

    return float('inf')

if dfs(0, N - 1) <= 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = map(int,input().split())
n1 = set()
ans = "IMPOSSIBLE"
for i in range(m):
    a,b = map(int,input().split())
    if a == 1 or a == n:
        if b in n1:
            ans = "POSSIBLE"
        else:
            n1.add(b)
    elif b == 1 or b == n:
        if a in n1:
            ans = "POSSIBLE"
        else:
            n1.add(a)
print(ans)

Solution (Python):
n, m = map(int, input().split())
sa = set()
sb = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        sb.add(b)
    if b == n:
        sa.add(a)

print('POSSIBLE' if len(sa&sb) != 0 else 'IMPOSSIBLE')

Solution (Python):

import sys




class UnionFind:
    def __init__(self, n):
        
        self.par = [-1] * (n+1)
        
        self.rank = [0] * (n+1)
    
    
    def size(self, x):
        return -1*self.par[self.find(x)]
    
    def size_list(self):
        return [x*(-1) for x in self.par[1:] if x < 0]

    
    def find(self, x):
        
        if(self.par[x] < 1):
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        
        x = self.find(x)
        y = self.find(y)

        
        if(x == y):
            return False

        
        if(self.size(x) < self.size(y)):
            x,y = y,x
        
        
        self.par[x] += self.par[y]
        
        self.par[y] = x

        return True 


YES = "POSSIBLE"  
NO = "IMPOSSIBLE"  

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    ab = sorted([[a[i], b[i]] for i in range(M)], key=lambda x:(x[0], x[1]))

    p1 = []

    for i,j in ab:
        if(i == 1):
            p1.append(j)
        else:
            break
    
    p1 = set(p1)

    for i,j in ab:
        if(i in p1 and j == N):
            print(YES)
            exit()

    print(NO)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
b1 = [False for i in range(n)]
bn = [False for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    if a == 0:
        b1[b] = True
    if b == n - 1:
        bn[a] = True
for i in range(n):
    if b1[i] and bn[i]:
        print("POSSIBLE")
        import sys
        sys.exit()
print("IMPOSSIBLE")

Solution (Python):

import sys
INF = float("inf")


def yes():
    print("POSSIBLE")  


def no():
    print("IMPOSSIBLE")  


import heapq
INF = float("inf")



class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    g = Graph(N)
    for aa, bb in zip(a, b):
        g.add_edge([aa-1, bb-1, 1])

    dist, prev = shortestPath(g, 0)
    if dist[N-1] <= 2:
        yes()
    else:
        no()
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
a=set()
b=set()
for i in range(m):
	x,y=map(int,input().split())
	if x==1:
		b.add(y)
	if y==n:
		a.add(x)
c=a&b
if len(c)==0:
	print("IMPOSSIBLE")
else:
	print("POSSIBLE")

Solution (Python):
n,m = map(int,input().split())
a1 = set()
an = set()
for i in range(m):
  now = list(map(int,input().split()))
  if now[0] == 1:
    a1.add(now[1])
  elif now[0] == n:
    an.add(now[1])
  elif now[1] == 1:
    a1.add(now[0])
  elif now[1] == n:
    an.add(now[0])
a = a1 & an
if len(a) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
s=set([])
g=set([])
for i in range(M):
    a,b=map(int,input().split())
    if a==1:s.add(b)
    if b==N:g.add(a)
print(["IMPOSSIBLE","POSSIBLE"][len(s&g)>0])

Solution (Python):
n, m = list(map(int, input().split()))
a = [list(map(int, input().split())) for i in range(m)]

ans = []
flag = False

for i in range(m):
    if 1 in a[i]:
        ans.append(a[i][1])
    if n in a[i]:
        ans.append(a[i][0])

if len(set(ans)) != len(ans):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import deque
N, M = map(int, input().split())
lst = [[] for _ in range(N + 1)]
dist = [float("inf")]*(N+1)
dist[1] = 0
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)

q = deque()
q.append(1)

while q:
    now = q.popleft()

    for itm in lst[now]:
        if dist[itm] > dist[now]:
            q.append(itm)
            dist[itm] = dist[now] + 1
print("POSSIBLE") if dist[N] <= 2 else print("IMPOSSIBLE")

Solution (Python):
from collections import deque
N, M = map(int, input().split())
lst = [[] for _ in range(N + 1)]
dist = [float("inf")]*(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)

q = deque()
d = 0
q.append([1,d])

while q:
    now, d = q.popleft()
    dist[now] = d

    for itm in lst[now]:
        if dist[itm] > d+1:
            q.append([itm,d+1])
            
print("POSSIBLE") if dist[N] <= 2 else print("IMPOSSIBLE")

Solution (Python):
from collections import deque
N, M = map(int, input().split())
lst = [[] for _ in range(N + 1)]
dist = [float("inf")]*(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    lst[a].append(b)
    lst[b].append(a)

q = deque()
d = 0
q.append([1,d])

while q:
    now, d = q.popleft()
    dist[now] = d
    if now == N:
        if d <= 2:
            print("POSSIBLE")
        else:
            print("IMPOSSIBLE")
        exit()
    
    for itm in lst[now]:
        if dist[itm] > d+1:
            q.append([itm,d+1])
            
print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())

l = [[] for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    l[a].append(b)
    l[b].append(a)
ans = 'IMPOSSIBLE'
for i in l[0]:
    for j in l[i]:
        if j == N-1:
            ans = 'POSSIBLE'
            break
print(ans)

Solution (Python):
n,m = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(m)]


dst1 = []
dst2 = []

for i in range(m):
    if lst[i][0] == 1:
        dst1.append(lst[i][1])
    elif lst[i][1] == n:
        dst2.append(lst[i][0])

if (set(dst1) & set(dst2)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
s = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    s[a].append(b)

for i in s[1]:
    if N in s[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
s = [[] for i in range(N+1)]
e = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    s[a].append(b)
    e[b].append(a)

for i in s[1]:
    if N in s[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):

import sys, math, fractions, itertools, bisect

YES = "POSSIBLE"  
NO = "IMPOSSIBLE"  

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    G = [[] for _ in range(N)]
    for i in range(M):
        G[a[i]-1].append(b[i]-1)
        G[b[i]-1].append(a[i]-1)
    G[0].sort()
    G[-1].sort()
    flag = False
    for g in G[0]:
        i = bisect.bisect_left(G[-1], g)
        if 0 <= i <= len(G[-1])-1:
            if G[-1][i] == g:
                flag = True
    if flag:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Solution (Python):

n,m = list(map(int,input().split()))
d = [list(map(int,input().split())) for i in range(m)]

from_one_to = []

to_n_from = []
for i,j in d:
    if i==1:
        from_one_to.append(j)
    if j==n:
        to_n_from.append(i)
if len(set(from_one_to) & set(to_n_from)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):


input=open(0).readline

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


for e in edge[-1]:
    if 0 in edge[e]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):


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


for e in edge[-1]:
    if 0 in edge[e]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):
N, M = [int(x) for x in input().split()]
E = [[] for x in range(N+1)]
visited = set()

for i in range(M):
    A, B = [int(x) for x in input().split()]
    E[A].append(B)
    E[B].append(A)

if set(E[1]) & set(E[N]):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())

sa=set()
sb=set()

for i in range(m):
    a,b=map(int,input().split())
    if a==1:sb.add(b)
    if b==n:sa.add(a)

print('IMPOSSIBLE' if len(sa&sb)==0 else 'POSSIBLE')

Solution (Python):
N, M = map(int, input().split())
cnt = [0]*N
for i in range(M):
    A, B = map(int, input().split())
    if A == 1:
        cnt[B] += 1
    elif B == N:
        cnt[A] += 1

if 2 in cnt:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
a = [0] * M
b = [0] * M
for i in range(M):
    a[i], b[i] = map(int, input().split())

check = [[] for _ in range(N+1)]

for i in range(M):
    check[a[i]].append(b[i])
    check[b[i]].append(a[i])


a = 0

for i in range(N+1):
    if 1 in check[i] and N in check[i]:
        print('POSSIBLE')
        a = 1
        break

if a == 0:
    print('IMPOSSIBLE')

Solution (Python):


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)

Solution (Python):
N, M = map(int, input().split())
ships = [[] for _ in range(2*10**5+1)]
for _ in range(M):
  _from, _to = map(int, input().split())
  ships[_from].append(_to)
for _to in ships[1]:
  if N in ships[_to]:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math
import itertools
 




 
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    g = Graph()
    
    for i in range(M):
        a,b = inputMap()
        g.add_edge(a-1, b-1, 1)
        g.add_edge(b-1, a-1, 1)
        
    d = Dijkstra(g, 0)
    tmp = d.shortest_distance(N-1)
    
    if tmp <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
        
        
    
class Graph(object):
    
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    
    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        
        return self.dist[goal]

    def shortest_path(self, goal):
        
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
        
if __name__ == "__main__":
	main()

Solution (Python):
N, M = map(int, input().split())
cnt = [0 for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cnt[b] += 1
    elif b == N:
        cnt[a] += 1
if 2 in cnt:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
a=[]
b=[]
for _ in [0]*m:
    l=list(map(int,input().split()))
    if l[0]==1:a.append(l[1])
    if l[1]==n:b.append(l[0])
print('POSSIBLE' if set(a)&set(b) else 'IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

ans = 'IMPOSSIBLE'
qs = [0]
for _ in range(2):
    qqs = []
    for q in qs:
        for n in graph[q]:
            if n == N-1:
                ans = 'POSSIBLE'
                break
            qqs.append(n)
    qs = qqs

print(ans)

Solution (Python):
n, m = map(int, input().split())
route = {i + 1 : [] for i in range(n)}
for i in range(m):
    a, b = map(int, input().split())
    route[a].append(b)
    route[b].append(a)
if set(route[1]) & set(route[n]):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
def main():
    N, M = map(int, input().split())

    
    s = []

    
    g = []

    for i in range(M):
        a,b = map(int, input().split())
        if a == 1:
            s.append(b)
        if b == 1:
            s.append(a)
        if a == N:
            g.append(b)
        if b == N:
            g.append(a)

    s = set(s)
    g = set(g)

    for i in s:
        if i in g:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

main()

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
ship = [[] for i in range(N)]
for i in range(M):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  ship[a].append(b)
visited = []
for i in ship[0]:
  visited.append(i)
  for j in ship[i]:
    visited.append(j)

if N-1 in visited:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007


def A():
    n = II()
    print("ABC"+str(n))
    return


def B():
    ni = [2 ** i for i in range(1, 10)]
    n = II()
    ans = 1
    for i in range(1, n + 1):
        if i in ni:
            ans = i
    print(ans)        
    return


def C():
    n, m = LI()
    edg = [[] for i in range(n)]
    for _ in range(m):
        a, b = LI_()
        edg[a].append(b)
        edg[b].append(a)
    next = []
    for i in edg[0]:
        next.append(i)
    for ne in next:
        for i in edg[ne]:
            if i == n - 1:
                print("POSSIBLE")
                return
    print("IMPOSSIBLE")
    return


def D():
    return


if __name__ == '__main__':
    C()

Solution (Python):
N,M = map(int,input().split())
T = [[]for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    T[a].append(b)
ans = "IMPOSSIBLE"
def f(v,p,n):
    global N,T,ans
    if n>2: return
    if n==2 and v==N: ans="POSSIBLE"
    for c in T[v]:
        if c!=p: f(c,v,n+1)
f(1,0,0)
print(ans)

Solution (Python):



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

s = [0]*(200000+1)
g = [0]*(200000+1)
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s[b] += 1
    if b == n:
        g[a] += 1
f = 0
for i in range(200000+1):
    if s[i] & g[i]:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):



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

s = [0]*(200000+1)
g = [0]*(200000+1)
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s[b] += 1
    if b == n:
        g[a] += 1
f = 0
for i in range(200000+1):
    if s[i] & g[i]:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
ship = [list(map(int, input().split())) for i in range(M)]


goal_ship = set()
transit = set()

for i in ship:
    if i[1] == N:
        goal_ship.add(i[0])
for i in ship:
    if i[0] == 1:
        transit.add(i[1])

ans = goal_ship & transit

if len(ans):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
ship = [list(map(int, input().split())) for i in range(M)]


goal_ship = []
transit = []

for i in ship:
    if i[1] == N:
        goal_ship.append(i[0])
for i in ship:
    if i[0] == 1:
        transit.append(i[1])

goal_ship = set(goal_ship)
transit = set(transit)

ans = goal_ship & transit

if len(ans):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())

first = [False for _ in range(N + 1)]
second = [False for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())

    if a == 1:
        first[b] = True
    if b == 1:
        first[a] = True
    if a == N:
        second[b] = True
    if b == N:
        second[a] = True

for f, s in zip(first, second):
    if f and s:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
c=[[]  for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    c[a-1].append(b-1)
    c[b-1].append(a-1)
for d in c:
    if 0 in d and n-1  in d:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]

ninoshima=[[0]*(n+1) for i in range(2)]

for i in range(m):
    if ab[i][0]==1:
        ninoshima[0][ab[i][1]]=1
    if ab[i][1]==n:
        ninoshima[1][ab[i][0]]=1
    

for i in range(n+1):
    if ninoshima[0][i]==ninoshima[1][i]==1:
        print("POSSIBLE")
        quit()

print("IMPOSSIBLE")

Solution (Python):

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)

Solution (Python):
N, M = map(int, input().split())

s = []
e = []
for _ in range(M):
    ab = list(map(int, input().split()))
    if ab[0] == 1:
        s.append(ab[1])
    if ab[1] == N:
        e.append(ab[0])

s = set(s)
e = set(e)

t = s & e

if len(t) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N,M = list(map(int,input().split()))
atob = [0] * N
btoz = [0] * N
for _ in range(M):
    a, b = list(map(int,input().split()))
    if a == 1:atob[b-1] = 1
    elif a == N:btoz[b-1] = 1
    if b == 1:atob[a-1] = 1
    elif b == N:btoz[a-1] = 1

for i in range(N):
    if atob[i]*btoz[i] == 1:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())

graph = [list() for i in range(n+1)]

for i in range(m):
    a, b = map(int, (input().split()))
    graph[a] += [b]
    graph[b] += [a]

for i in graph[1]:
    if n in graph[i]:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
island=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    island[a].append(b)
    island[b].append(a)
for i in range(n+1):
    if 1 in island[i] and n in island[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
def main():
    N, M = map(int, input().split())
    C = [0] * (N + 1)
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            C[b] += 1
        elif b == N:
            C[a] += 1
    if C.count(2) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


main()

Solution (Python):
n,m = map(int,input().split())
if m == 1:
    print("IMPOSSIBLE")
    exit()
a = set()
b = set()
for i in range(m):
    arr = list(map(int,input().split()))
    if 1 in arr:a.add(arr[1])
    if n in arr:b.add(arr[0])
if len(a&b)==0:print("IMPOSSIBLE")
else:print("POSSIBLE")