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())
ship = {i:False for i in range(1, n+1)}
bl = []
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ship[b] = True
    elif b == n:
        bl.append(a)

for i in bl:
    if ship[i] == True:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
ship = {i:[] for i in range(1, n+1)}

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

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

Solution (Python):
n, m = map(int, input().split())
d = {i:[] for i in range(1, n)}
for i in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
ans = "IMPOSSIBLE"
for dd in d[1]:
    if n in d[dd]:
        ans = "POSSIBLE"
        break
print(ans)

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

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

S, G = [False] * N, [False] * N
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    if a == 1:
        S[b - 1] = True
    if b == N:
        G[a - 1] = True

if any(s and g for s, g in zip(S, G)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

S, G = set(), set()
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    if a == 1:
        S.add(b)
    if b == N:
        G.add(a)

if len(S & G) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

S, G = set(), set()
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    if a == 1:
        S.add(b)
    if b == N:
        G.add(a)

if any(s in G for s in S):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

flag = False

for i in range(len(link[0])):
    for j in link[link[0][i]]:
        if j == N-1:
            flag = True

if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M = map(int,input().split())
c1 = [False]*N
c2 = [False]*N
for _ in [0]*M:
    a,b = map(int,input().split())
    if a == 1 : c1[b-1] = True
    if b == N : c2[a-1] = True
for i in range(1,N-1):
    if c1[i] and c2[i]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]

f = set()
s = set()

for a, b in AB:
	if a == 1 or b == 1:
		f |= {a + b - 1}
	if a == N or b == N:
		s |= {a + b - N}
print(["POSSIBLE", "IMPOSSIBLE"][not(f & s)])

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

for i in range(N):
    if a[i] * b[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
from collections import Counter
from functools import reduce

import bisect
import copy
import fractions
import math
import pprint
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    
    x = root(x)
    y = root(y)
    if x == y:
        return
    
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  
        return x
    else:
        node[x] = root(node[x])  
        return node[x]
def dfs(v,depth):
    
    visited[v] = 1
    if depth == 2:
        return
    for a, b in sides:
        if v == a-1:
            depth += 1
            dfs(b-1, depth)
            depth -= 1

n, m = MI()
a, b = set(), set()
for i in range(m):
    x, y = MI()
    if x == 1:
        a.add(y)
    if y == n:
        b.add(x)

print("POSSIBLE" if a&b else "IMPOSSIBLE")

Solution (Python):
from collections import Counter
from functools import reduce

import bisect
import copy
import fractions
import math
import pprint
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))
def unite(x, y):
    
    x = root(x)
    y = root(y)
    if x == y:
        return
    
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  
        return x
    else:
        node[x] = root(node[x])  
        return node[x]
def dfs(v,depth):
    
    visited[v] = 1
    if depth == 2:
        return
    for a, b in sides:
        if v == a-1:
            depth += 1
            dfs(b-1, depth)
            depth -= 1

n, m = MI()
sides = [LI() for _ in range(m)]
islands = [[0] * 2 for _ in range(n)]

for a, b in sides:
    if a-1 == 0:
        islands[b-1][0] = 1
    if b-1 == n-1:
        islands[a-1][1] = 1

for a, b in islands:
    if a == b == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):


def read_input():
    n, m = map(int, input().split())

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

    return n, m, ships


def submit():
    n, m, ships = read_input()

    links = {i: [] for i in range(1, n+1)}

    for ship in ships:
        links[ship[0]].append(ship[1])
        links[ship[1]].append(ship[0])

    set1 = set(links[1])
    set2 = set(links[n])

    if set1.intersection(set2):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')



if __name__ == '__main__':
    submit()

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

S = []
E = []

for i in range(M):
  if ab[i][0] == 1:
    S.append(ab[i][1])
  if ab[i][1] == N:
    E.append(ab[i][0])

if set(S) & set(E):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

N, M = map(int, input().split())
edge1 = []
edgeN = []
for _ in range(M):
    s, n = map(int, input().split())
    if s == 1:
        edge1.append(n)
    elif n == N:
        edgeN.append(s)
