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=[0]*n
B=[0]*n
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

ans="IMPOSSIBLE"
for i in range(n):
    if A[i]==1 and B[i]==1:
        ans="POSSIBLE"
        break
print(ans)

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)

from collections import deque 

def bfs(u, g): 
    u-=1
    queue = deque([u])
    d=[-1]*n
    d[u]=0
    while queue:
        v=queue.popleft()
        for i in g[v]:
            if d[i] is -1:
                d[i]=d[v]+1
                queue.append(i)
    return d

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

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

graph = [[] for _ in range(n)]
for v in ab:
    graph[v[0]-1].append(v[1]-1)
    graph[v[1]-1].append(v[0]-1)


from collections import deque

queue = deque([0])
d = [10**6] * n
d[0] = 0
while queue:
    v = queue.popleft()
    for i in graph[v]:
        if d[i]==10**6:
            d[i] = d[v] + 1
            queue.append(i)


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

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

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

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    input = stdin.buffer.readline
    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)

    q = deque([0])
    seen = [-1] * n
    seen[0] = 0

    while q:
        u = q.popleft()

        for v in g[u]:
            if seen[v] == -1 or seen[v] > seen[u] + 1:
                seen[v] = seen[u] + 1
                q.append(v)

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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


for a,b in AB:
  if a > b:
    a,b = b,a
  
  if a == 1:
    set_a.add(b)
  if b == n:
    set_b.add(a)

se = set_a & set_b
print('POSSIBLE' if se else 'IMPOSSIBLE')

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n+1)]
    for _ in range(m):
        a,b=map(int,readline().split())
        G[a].append(b)
        G[b].append(a)

    s=set(G[1])
    ans=False
    while len(s)>0:
        now=s.pop()
        for nex in G[now]:
            if nex==n:
                ans=True
                break

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

if __name__=="__main__":
    main()

Solution (Python):
from sys import stdin
from collections import deque
def main():
    
    readline=stdin.readline
    n,m=map(int,readline().split())
    G=[[] for _ in range(n+1)]
    for _ in range(m):
        a,b=map(int,readline().split())
        G[a].append(b)
        G[b].append(a)

    
    q=deque([tuple((1,0))])
    flags=[False]*(n+1)
    flags[1]=True
    ans=False
    while len(q)>0:
        now,d=q.popleft()
        if now==n:
            if d==2:
                ans=True
                break
        for nex in G[now]:
            if flags[nex]==False:
                flags[nex]=True
                q.append(tuple((nex,d+1)))

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

if __name__=="__main__":
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    N, M = map(int, input().split()) 
    edge = [[] for i in range(2)] 
    for i in range(M): 
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        if a==0 :
            edge[0].append(b)
        elif b==N-1:
            edge[1].append(a)
    if len(set(edge[0])&set(edge[1]))>=1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

resolve()

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

path = [[] for i in range(n)]

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

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

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

aset = set()
bset = set()

for i in range(M):
  a,b  = map(int,input().split())
  if a == 1:
    aset.add(b)
  elif b == N:
    bset.add(a)

for i in bset:
  if i in aset:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Solution (Python):
def main():
    n, m = map(int,(input().split()))
    inlis = []
    lis_1 = []
    lis_n = []

    for _ in range(m):
        a, b = map(int, input().split())
        
        if a == 1:
            lis_1.append(b)
            
        if b == n:
            lis_n.append(a)
            
    
    set_1 = set(lis_1)
    set_n = set(lis_n)
    
    if set_1 & set_n:
        
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    
if __name__ == "__main__":
    main()

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())
AB = [list(map(int,input().split())) for _ in range(M)]

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

for a,b in AB:
  EDGE[a].append(b)
  EDGE[b].append(a)
  
def dfs(p,u,d):
  if u == N:
    return True
  
  if d == 0:
    return False
  
  ans = False
  
  for v in EDGE[u]:
    if v == u:
      continue
      
    ans |= dfs(u,v,d-1)
  
  return ans

ans = dfs(-1,1,2)

s = 'POSSIBLE' if ans else 'IMPOSSIBLE'

print(s)

Solution (Python):
n, m = [int(i) for i in input().split()]
islands = [set() for i in range(n)]
for i in range(m):
    a, b = [int(i) for i in input().split()]
    islands[a-1].add(b)
    islands[b-1].add(a)
f = False
for i in islands[n-1]:
    if 1 in islands[i-1]: f = True
