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):
N,M = map(int,input().split())
a_list=[]
pass_1= []
for i in range(M):
    a = list(map(int,input().split()))
    if(a[0]==1):
        pass_1.append(a[1])
    elif(a[1]==N):
        a_list.append(a[0])
    
if list(set(pass_1) & set(a_list)):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

front=[]
back=[]

for i in lst:
    if i[0]==1:
        front.append(i[1])

for i in lst:
    if i[1]==n:
        back.append(i[0])
front=set(front)
back=set(back)
print("POSSIBLE" if len(front&back)>=1 else "IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
route = [[] for _ in range(n)]
check = [0]*n
for _ in range(m):
    a, b = map(int, input().split())
    route[a-1].append(b-1)
pos = [0]
for i in range(2):
    
    tmp = list()
    for p in pos:
        for r in route[p]:
            if r == n-1:
                print('POSSIBLE')
                exit()
            if check[r-1] == 0:
                tmp.append(r)
                check[r-1] == 1
    pos = tmp

print('IMPOSSIBLE')

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

islands1=set() 
islands2=set() 

for i in range(m):
    if a[i]==1:
        islands1.add(b[i])
    
    if b[i]==n:
        islands2.add(a[i])

ans=islands1 & islands2
print("POSSIBLE" if ans else "IMPOSSIBLE")

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy,deepcopy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,M = I()
links = [[] for _ in range(N)]
for i in range(M):
    a,b = I()
    links[a-1].append(b-1)
    links[b-1].append(a-1)
for l1 in links[0]:
    for l2 in links[l1]:
        if l2 == N-1:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
c=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=f()
    c[a]+=[b]
    c[b]+=[a]
print("IMPOSSIBLE" if all(n not in c[i] for i in c[1]) else "POSSIBLE")

Solution (Python):
from collections import deque

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

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

for _ in range(M):
    A,B=map(int,input().split()) 
    graph[A].append(B)
    graph[B].append(A)

dist=[-1]*(N+1) 
dist[0]=0
dist[1]=0

D=deque()
D.append(1)

while D:
    V=D.popleft()
    for i in graph[V]:
        if dist[i]!=-1:
            continue
        dist[i]=dist[V]+1 
        D.append(i)

print(['IMPOSSIBLE','POSSIBLE'][dist[N]==2])

Solution (Python):
n, m = map(int, input().split())
ans = [0]*(n+1)
for _ in [0]*m:
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    if a==1:
        ans[b] += 1
    elif b==n:
        ans[a] += 1
if 2 in set(ans):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

Solution (Python):
import bisect,copy,heapq,itertools,string
from collections import *
from math import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
a = [LIST() for i in range(m)]
c = [0]*(n+1)

for i in range(m):
        if a[i][0] == 1 or a[i][0] == n or a[i][1] == 1 or a[i][1] == n:
                c[a[i][0]] += 1
                c[a[i][1]] += 1

for i in range(2, n):
        if c[i] >= 2:
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

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

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

Solution (Python):
N,M=map(int,input().split())
dp=[0]*(2*(10**5)+1)
bp=[0]*(2*(10**5)+1)
for _ in range(M):
  a,b=map(int,input().split())
  if a==1:
    if bp[b]==1:
      print('POSSIBLE')
      exit()
    dp[b]+=1
  if b==N:
    if dp[a]==1:
      print('POSSIBLE')
      exit()
    bp[a]+=1
print('IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
a_b = [list(map(int,input().split())) for _ in range(m)]
a_b = sorted(a_b,key=lambda x:x[0])

s = set()
for i in range(m):
    if a_b[i][0] == 1:
        s.add(a_b[i][1])
for i in range(m):
    if a_b[i][0] in s:
        if a_b[i][1] == n:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

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

Solution (Python):
n,m=map(int,input().split())
ans=[0]*n
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        ans[b]+=1
    if b==n:
        ans[a]+=1

bl=False
for i in range(n):
    if ans[i]>=2:
        bl=True

if bl:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys
n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]
ln1 = []
ln2 = []
for i in p:
    if i[0] == 1:
        ln1.append(i[1])
for j in p:
    if j[1] == n:
        ln2.append(j[0])

if len(set(ln1) & set(ln2)) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
from collections import defaultdict
n, m = map(int, input().split())
d = defaultdict(list)
for i in range(m):
  a, b = map(int, input().split())
  d[a].append(b)
ans = ''
for mid in d[1]:
  if ans == '':
    for goal in d[mid]:
      if goal == n:
        ans = 'POSSIBLE'
        break
if ans == '':
  ans = 'IMPOSSIBLE'
print(ans)

Solution (Python):
import sys
n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]
ln1 = []
ln2 = []
for i in p:
    if i[0] == 1:
        ln1.append(i[1])