if len(set(edge1) & set(edgeN)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
def c_cat_snuke_and_a_voyage(N, M, I):
    node1 = [False] * N  
    node2 = [False] * N  
    for a, b in I:
        if a == 1:  
            node1[b] = True
        elif b == N:  
            node2[a] = True
    return 'POSSIBLE' if any([p and q for p, q in zip(node1, node2)]) else 'IMPOSSIBLE'

N, M = [int(i) for i in input().split()]
I = [[int(i) for i in input().split()] for j in range(M)]
print(c_cat_snuke_and_a_voyage(N, M, I))

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

fr = []
to = []

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

fr.sort()
to.sort()

searched = 0
for i in range(len(fr)):
    while searched <= len(to) - 1 and to[searched] <= fr[i]:
        if to[searched] == fr[i]:
            print('POSSIBLE')
            exit()
        searched += 1


print('IMPOSSIBLE')

Solution (Python):
from sys import exit, stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
s1 = set()
sn = set()
for _ in range(M):
    a,b = [int(_) for _ in stdin.readline().rstrip().split()]
    if a==1:
        s1.add(b)
    elif b==N:
        sn.add(a)
for x in s1:
    if x in sn:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math


N,M = map(int,input().split())
a = []
for i in range(M):
    x,y = map(int,input().split())
    a.append([x,y])

ans = False
routes_s = []
routes_g = []

for ai in range(len(a)):
    if 1 in a[ai]:
        inx = a[ai].index(1)
        routes_s.append(a[ai][inx-1])
    if N in a[ai]:
        inx = a[ai].index(N)
        routes_g.append(a[ai][inx-1])


if 1 in routes_g or N in routes_s:
    print("POSSIBLE")
    exit()

s_reach = list(set(routes_s))
g_reach = list(set(routes_g))
sg_reach = list(set(g_reach+s_reach))

if len(s_reach)+len(g_reach) != len(sg_reach):
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

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

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

flg = 0
for i in voyage[0]:
    if N-1 in voyage[i]:
        flg = 1

print('POSSIBLE' if flg == 1 else 'IMPOSSIBLE')

Solution (Python):
from functools import reduce
from collections import defaultdict
from collections import deque
import math

def btf(i,d,N):
    q = deque()
    q.append(i)
    dist = [-1]*N
    dist[i] = 0
    i = 1
    while q:
        l = len(q)
        for j in range(l):
            next_node = q.popleft()
            for succ in d[next_node]:
                if dist[succ] == -1:
                    dist[succ] = i
                    q.append(succ)
        i +=1
    return dist

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N,M = (int(_) for _ in input().split())
    d = defaultdict(list)
    
    for i in range(M):
        s1,s2 = (int(_) for _ in input().split())
        d[s1-1].append(s2-1)
        d[s2-1].append(s1-1)

    dist = btf(0,d,N)

    if dist[N-1] == 2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
        
if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
l=[[]for i in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  l[a]+=[b]
  l[b]+=[a]
k=0
for i in l[0]:
  if n-1 in l[i]:
    k=1
if k:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):


import itertools
import collections
import bisect

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

    src = {}
    A = []
    B = []
    for _ in range(M):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

        if a == 1:
            src[b] = 1

    for i in range(M):
        if A[i] in src and B[i] == N:
            print("POSSIBLE")
            exit()

    print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
d = {i:[] for i in range(1, n)}
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
ans = "IMPOSSIBLE"
for dd in d[1]:
    if n in d[dd]:
        ans = "POSSIBLE"
        break
print(ans)

Solution (Python):
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
one=[0 for i in range(n)]
ans = "IMPOSSIBLE"
for i in a:
  if i[0] == 1:
    if one[i[1]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[1]] = 1
  elif i[1] == n:
    if one[i[0]] == 1:
      ans = "POSSIBLE"
      break
    else:
      one[i[0]] = 1
print(ans)

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

print("POSSIBLE" if len({b_i for a_i, b_i in zip(a, b) if a_i == 1} & {a_i for a_i, b_i in zip(a, b) if b_i == n}) > 0 else "IMPOSSIBLE")

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

ship = {}

for i in range(m):
  a,b = (map(int, input().split()))
  if a == 1 or b == n:
    if a in ship: 
      ship[a].append(b)
    else:
      ship[a] = [b]

if 1 in ship:
  for i in ship[1]:
    if i in ship and n in ship[i]:
      print("POSSIBLE")
      exit()
      


  
  
print("IMPOSSIBLE")

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

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

a = [list(sorted(map(int, input().split()))) for i in range(m)]
a.sort()

x = 0
li_a = []

while x < m and a[x][0]== 1:
    li_a.append(a[x][1])
    x += 1

a.sort(reverse=True, key=lambda x: x[1])

x = 0
li_b = []

while x < m and a[x][1] == n:
    li_b.append(a[x][0])
    x += 1

print("POSSIBLE" if set(li_a) & set(li_b) else "IMPOSSIBLE")

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

A = [False] * N
B = [False] * N
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A[b-1] = True
    if b == N:
        B[a-1] = True

flag = False
for i in range(N):
    if A[i] and B[i]:
        flag = True
        break

print('POSSIBLE' if flag else 'IMPOSSIBLE')

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
route = defaultdict(lambda: False)
for i in range(M):
    ai, bi = map(int, input().split())
    route[(ai, bi)] = True

possible = False
for i in range(2, N):
    if route[(1, i)] and route[(i, N)]:
        possible = True
print('POSSIBLE' if possible else 'IMPOSSIBLE')

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N,M =LI()
X,Y=[],[]
for i in range(M):
	a = LI()
	if a[0] == 1:
		X.append(a[1])
	if a[1] == N:
		Y.append(a[0])
X=set(X)
Y=set(Y)
for x in X:
	if x in Y:
		print("POSSIBLE")
		exit()
	

	
print("IMPOSSIBLE")

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

Solution (Python):
n,m = map(int,input().split())
adj = [ set() for i in range(n+1) ]
for i in range(m):
    a,b = map(int,input().split())
    adj[a].add(b)
    adj[b].add(a)

x = adj[1].intersection(adj[n])
if len(x) != 0:
    print("POSSIBLE")
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)
  elif b==n:
    B.append(a)