print("POSSIBLE" if f else "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())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
for i in range(1, n - 1):
    ma = 0
    mi = n
    for node in g[i]:
        ma = max(ma, node)
        mi = min(mi, node)
    if ma == n - 1 and mi == 0:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
islands=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    islands[a].append(b)
answer=1
for n in islands[1]:
    if N in islands[n]:
        answer=0
        print('POSSIBLE')
        break
if answer==1:
    print('IMPOSSIBLE')

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    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)
        G[b].append(a)

    ans = "IMPOSSIBLE"
    for v in G[0]:
        if N - 1 in G[v]:
            ans = "POSSIBLE"
            break

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    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)
        G[b].append(a)

    ans = "IMPOSSIBLE"
    for v in G[0]:
        if N - 1 in G[v]:
            ans = "POSSIBLE"

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
AB = []
import collections
d = collections.defaultdict(list)
for i in range(m):
    a,b = map(int, input().split())
    
    d[a].append(b)
    d[b].append(a)
for k in d.keys():
    if 1 in d[k] and n in d[k]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

adj = [[] for i in range(n)]
dist = [-1]*n
for i in range(m):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
q = deque()
dist[0] = 0
q.append(0)

while len(q) > 0:
    x = q.popleft()
    
    for f in adj[x]:
        if dist[f] != -1:
            continue
        
        dist[f] = dist[x] + 1
        q.append(f)
     