for j in p:
    if j[1] == n:
        ln2.append(j[0])

if len(set(ln1) & set(ln2)) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
n,m = map(int,input().split())
a = []
a_1 = []
a_2 = []
for i in range(m):
    t = list(map(int,input().split()))
    if t[0] == 1:
        a_1.append(t[1])
    if t[1] == n:
        a_2.append(t[0])
    a.append(t)

a = a_1 + a_2
if len(set(a)) < len(a):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import Counter
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]

L.sort(key=lambda x: x[0])

ans = []
for i in range(M):
    if (L[i][0] == 1):
        ans.append(L[i][1])

    if (L[i][1] == N):
        ans.append(L[i][0])

c = Counter(ans)
for i, v in c.items():
    if (v >= 2):
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
N,M = list(map(int,input().split()))
xfrom1 = []
xton =[]
for i in range(M):
    a,b = list(map(int,input().split()))
    if a == 1:
        xfrom1.append(b)
    elif a== N:
        xton.append(b)
    elif b==N:
        xton.append(a)
if len(set(xfrom1) & set(xton)) >0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    G[a].append(b)
    G[b].append(a)


from collections import deque
q = deque([[0, 0]])
visited = [0] * n
visited[0] = 1
while q:
    node, c = q.popleft()
    if c > 2:
        continue
    if node == n-1:
        print('POSSIBLE')
        break

    for to in G[node]:
        if visited[to] == 1:
            continue
        visited[to] = 1
        q.append([to, c+1])
else:
    print('IMPOSSIBLE')

Solution (Python):
import bisect
N, M = map(int, input().split())
start_to_middle = []
middle_to_end = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        start_to_middle.append(b)
    elif b == N:
        middle_to_end.append(a)
if not len(start_to_middle) or not len(middle_to_end):
    print('IMPOSSIBLE')
    exit()
middle_to_end.sort()
for middle in start_to_middle:
    idx = bisect.bisect_left(middle_to_end, middle)
    if idx < len(middle_to_end) and middle_to_end[idx] == middle:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

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

Solution (Python):
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
start = []
goal = []
for a,b in ab:
    if a == 1: start.append(b)
    elif b == n: goal.append(a)
print("POSSIBLE" if list(set(start) & set(goal)) else "IMPOSSIBLE")

Solution (Python):
import heapq
INFTY = 10**6
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
dist = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
heap = [(0,1)]
dist[1] = 0
hist[1] = 1
while heap:
    d,x = heapq.heappop(heap)
    if dist[x]<d:continue
    hist[x]=1
    for y in G[x]:
        if hist[y]==0 and dist[y]>d+1:
            dist[y] = d+1
            heapq.heappush(heap,(d+1,y))
if dist[N]==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

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

if set(ships[0]) & set(ships[-1]) == set():
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations,accumulate 

from collections import deque,defaultdict,Counter
import decimal











import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m = readInts()
A = set()
B = set()
for i in range(m):
    a,b = readInts()
    if a == 1:
        A.add(b)
    if b == n:
        B.add(a)
print('POSSIBLE' if A&B else 'IMPOSSIBLE')

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N, M = inm()


def solve():
    s1 = set()
    sn = set()
    for i in range(M):
        a, b = inm()
        if a == 1:
            s1.add(b)
        if b == 1:
            s1.add(a)
        if a == N:
            sn.add(b)
        if b == N:
            sn.add(a)
    return bool(s1 & sn)


print("POSSIBLE" if solve() else "IMPOSSIBLE")

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


road = [0]*N

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

    if a == 1:
        road[b-1] += 1
    elif b == N:
        road[a-1] += 1

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

Solution (Python):
n, m = map(int, input().split())
S = set()
for i in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    S.add((a, b))

for i in range(1, n-1):
    if (0, i) in S and (i, n-1) in S:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
a=[0]*(n+1)
b=[0]*(n+1)
for i in range(m):
  x,y=map(int,input().split())
  if x==1:
    a[y]=1
  if y==n:
    b[x]=1
ans=0
for i in range(n+1):
  ans+=a[i]*b[i]