print("POSSIBLE" if len(set(A)&set(B))>0 else "IMPOSSIBLE")

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

for x in s1:
    if x in sn:
        print("POSSIBLE")
        exit(0)
print("IMPOSSIBLE")

Solution (Python):
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
lis = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = nm()
    lis[a].append(b)
    lis[b].append(a)
for i in range(len(lis[1])):
    l = lis[1][i]
    if n in lis[l]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
import sys
fastinput=sys.stdin.readline
N,M=map(int,fastinput().split())
first=[False]*N
second=[False]*N
for _ in range(M):
    i,j=[int(k) for k in fastinput().split()]
    if i==1:
        first[j-1]=True
    if j==N:
        second[i-1]=True
if any([(first[a] and second[a]) for a in range(N)]):
    print("POSSIBLE")
else:print("IMPOSSIBLE")

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

way = [0] * (n + 1)
for a, b in ab:
    if a == 1:
        way[b] += 1
    if b == 1:
        way[a] += 1
    if a == n:
        way[b] += 1
    if b == n:
        way[a] += 1
if 2 in way:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
ships = [list(map(int, input().split())) for _ in range(m)]
starts = list(map(lambda x:x[1], list(filter(lambda x:x[0]==1, ships))))
goals = list(map(lambda x:x[0], list(filter(lambda x:x[1]==n, ships))))
if len(set(starts+goals)) != len(starts+goals):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):

N,M=map(int,input().split())
l=[]
for i in range(M):
    l.append(list(map(int,input().split())))
first=[]
last=[]
H=[[] for i in range(N)]
for t in l:
    H[t[0]-1].append(t[1])
    H[t[1]-1].append(t[0])



if any(N in H[v-1] for v in H[0]):
    
    
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split());a=[]
for i in range(m):
  aa,bb=map(int,input().split())
  if aa==1:a.append(bb)
  if bb==n:a.append(aa)
a.sort()
for i in range(len(a)-1):
  if a[i]==a[i+1]:print("POSSIBLE");exit()
print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict
n, m = map(int, input().split())
bridges = [list(map(int, input().split())) for _ in range(m)]
first_bridge = []
second_bridge = []
bri_dict = defaultdict(list)
for bridge in bridges:
  bri_dict[bridge[0]].append(bridge[1])
  bri_dict[bridge[1]].append(bridge[0])
for bridge in bridges:
  if bridge[1] == n:
    second_bridge.append(bridge[0])

flag = False
for island in second_bridge:
  if 1 in bri_dict[island]:
    flag = True
  
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
l=[tuple(map(int,input().split())) for i in range(m)]
p=[]
q=[]
for i in l:
    if i[0]==1:
        p.append(i[1])
    if i[1]==n:
        q.append(i[0])
if len(set(p)&set(q))!=0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = list(map(int, input().split()))
A = set()
B = set()

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

    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if len(A & B):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