if dist[n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

adj = [[] for i in range(n)]
dist = [-1]*n
for i in range(m):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
q = deque()
dist[0] = 0
q.append(0)

while len(q) > 0:
    x = q.popleft()
    
    for f in adj[x]:
        if dist[f] != -1:
            continue
        
        dist[f] = dist[x] + 1
        q.append(f)
     
if dist[n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

adj = [[] for i in range(n)]
dist = [-1]*n
for i in range(m):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
q = queue.Queue()
dist[0] = 0
q.put(0)

while not q.empty():
    x = q.get()
    
    for f in adj[x]:
        if dist[f] != -1:
            continue
        
        dist[f] = dist[x] + 1
        q.put(f)
     
if dist[n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

adj = [[] for i in range(n)]
dist = [-1]*n
for i in range(m):
    a,b = map(int,input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
q = queue.Queue()
dist[0] = 0
q.put(0)

while not q.empty():
    x = q.get()
    
    for f in adj[x]:
        if dist[f] != -1:
            continue
        
        dist[f] = dist[x] + 1
        q.put(f)
     
if dist[n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

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

if len(arrival&deperture)>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    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)
    for e in G[0]:
        if N-1 in G[e]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

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)
while v[1]:
    temp = v[1].pop()
    if n in v[temp]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
    n, m = nm()
    G = [list() for _ in range(n)]
    for _ in range(m):
        u, v = nm()
        u -= 1; v -= 1
        G[u].append(v)
        G[v].append(u)
    if (set(G[0]) & set(G[n-1])):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')
    return

solve()

Solution (Python):
import collections
import heapq


class Dijkstra():
    def __init__(self):
        self.e = collections.defaultdict(list)

    def add(self, u, v, d, directed=False):
        """
        
        
        
        """
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def Dijkstra_search(self, s):
        """
        
        
        
        """
        d = collections.defaultdict(lambda: float('inf'))
        prev = collections.defaultdict(lambda: None)
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = collections.defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            v[u] = True

            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    prev[uv] = u
                    heapq.heappush(q, (vd, uv))

        return d, prev

    def getDijkstraShortestPath(self, start, goal):
        _, prev = self.Dijkstra_search(start)
        shortestPath = []
        node = goal
        while node is not None:
            shortestPath.append(node)
            node = prev[node]
        return shortestPath[::-1]


N, M = map(int, input().split())
islands = Dijkstra()
for _ in range(M):
    a, b = map(int, input().split())
    islands.add(a, b, 1)

dis = islands.Dijkstra_search(1)[0][N]

if dis > 2:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
n,m=map(int,input().split())
a=[0]*(n+1)
b=[0]*(n+1)
flg=0
for i in range(m):
  p,q=map(int,input().split())
  if (p==1 and q==n) or (p==n and q==1):
    flg=1
  elif p==1:
    a[q]=1
  elif q==1:
    a[p]=1
  elif p==n:
    b[q]=1
  elif q==n:
    b[p]=1
for i in range(1,n+1):
  if a[i]==1 and b[i]==1:
    flg=1
if flg==1:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
def answer(destination, services):
    P, M = ("POSSIBLE", "IMPOSSIBLE")
    dic = {}
    for a, b in services:
        if dic.get(a) is None:
            dic[a] = [b]
        else:
            dic[a].append(b)
        if dic.get(b) is None:
            dic[b] = [a]
        else:
            dic[b].append(a)
    if dic.get(destination) is None: return M
    arr = dic[destination]
    for i in arr:
        if 1 in dic[i]:
            return P
    return M

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

Solution (Python):
import fractions
import sys
from functools import reduce
import math

input = sys.stdin.readline


def main():
    n, m = input_list()
    starts = []
    ends = []
    for _ in range(m):
        a, b = input_list()
        if a == 1:
            starts.append(b)
        elif b == n:
            ends.append(a)
    
    if set(starts) & set(ends):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

def get_camulative(l):
    import itertools
    
    return [0] + list(itertools.accumulate(l))

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def gcd(*numbers):
    return reduce(fractions.gcd, numbers)


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
G = [[] for _ 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)
  
for i in G[0]:
  for j in G[i]:
    if j == N-1:
      print('POSSIBLE')
      exit()
      
print('IMPOSSIBLE')

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

fukasa = [10 ** 18 for _ in range(n)]
kaisuu = 0
settansaku = set([])
setmada = set([0])
kouho = 1

while kouho != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		kouho -= 1
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					kouho += 1
					fukasa[k] = kaisuu

if fukasa[n-1] <= 2:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

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

fukasa = [10**18 for _ in range(n)]
kaisuu = 0
settansaku = set([])
setmada = set([0])

while len(setmada) != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					fukasa[k] = kaisuu

if fukasa[n-1] <= 2:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Solution (Python):
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *

from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction



mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]








    


N,M=l()
g=[[]  for i in range(N+1)]
for i in range(M):
    a,b=l()
    g[a].append(b)
    g[b].append(a)
pos=0
for j in g[1]:
    if(N in g[j]):
        pos=1
        break
if(N in g[1] or pos):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

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

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

    edge[a].append(b)
    edge[b].append(a)


from collections import deque

d = deque([0])

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

while d:
    v = d.popleft()

    for w in edge[v]:
        if dist[w]==-1:
            dist[w]=dist[v]+1
            d.append(w)

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

Solution (Python):
from collections import defaultdict


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

    g = defaultdict(list)

    for n in ab:
        g[n[0]].append(n[1])

    if 1 not in g:
        print('IMPOSSIBLE')
        exit()

    for i in g[1]:
        if i not in g:
            continue
        for j in g[i]:
            if j == N:
                print('POSSIBLE')
                exit()

    print('IMPOSSIBLE')


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

N,M,*abf = map(int, open(0).read().split())
ab = [abf[i:i+2] for i in range(0, len(abf), 2)]

connected = [[]for _ in range(N+1)]
for u, v in ab:
    connected[u].append(v)
    connected[v].append(u)
    
d = deque([])
for x in connected[1]:
    if x == N:
        print('POSSIBLE')
        break
    else:
        d.append(x)
else:
    while d:
        temp = d.popleft()
        for x in connected[temp]:
            if x == N:
                print('POSSIBLE')
                break
        else:
            continue
        break
    else:
        print('IMPOSSIBLE')

Solution (Python):
import sys

N, M = map(int, sys.stdin.readline().strip().split())

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

for i in paths[1]:
    for j in paths[i]:
        if j == N:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")

Solution (Python):
import sys
from collections import deque

N, M = map(int, sys.stdin.readline().strip().split())

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

q = deque([(1, 0)])
visited = set()
while q:
    p, c = q.popleft()
    if p in visited:
        continue
    visited.add(p)
    if c > 2:
        continue
    if p == N:
        print("POSSIBLE")
        sys.exit()
    for next_p in paths[p]:
        q.append((next_p, c+1))

print("IMPOSSIBLE")

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque 
def main():
    n, m = map(int, readline().split())
    to = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, readline().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)

    INF = int(1e6) 
    dq = deque()
    dq.append(0)
    dist = [INF for _ in range(n)]
    dist[0] = 0
    while len(dq)>0: 
        v = dq.popleft()
        for nx in to[v]:
            if dist[nx] != INF:
                continue
            dq.append(nx)    
            dist[nx] = dist[v]+1
    if dist[n-1] == 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

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



reachables = defaultdict(set)
for a, b in data:
    reachables[a].add(b)
    reachables[b].add(a)


reachables_from1 = reachables[1]
possible = False
for i in reachables_from1:
    if n in reachables[i]:
        possible = True
        break

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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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

from itertools import permutations
from math import factorial, hypot





N, M = getNM()
dist = [set() for i in range(N)]
for i in range(M):
    a, b = getNM()
    dist[a - 1].add(b - 1)
    dist[b - 1].add(a - 1)

flag = False
for i in list(dist[0]):
    if N - 1 in dist[i]:
        flag = True
print('POSSIBLE' if flag else 'IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
from_1 = set()
to_N = set()
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    from_1.add(b)
  if b == N:
    to_N.add(a)

if len(from_1 & to_N) >= 1:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
reachable_islands_from_1 = []    
reachable_islands_from_n = []    

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

if len(list(set(reachable_islands_from_1) & set(reachable_islands_from_n))) == 0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
ab = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    ab[a].append(b)
    ab[b].append(a)

ans = "IMPOSSIBLE"
for u in ab[1]:
    if N in ab[u]:
        ans = "POSSIBLE"
        break
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:
    sa.add(b)
  if b==n:
    sb.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")

Solution (Python):
N,M = list(map(int,input().split()))
N = str(N)
AB = [input().split() for _ in range(M)]
_1B = set([ab[1] for ab in AB if ab[0] == '1'])
BN = set([ab[0] for ab in AB if ab[1] == N])
if len(_1B&BN) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
class Ship:
  def __init__(self, land_from, land_to):
    self.land_from = land_from - 1
    self.land_to = land_to - 1

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

mid_from = set()
mid_to = set()

ships = []
for _ in range(M):
  f, t = map(int, input().split())
  ship = Ship(f, t)
  if ship.land_from == 0:
    mid_from.add(ship.land_to)
  if ship.land_to == N - 1:
    mid_to.add(ship.land_from)


if mid_from & mid_to:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
def main():
    n, m = list(map(int, input().split()))
    connect_1 = set()
    connect_n = set()
    for _ in range(m):
        a, b = list(map(int, input().split()))
        if a == 1:
            connect_1.add(b)
        elif b == n:
            connect_n.add(a)
        else:
            pass
    if connect_1.isdisjoint(connect_n):
        print('IMPOSSIBLE')
    else:
        print('POSSIBLE')

if __name__ == '__main__':
    main()

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

st,go = set(),set()
for i in range(m):
    if 1 in L[i]:
        st.add(L[i][1])
    if n in L[i]:
        go.add(L[i][0])

if set(st)&set(go):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

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

Solution (Python):

n,m = map(int,input().split())
 
lis = [[] for i in range(n)] 
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 
 
if set(lis[-1]).isdisjoint(set(lis[0])): 
    print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Solution (Python):
n,m = map(int,input().split())
 
lis = [[] for i in range(n)] 
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 
 
if set(lis[-1]).isdisjoint(set(lis[0])):
    print('IMPOSSIBLE')
else:
  print('POSSIBLE')

Solution (Python):

N, M = map(int, input().split())
link1 = [False for i in range(N+1)]
link2 = [False for i in range(N+1)]
flag = False
for i in range(M):
    A, B = map(int, input().split())
    if A == 1:
        link1[B] = True
    elif B == N:
        link2[A] = True
for i in range(2, N):
    if link1[i] and link2[i]:
        print("POSSIBLE")
        flag = True
        break
if flag == False:
    print("IMPOSSIBLE")

Solution (Python):
from collections import deque

N,M=map(int,input().split())
graph=[[] for _ 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)

def dfs(start):
    d=[float("inf")]*N
    d[start]=0

    queue=deque([start])
    while queue:
        x=queue.popleft()
        for y in graph[x]:
            if d[y]!=float("inf"):
                continue
            d[y]=d[x]+1
            queue.append(y)
    
    return d

d=dfs(0)
if d[-1]==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

Solution (Python):
n, m = map(int, input().split())
s = [False] * (n + 1)
t = [False] * (n + 1)
for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    s[b] = True
  if b == n:
    t[a] = True
for i in range(2, n):
  if s[i] and t[i]:
    print('POSSIBLE')
    break
else:
  print('IMPOSSIBLE')

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

from collections import defaultdict 
V = defaultdict(list)

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

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * (n+1) 
    d[u] = 0 
    while queue:
        v = queue.popleft()
        for i in V[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

b1 = bfs(1)
if b1[n] ==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

s1 = set()
s2 = set()
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s1.add(b)
    elif b == 1:
        s1.add(a)
    elif a == n:
        s2.add(b)
    elif b == n:
        s2.add(a)

if s1.isdisjoint(s2):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
import bisect


def main():
    N, M = list(map(int, input().split(' ')))
    from_1 = list()
    to_n = list()
    for _ in range(M):
        a, b = list(map(int, input().split(' ')))
        if a == 1:
            from_1.append(b)
        elif b == N:
            to_n.append(a)
    from_1.sort()
    for via in to_n:
        index = bisect.bisect_left(from_1, via)
        if index < len(from_1) and from_1[index] == via:
            print('POSSIBLE')
            return
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
E1=set()
EN=set()
for i in range(M):
    x,y=map(int,input().split())
    if x==1 or y==1:
        E1.add(x)
        E1.add(y)

    if x==N or y==N:
        EN.add(x)
        EN.add(y)

if E1 & EN!=set():
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")