if ans==0:
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Solution (Python):
N_shima, M_fune = map(int, input().split())

shima_1 = []
shima_N = []

for i in range(M_fune):
    a, b = map(int, input().split())

    if (a == 1):
        shima_1.append(b)
    elif (a == N_shima):
        shima_N.append(b)
    if (b == 1):
        shima_1.append(a)
    elif (b == N_shima):
        shima_N.append(a)
    
judge = set(shima_1) & set(shima_N)

if (len(judge) >= 1):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


from collections import defaultdict
N, M = ints()

graph = defaultdict(lambda: [])
for _ in ra(M):
    a, b = mina(*ints())
    graph[a].append(b)
    graph[b].append(a)


def dfs(now, fr, d):
    if d == 2:
        return now == N - 1
    res = False
    for to in graph[now]:
        if fr == to:
            continue
        res = res or dfs(to, now, d + 1)
    return res


print('POSSIBLE' if dfs(0, -1, 0) else 'IMPOSSIBLE')

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

dic = {1:set(), N:set()}

for _ in range(M):
  a,b = map(int, input().split())
  if a == 1:
    dic[1].add(b)
  elif b == N:
    dic[N].add(a)

for i in dic[1]:
  if i in dic[N]:
    print("POSSIBLE")
    exit()
    
print("IMPOSSIBLE")

Solution (Python):
import queue
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

def main():
    N,M = [int(x) for x in input().split()]
    C = defaultdict(list)
    for _ in range(M):
        a,b = [int(x) for x in input().split()]
        C[a-1].append(b-1)
    
    
    q = queue.Queue()
    
    V = [0]*N
    V[0] = 0
    
    s = 0
    while True:
        
        for u in C[s]:
            
            if V[u] == 0:
                q.put(u)
                V[u] = V[s]+1 
        if q.empty() or V[N-1] > 0:
            break
        s = q.get()
    
    
    if 0 < V[N-1] and V[N-1] <= 2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
        
if __name__ == '__main__':
    main()

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