def Dijkstra(N, edges, s):
    from heapq import heappush, heappop, heapify
    dist = [10**18 for _ in range(N)]
    dist[s], h = 0, [[0, s]]
    while (len(h)):
        p = heappop(h)
        d, v = p[0], p[1]
        if d > dist[v]:
            continue
        for i in range(len(edges[v])):
            u = edges[v][i]
            if d + 1 < dist[u]:
                dist[u] = d + 1
                heappush(h, [dist[u], u])
    return dist

N, M = map(int, input().split())
es = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    es[a].append(b)
    es[b].append(a)
dist = Dijkstra(N, es, 0)
if dist[N - 1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

if(M >= 2):
 
 island1 = [0]*N
 
 islandN = [0]*N

 for i in range(M):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  if(a == 0): island1[b] = 1
  if(b == 0): island1[a] = 1 
  if(a == N-1): islandN[b] = 1
  if(b == N-1): islandN[a] = 1
    
 for i in range(len(island1)):
  if((island1[i] == 1)and(islandN[i] == 1)):
    judge = 1
    break
    
if(judge == 0):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Solution (Python):
n,m = map(int,input().split())
dic = {}
for _ in range(m):
    a,b = map(int,input().split())
    if not a in dic.keys():
        dic[a] = [b]
    else:
        dic[a].append(b)
for i in dic[1]:
    if i in dic.keys() and n in dic[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):


import sys
def input():
    return sys.stdin.readline()
n,m=map(int,input().split())
a=[0]*(m+1)
b=[0]*(m+1)
c=[0]*(n+1)
f1=[]
f2=[]
for i in range(m):
    a[i],b[i]=map(int,input().split())
    if a[i]==1:
        c[b[i]]=1

ans='IMPOSSIBLE'
for i in range(m):
    if b[i]==n:
        if c[a[i]]==1:
            ans='POSSIBLE'
print(ans)

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

Solution (Python):
INF = float("inf")


N,M = map(int,input().split())
ab =[list(map(int,input().split())) for i in range(M)]
dist = [INF]*(N)
for i in range(M):
    if ab[i][0] == 1:
        dist[ab[i][1]-1] = 1
for i in range(M):
    if ab[i][1] == N:
        if dist[ab[i][0]-1] <= 1:
            print("POSSIBLE")
            exit()
        else:
            continue
print("IMPOSSIBLE")

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

li_route = list()

for i in range(m):
    li_route.append(list(map(int, input().split())))

starts = set(l[1] for l in li_route if l[0] == 1)

ends = set(l[0] for l in li_route if l[1] == n)

if len(starts.intersection(ends)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        A[a].append(b)
        A[b].append(a)

    q = deque()
    for a in A[1]:
        q.append(a)

    while len(q) > 0:
        a = q.popleft()
        if N in A[a]:
            return 'POSSIBLE'

    return 'IMPOSSIBLE'





if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
n,m=map(int,input().split())
l=[[int(i) for i in l.split()] for l in sys.stdin]
possible=[]
possible2=[]
for i in l:
  if i[0]==1:
    possible.append(i[1])
for i in l:
  if i[1]==n:
    possible2.append(i[0])
if len(set(possible)&set(possible2))>0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, (input().split()))
L1 = [0 for i in range(N)]
L2 = [0 for j in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        L1[b - 1] = 1
    elif b == N:
        L2[a - 1] = 1
for i in range(N):
    if L1[i] == L2[i] == 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
input = open(0).read

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


*abm, = zip(l[::2], l[1::2])


def f(i):
    
    
    return set(abi[i < 2] for abi in abm if i in abi)


def main():
    print("POSSIBLE" if f(1) & f(n) else "IMPOSSIBLE")


main()

Solution (Python):
from sys import stdin

lines = stdin.readlines

l = [[int(i) - 1 for i in line.split()] for line in lines()]

N, M = l[0][0] + 1, l[0][1] + 1


def main():
    f = [False] * N
    t = [False] * N

    for a, b in l[1:]:
        if a == 0:
            f[b] = True
        elif b == N - 1:
            t[a] = True

    for a, b in zip(f, t):
        if a and b:
            print("POSSIBLE")
            return
    else:
        print("IMPOSSIBLE")

    return


main()

Solution (Python):
N, M = list(map(int, input().split()))
A = [0 for i in range(200000+1)]
B = [0 for i in range(200000+1)]
ans = 'IMPOSSIBLE'

for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1:
        A[b] = 1
        if A[b] and B[b]:
            ans = 'POSSIBLE'
            break
    elif b == N:
        B[a] = 1
        if A[a] and B[a]:
            ans = 'POSSIBLE'
            break
print(ans)

Solution (Python):
def cat_snuke_and_a_voyage(N: int, M: int, ships: list)->bool:
    passable = [(False, False)] * (N-2)
    for a, b in ships:
        if a == 1:
            _, bN = passable[b-2]
            passable[b-2] = (True, bN)
            if bN:
                return True
        elif b == N:
            a1, _ = passable[a-2]
            passable[a-2] = (a1, True)
            if a1:
                return True
    return False


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    ships = [tuple(map(int, input().split())) for _ in range(M)]
    yes = cat_snuke_and_a_voyage(N, M, ships)
    print('POSSIBLE' if yes else 'IMPOSSIBLE')

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

set1=set()
setn=set()

for s in S:
  a=min(s)
  b=max(s)
  if a==1 and b==N:
    print('POSSIBLE')
    break
  elif a==1:
    set1.add(b)
  elif b==N:
    setn.add(a)
  else:
    continue
else:
  if (set1 & setn):
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')

Solution (Python):
I=lambda:map(int,input().split())
N,M=I()
d={i+1:0 for i in range(N)}
for _ in[0]*M:
  a,b=I()
  if a in [1,N]:d[b]+=1
  if b in [1,N]:d[a]+=1

for i in range(2,N):
  if d[i]==2:print("POSSIBLE");exit()
print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
x = set()
y = set()
for a, b in L:
    if a == 1:
        x.add(b)
    if b == N:
        y.add(a)
if len(x & y) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict
n, m = map(int, input().split())
l_1 = [False] * n
l_n = [False] * n
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l_1[b] = True
    elif b == n:
        l_n[a] = True
for i in range(n):
    if l_1[i] == True and l_n[i] == True:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
N,M = map(int,input().split())
one = []
nnn = []
for i in range(M):
    ai,bi = map(int,input().split())
    if ai == 1:
        one.append(bi)
    if bi == N:
        nnn.append(ai)
def bs_left(l, target): 
    low, high = 0, len(l)
    while low < high:
        mid = (low+high)//2
        if l[mid] < target:
            low = mid+1
        else:
            high = mid
    if low == len(l):
        return -1
    return low
flag = False
if len(one) == 0 or len(nnn) == 0:
    pass
else:
    nnn.sort()
    for i in range(len(one)):
        if nnn[bs_left(nnn,one[i])] == one[i]:
            flag = True
            break

if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
X=[]
for i in range(m):
    a,b=map(int,input().split())
    X.append([a,b])
    
I=[e for i,e in X if i==1]

E=[i for i,e in X if e==n]



if set(I)&set(E)!=set():
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
d={1:set(),N:set()}
for i in range(M):
    a,b=map(int,input().split())
    if a in d.keys():
        d[a]|={b,}
    if b in d.keys():
        d[b]|={a,}
if len(d[1]&d[N])>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
start=set()
goal=set()
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        start|={b,}
    if a==N:
        goal|={b,}
    if b==1:
        start|={a,}
    if b==N:
        goal|={a,}
if len(start&goal)>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
from sys import exit
N,M = [int(n) for n in input().split()]
Mat = [set() for _ in range(N)]
for i in range(M):
    a,b = [int(n) for n in input().split()]
    Mat[a-1].add(b-1)
    Mat[b-1].add(a-1)
N-=1
for ne in Mat[0]:
    
    if N in Mat[ne]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
island = [[int(_) for _ in input().split()] for _ in range(M)]
set1 = set()
setN = set()
flag = False

for i in island:
    if i[0] == 1:
        set1.add(i[1])
    elif i[1] == N:
        setN.add(i[0])

for i in set1:
    if i in setN:
        flag = True
        break

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

Solution (Python):
N, M = map(int, input().split())
b_1 = []
a_N = []
ab = []
for i in range(M):
    a,b = map(int, input().split())
    if a == 1:
        b_1.append(b)
    if b == N:
        a_N.append(a)
    ab.append((a,b))
    
if len(set(b_1) & set(a_N)) >= 1:
    print('POSSIBLE')
else:
    print("IMPOSSIBLE")