def binary_search(num_list, target):
    
    ans_counter = 0
    while True:
        
        middle = num_list[len(num_list) // 2]
        
        left = num_list[:len(num_list) // 2]
        
        right = num_list[len(num_list) // 2:]
        
        if middle == target:
            ans_counter += len(left) + 1
            print("{}は{}番目にありました。".format(target, ans_counter))
            break
        
        
        elif len(num_list) == 1 and num_list[0] != target\
                or left[-1] < target < right[0]:
            print("{}はありませんでした。".format(target))
            break
        
        elif target <= left[-1]:
            num_list = left
        
        elif right[0] < target:
            ans_counter += len(left)
            num_list = right


first_hune = [False for _ in range(n + 1)]
second_hune = [False for _ in range(n + 1)]

AB.sort(key=lambda x: [x[0], x[1]])
totyu = []
for a, b in AB:
    if a == 1:
        first_hune[b] = True
    if b == n:
        if first_hune[a] is True:
            print('POSSIBLE')
            exit()


print('IMPOSSIBLE')

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

near = [set([]) for _ in range(n)]
for a, b in ab:
    near[a - 1].add(b - 1)
    near[b - 1].add(a - 1)

for i in near[0]:
    if i in near[n - 1]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

dic={}

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

for i in range(m):
    a,b=ab[i]
    if a==1:
        dic[b]=1


for i in range(m):
    a,b=ab[i]
    if b==n and a in dic:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

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


def bfs(v):
   dist = [-1] * n
   dist[v] = 0
   visit = [v]
   c = 1
   while visit:
      next = []
      for i in visit:
         for j in edges[i]:
            if dist[j] == -1:
               dist[j] = c
               next.append(j)
      visit = next
      c += 1
      if c > 2:
         break

   return dist

dist = bfs(0)
if dist[-1] == -1:
   print('IMPOSSIBLE')
else:
   print('POSSIBLE')

Solution (Python):
n, m = map(int, input().split())
dic = {}
for i in range(m):
  a, b = map(int, input().split())
  if a in dic:
    dic[a].append(b)
  else:
    dic[a] = [b]
  if b in dic:
    dic[b].append(a)
  else:
    dic[b] = [a]

res = []
for elem in dic[1]:
  res += dic[elem]
if n in res:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
W = V[1]
z = []
for x in W:
    z.append(V[x])
s = 0
for q in z:
    if n in q:
        s = 1
        break
if s == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys
buf = sys.stdin.buffer

n, m = map(int, buf.readline().split())
AB = map(int, buf.read().split())

reachable_from_start = set()
reachable_to_goal = set()
for a, b in zip(AB,AB):
    if a == 1:
        reachable_from_start.add(b)
    if b == n:
        reachable_to_goal.add(a)

possible = reachable_from_start & reachable_to_goal
if possible or n in reachable_from_start:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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


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

edges = [set() for _ in range(n)]
for _ in range(m):
    _from, to = map(int, input().split())
    edges[_from-1].add(to-1)

first = list(edges[0])

possible = False
while first:
    island = first.pop()
    if n-1 in edges[island]:
        possible = True
        break

if possible:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE ")

Solution (Python):
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n, m = LI()
a = []
b = []
for _ in range(m):
    ai, bi = LI()
    a.append(ai)
    b.append(bi)

b1 = set(bi for ai, bi in zip(a, b) if ai == 1)
an = set(ai for ai, bi in zip(a, b) if bi == n)

s = b1 & an
ans = 'POSSIBLE' if len(s) > 0 else 'IMPOSSIBLE'
print(ans)

Solution (Python):
import sys
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(m)]
b=set()
c=set()
for l in a:
  if l[0]==1:
    b.add(l[1])
  elif l[1]==n:
    c.add(l[0])
for x in b:
  if x in c:
    print("POSSIBLE")
    sys.exit()
print("IMPOSSIBLE")

Solution (Python):
N, M=map(int, input().split())
from1=set([])
fromN=set([])

for _ in range(M):
  a, b=map(int, input().split())
  if a==1:
    from1.add(b)
  if b==N:
    fromN.add(a)
while from1:
  if from1.pop() in fromN:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Solution (Python):
import sys
N, M = map(int, input().split())
route = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    route[a-1].append(b)
    
for i in route[0]:
    if len(route) != 1:
        for j in route[i-1]:
            if j == N:
                print('POSSIBLE')
                sys.exit()
    else:
        if i == N:
            print('POSSIBLE')
            sys.exit()
                
print('IMPOSSIBLE')

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

a = [0]*N
b = [0]*N

for i in range(M):
    if ll[i][0] == 1:
        a[ll[i][1]-1] += 1
    if ll[i][1] == N:
        b[ll[i][0]-1] += 1

for i in range(N):
    if a[i] != 0 and b[i] != 0:
        print("POSSIBLE")
        exit()
    else:
        pass
print("IMPOSSIBLE")

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

l1=[0]*n
ln=[0]*n
for i in range(m):
    if ab[i][0]==1:
        l1[ab[i][1]-1]+=1
    if ab[i][1]==n:
        ln[ab[i][0]-1]+=1
    
for i in range(n):
    if l1[i]!=0 and ln[i]!=0:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
from collections import deque
import sys

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

G = [deque([]) for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

time = 0

for i in range(len(G[0])):
    if (N-1) in G[G[0][i]]:
        print('POSSIBLE')
        sys.exit()

print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
f=set([ft[1] for ft in ab if ft[0]==1])
t=set([ft[0] for ft in ab if ft[1]==n])
if f&t: print("POSSIBLE")
else: print("IMPOSSIBLE")

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

if len(A[0])+len(A[-1]) != len(set(A[0]+A[-1])):
        print("POSSIBLE")
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque
    n, m = map(int, readline().split())
    edge = defaultdict(set)

    for _ in range(m):
        a, b = map(int, readline().split())
        edge[a].add(b)
        edge[b].add(a)

    for u in edge[1]:
        if n in edge[u]:
            print("POSSIBLE")
            sys.exit()

    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
graph = {i:[] for i in range(n)}
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for dst in graph[0]:
    if n-1 in graph[dst]:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
li=[[] for _ in range(n)]
for i in range(m):
  x,y=map(int,input().split())
  li[x-1].append(y-1)
  li[y-1].append(x-1)
an=[]
for i in li[0]:
  an+=li[i]
if n-1 in an:
  print('POSSIBLE')
else:print('IMPOSSIBLE')

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

for v in G[0]:
  if N-1 in G[v]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

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

for v in G[0]:
  for nv in G[v]:
    if nv == N-1:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

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

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

for first in g[0]:
    if n-1 in g[first]:
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
A = []
B = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    A.append(b)
  if b == N:
    B.append(a)
C = list(set(A) & set(B))
ans = 'IMPOSSIBLE'
if len(C) > 0:
  ans = 'POSSIBLE'
print(ans)

Solution (Python):
n, m = map(int, input().split())
f = {}
s = {}


for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        f[b] = 1
        if b in s:
            print("POSSIBLE")
            exit()
    if b == n:
        s[a] = 1
        if a in f:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
f = [0]*200020
s = [0]*200020


for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        f[max(a, b)] = 1
        if s[max(a, b)] == 1:
            print("POSSIBLE")
            exit()
    if a == n or b == n:
        s[min(a, b)] = 1
        if f[min(a, b)] == 1:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

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

for m in range(M):
    a,b = map(int,input().split())
    if a==1:
      x.add(b)
    if b==N:
      y.add(a)

if x&y:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

l = list()
la = [0] * (n+1)
ln = [0] * (n+1)

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        la[b] = 1
    elif b == 1:
        la[a] = 1
    if a == n:
        ln[b] = 1
    elif b == n:
        ln[a] = 1

for i in range(n+1):
    if la[i]*ln[i] == 1:
        print("POSSIBLE") 
        exit()

print("IMPOSSIBLE")

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

l = list()
la = [0] * (n+1)
ln = [0] * (n+1)

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        la[b] = 1
    elif b == 1:
        la[a] = 1
    if a == n:
        ln[b] = 1
    elif b == n:
        ln[a] = 1

for i in range(n+1):
    if la[i]*ln[i] == 1:
        print("POSSIBLE") 
        exit()

print("IMPOSSIBLE")

Solution (Python):
import heapq

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

roots = [[] for _ in range(n)]

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

def dijkstra(edges, s):
    hq = []
    d = [-1] * n
    d[s] = 0
    heapq.heappush(hq, (0, s))
    while hq:
        d1, p = heapq.heappop(hq)
        for i in edges[p]:
            if d[i] == -1 or d[i] > d1 + 1:
                d[i] = d1 + 1
                heapq.heappush(hq, (d1+1, i))
    return d

d = dijkstra(roots, 0)

if d[-1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

li1 = [False] * n
lin = [False] * n

for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        li1[b-1] = True
    elif b == n:
        lin[a-1] = True

for i in range(n):
    if li1[i] and lin[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

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

li1 = []
lin = []

for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        li1.append(b)
    elif b == n:
        lin.append(a)

li1.sort()
lin.sort()

tmp = 0

if not len(lin):
    print('IMPOSSIBLE')
    exit()

for i in li1:
    while i > lin[tmp]:
        tmp += 1
        if tmp == len(lin):
            print('IMPOSSIBLE')
            exit()
    if i == lin[tmp]:
        print('POSSIBLE')
        exit()


print('IMPOSSIBLE')

Solution (Python):
from collections import deque

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


S = [[]for i in range(N+1)]
deq=deque()

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

lenN=len(S[N])
for i in range(lenN):
    v=S[N][i]
    
    
    
    if 1 in S[v]: 
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
from collections import deque

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


S = [[]for i in range(N+1)]
deq=deque()

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

lenN=len(S[N])
for i in range(lenN):
    v=S[N][i]
    
    
    
    if 1 in S[v]: 
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
A, B = [0]*n, [0]*n
ans = 'IMPOSSIBLE'
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        A[b-1] += 1
    if b == n:
        B[a-1] += 1
if sum(B) == 0:
    print(ans)
    exit()
else:
    for i in range(n):
        if A[i] == 1 and B[i] == 1:
            ans = 'POSSIBLE'
            break
    print(ans)

Solution (Python):
import sys
n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = []
new = []
for i in range(m):
    if ls[i][0] == 1:
        di.append(ls[i][1])
    if ls[i][1] == n:
        new.append(ls[i][0])
f = list(set(di) & set(new))
if len(f) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

l = [[] for _ in range(n+1)]

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

if len(l[n]):
    for x in l[n]:
        if l[x].count(0):
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Solution (Python):
from collections import deque
n,m = map(int,input().split())

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

q = deque()
q.append((0,0))
while q:
    now,cnt = q.popleft()
    if now==n-1 and cnt==2:
        print('POSSIBLE')
        exit()
    if cnt>=2:
        continue
    for index in Map[now]:
        q.append((index,cnt+1))
print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
AB=[[] for i in range(N)]
for j in range(M):
    a,b=map(int,input().split())
    AB[a-1].append(b)
    AB[b-1].append(a)
for ab in AB:
    if 1 in ab and N in ab:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")