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())
neighborof1 = set()
neighborofN = set()
for j in range(M):
    a, b = map(int, input().split())
    if a == 1:
        neighborof1.add(b)
    elif b == N:
        neighborofN.add(a)
flag = 0
if len(neighborof1) > len(neighborofN):
    for i in neighborofN:
        if i in neighborof1:
            flag = 1
            break
else:
    for k in neighborof1:
        if k in neighborofN:
            flag = 1
            break
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
s = set()
t = set()
for i in range(m):
    a, b = map(int, input().split())
    if a > b : a, b = b, a
    if a == 1:
        s.add(b)
    if b == n:
        t.add(a)

if s & t:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
arr = input().split()
n = int(arr[0])
m = int(arr[1])

x = []
y = []

for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        x.append(b)
    if b == n:
        y.append(a)

if len(set(x+y)) < len(x) + len(y):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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


for j in range(len(can[1])):
  k = can[1][j]
  if N in can[k]:
    print("POSSIBLE")
    quit()
    
print("IMPOSSIBLE")

Solution (Python):
N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
D=[[]for i in range(N)]
for i in range(M):
  D[A[i][0]-1].append(A[i][1]-1)
  D[A[i][1]-1].append(A[i][0]-1)
a=len(D[-1])
b=len(D[0])
c=len(set(D[-1]+D[0]))
if a+b==c:
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

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

starts = {}
goals = {}
for i in range(len(A)):
    s_num = A[i][0]
    g_num = A[i][1]
    if s_num == '1':
        starts[A[i][1]] = 0
    elif g_num == str(N):
        goals[A[i][0]] = 0

is_ok = False
for s in starts:
    if s in goals:
        is_ok = True
        break











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

Solution (Python):
from collections import deque

def solve(n, m, AB):
    g = [[] for _ in range(n)]
    for a, b in AB:
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    q = deque(maxlen = n)
    q.append((0, 0))
    used = {0}
    while len(q) > 0:
        i, d = q.popleft()
        if d >= 2:
            break
        for c in g[i]:
            if c in used:
                continue
            if d == 1 and c == n - 1:
                return 'POSSIBLE'
            q.append((c, d + 1))
            used.add(c)
    return 'IMPOSSIBLE'

_n, _m = map(int, input().split())
_AB = [map(int, input().split()) for _ in range(_m)]
print(solve(_n, _m, _AB))

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())

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


for i in rList[0]:
  if rList[i-1].count(n) > 0:
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict
d = defaultdict(set)
n, m = map(int, input().split())
for _ in range(m):
    a, b = map(int, input().split())
    d[a].add(b)


def solve(n, d):
    for a in d[1]:
        if n in d[a]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'


print(solve(n, d))

Solution (Python):
from collections import defaultdict
d = defaultdict(list)
n, m = map(int, input().split())
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)


for a in d.keys():
    d[a] = set(d[a])


def solve(n, d):
    for a in d[1]:
        if n in d[a]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'


print(solve(n, d))

Solution (Python):
N, M = map(int, input().split())
first = set()
second = set()
for _ in range(M):
  a, b = map(int, input().split())
  if a == 1:
    first.add(b)
  elif b == N:
    second.add(a)

ans = 0
for i in first:
  if i in second:
    ans = 1
    break
if ans:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
first = [False] * n
second = [set() for _ in range(max(m,n)+1)]

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        first[b] = True
    else:
        second[a].add(b)

f = True
for i in range(1, n):
    if first[i]:
        if n in second[i]:
            f = False
            break
if f:
    print('IM', end='')
print('POSSIBLE')

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,m = map(int,input().split())
can_flag = 0 
from_1 = []
to_n = []
for i in range(m):
    s,d = map(int,input().split())
    if s == 1: from_1.append(d)
    if d == n: to_n.append(s)
from_1.sort()
to_n.sort()
idx_from = 0
idx_to = 0

while idx_from != len(from_1) and idx_to != len(to_n):
    if from_1[idx_from] == to_n[idx_to]:
        can_flag = 1
        break
    elif from_1[idx_from] > to_n[idx_to]:
        idx_to += 1
    else: idx_from += 1
if can_flag: print("POSSIBLE")
else: print("IMPOSSIBLE")

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

S = []
for _ in range(M):
    D = list(map(int, input().split()))
    S.append(D)

set1=set()
set2=set()

for tmp in S:
    if tmp[0]==1:
        set1.add(tmp[1])
    if tmp[1]==N:
        set2.add(tmp[0])

if len(set1&set2) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
import sys

if sys.platform =='ios':
	sys.stdin=open('input_file.txt')
	

n,m=list(map(int, input().split()))
aa={i:[] for i in range(1,n+1)}
for _ in range(m):
	a,b = list(map(int, input().split()))
	aa[a].append(b)
	aa[b].append(a)
for a in aa[1]:
	if n in aa[a]:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
side1=set()
side2=set()
for i in range(m):
	a,b=map(int,input().split())
	if a==1:
		side1.add(b)
	elif b==n:
		side2.add(a)
print(("" if side1 & side2 else "IM")+"POSSIBLE")

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

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

	if a == 1:
		side1.add(b)
	
	elif b == n:
		side2.add(a)

print(("" if side1 & side2 else "IM") + "POSSIBLE")

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

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

	if a == 1:
		side1.add(b)
	
	elif b == n:
		side2.add(a)

print(("" if side1 & side2 else "IM") + "POSSIBLE")

Solution (Python):
N,M=map(int,input().split())
f=set()
t=set()
for i in range(M):
  a,b=map(int,input().split())
  if a<2:
    f.add(b)
  if b==N:
    t.add(a)
print("IM"*(len(f&t)^1)+"POSSIBLE")

Solution (Python):
N,M=map(int,input().split())
f=set()
t=set()
for i in range(M):
  a,b=map(int,input().split())
  if a<2:
    f.add(b)
  elif b==N:
    t.add(a)
print(("IM","")[len(f&t)]+"POSSIBLE")

Solution (Python):
N,M=map(int,input().split())
from1=set()
toN=set()
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    from1.add(b)
  elif b==N:
    toN.add(a)
print(("","IM")[len(from1&toN)==0]+"POSSIBLE")

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


ans = 'IMPOSSIBLE'
if first & second:
    ans = 'POSSIBLE'
print(ans)

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

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

if first & second:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
x = []
y = []
for _ 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+y)) < len(x)+len(y):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
import collections


input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    ab = [[] for j in range(N + 1)]
    distance = [0] * (N + 1)
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        ab[a].append(b)
        ab[b].append(a)

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

    visited = set()
    visited.add(1)

    while q:
        c, d = q.popleft()

        for n in ab[c]:
            if n not in visited:
                visited.add(n)
                q.append([n, d + 1])
                distance[n] = d + 1

    if distance[N] != 0 and distance[N] <=2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")




    
    
    

if __name__ == '__main__':
    main()

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

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

ans = "IMPOSSIBLE"

for i in liners[1]:
    if i in liners and N in liners[i]:
        ans = "POSSIBLE"
        break

print(ans)

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

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        lst.append(b)
    elif b == N:
        lst.append(a)
        
lst.sort()
flg = 0

for i in range(len(lst) - 1):
    if lst[i] == lst[i + 1]:
        flg = 1
        break
        
if flg:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):

import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
INF = 10**12


class Edge:  
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class Dijkstra:  
    def __init__(self, n):
        self.n = n
        self.dist = [INF for _ in range(n)]
        self.edges = [list() for _ in range(n)]
        self.q = collections.deque()

    def calcShortest(self, start):
        self.q.append((start, 0))
        while(len(self.q) != 0):
            v, cost = self.q.popleft()
            if cost > 2:
                continue
            if self.dist[v] <= cost:
                continue
            self.dist[v] = cost
            for edge in self.edges[v]:
                self.q.append((edge.to, cost+edge.cost))

    def addEdge(self, st, gl, cost):
        self.edges[st].append(Edge(gl, cost))


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

v.calcShortest(0)
if v.dist[n-1] <= 2:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')

Solution (Python):

import collections
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
INF = 10**12


class Edge:  
    def __init__(self, to, cost):
        self.to = to
        self.cost = cost


class Dijkstra:  
    def __init__(self, n):
        self.n = n
        self.dist = [INF for _ in range(n)]
        self.edges = [list() for _ in range(n)]
        self.q = collections.deque()

    def calcShortest(self, start):
        self.q.append((start, 0))
        while(len(self.q) != 0):
            v, cost = self.q.popleft()
            if cost > 3:
                continue
            if self.dist[v] <= cost:
                continue
            self.dist[v] = cost
            for edge in self.edges[v]:
                self.q.append((edge.to, cost+edge.cost))

    def addEdge(self, st, gl, cost):
        self.edges[st].append(Edge(gl, cost))


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

v.calcShortest(0)
if v.dist[n-1] <= 2:
    print('POSSIBLE')
    exit(0)
print('IMPOSSIBLE')

Solution (Python):
import collections
N, M = map(int, input().split())
ablist = []
hublist1 = []
hublistN = []
work = []
for i in range(M):
    ab = tuple(map(int, input().split()))
    ablist.append(ab)
    if N in ab:
        if ab[0] == N:
            hublistN.append(ab[1])
        else:
            hublistN.append(ab[0])

    if 1 in ab:
        if ab[0] == 1:
            hublist1.append(ab[1])
        else:
            hublist1.append(ab[0])
            
work = hublist1 + hublistN
c = collections.Counter(work)
if 2 in c.values():
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
print("POSSIBLE" if any(N in G[u] for u in G[1]) else "IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
d={}
flag=False

for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        try:
            flag=(d[b]==n)
        except:
            d[b]=1
    elif b==n:
        try:
            flag=(d[a]==1)
        except:
            d[a]=n
    if flag:
        print('POSSIBLE')
        break

if not flag:
    print('IMPOSSIBLE')

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

Solution (Python):

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

s = set()
g = set()

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

if s & g:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 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 S(): return input()
     
def main():
    N, M = LI()
    reachable_from_1 = set()
    reachable_to_N = []
    ships = []
    for _ in range(M):
        a, b = LI()
        ships.append((a, b))
        if b == N:
            reachable_to_N.append(a)
        if a == 1:
            reachable_from_1.add(b)
    ans = False
    for n in reachable_to_N:
        if n in reachable_from_1:
            ans = True
    if ans:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

main()

Solution (Python):
import sys
input = sys.stdin.readline
N,M = [int(i) for i in input().split()]
nes = [0] * (N+1)
for i in range(1,N+1) :
    nes[i] = []
for i in range(M) :
    a,b = [int(i) for i in input().split()]
    nes[a].append(b)
    nes[b].append(a)
ans = "IMPOSSIBLE"
for i in nes[1] :
    for j in nes[i] :
        if j == N :
            ans = "POSSIBLE"
            break
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N,M = [int(i) for i in input().split()]
nes = [0] * (N+1)
for i in range(1,N+1) :
    nes[i] = []
for i in range(M) :
    a,b = [int(i) for i in input().split()]
    nes[a].append(b)
    nes[b].append(a)
ans = "IMPOSSIBLE"
for i in nes[1] :
    for j in nes[i] :
        if j == N :
            ans = "POSSIBLE"
            break
print(ans)

Solution (Python):
N,M=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(M)]
l_1=[]
l_n=set()
for l in A:
    if 1 in l:
        l_1.append(sum(l)-1)
for l in A:
    if N in l:
        l_n.add(sum(l)-N)
for x in l_1:
    if x in l_n:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

Solution (Python):

N, M = map(int, input().split())
edges = [[] for _ in range(N + 1)]

from collections import deque

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

queue = deque()
queue.append(1)
colors = ["white"] * (N + 1)

u = queue.popleft()
colors[u] = "black"

for edge in edges[u]:
  if colors[edge] != "black":
    queue.append(edge)

for i in range(len(queue)):
  u = queue.popleft()
  colors[u] = "black"
  for edge in edges[u]:
    if colors[edge] != "black":
      queue.append(edge)

for q in queue:
  if q == N:
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Solution (Python):
import sys
input = sys.stdin.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)

u=g[0]
for v in u:
    if n-1 in g[v]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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

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

lst=set()
for a,b in AB:
    if b==N:
        lst.add(a)

for a,b in AB:
    if a==1:
        if b in lst:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

Solution (Python):
N,M=map(int, input().split())
TO = set([])
FM = set([])
for i in range(M):
    f,t = map(int, input().split())
    if f == 1:
        TO.add(t)
    elif t == N:
        FM.add(f)
if len(TO & FM)>0:
    ans = 'POSSIBLE'
else:
    ans = 'IMPOSSIBLE'
print(ans)

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

s = dict()

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

    if a not in s.keys():
        s[a] = list()

    s[a].append(b)

    if b not in s.keys():
        s[b] = list()

    s[b].append(a)

ans = False
for k in s[1]:
    g = s[k]
    if n in g:
        ans = True
        break

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

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

s = [0]*(n+1)
t = [0]*(n+1)
for i in ab:
  if i[0] == 1:
    s[i[1]] = 1
    
for i in ab:
  if i[1] == n:
    t[i[0]] = 1

for i in range(2,n):
  if s[i] == 1 and t[i] == 1:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(m)]
b=[None]*n
for i in a:
    if i[1]==n:
        if b[i[0]-1]!=None:
            print('POSSIBLE')
            exit()
        else:
            b[i[0]-1]=True
    if i[0]==1:
        if b[i[1]-1]!=None:
            print('POSSIBLE')
            exit()
        else:
            b[i[1]-1]=True
print('IMPOSSIBLE')

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

Solution (Python):
n,m=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(m)]
s=set()
for i in a:
    if i[1]==n:
        s.add(i[0])
for i in a:
    if i[0]==1 and i[1] in s:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

flag = [0, 0]
ls1 = []
ls2 = []

for i in range(m):
    if ls[i][0] == 1 and ls[i][1] == n:
        flag[0] = 1
        break
    elif ls[i][0] == 1:
        ls1.append(ls[i][1])
    elif ls[i][1] == n:
        ls2.append(ls[i][0])

ls1_ls2 = set(ls1) & set(ls2)

if len(ls1_ls2) != 0:
    flag[1] = 1

if sum(flag) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N,M = map(int,input().split())
ans = "IMPOSSIBLE"
f = dict(zip(list(range(N)),[0]*N))
s = dict(zip(list(range(N)),[0]*N))
for i in range(M):
    a,b = map(lambda x: int(x)-1, input().split())
    if a == 0:
        f[b] = 1
    if b == N-1:
        s[a] = 1
if len(f) > len(s):
    for i in range(len(s)):
        if s[i] == 1 and f[i] == 1:
            ans = "POSSIBLE"
            break
else:
    for i in range(len(f)):
        if f[i] == 1 and s[i] == 1:
            ans = "POSSIBLE"
            break
print(ans)

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

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

ans = False
for i in range(1,n-1):
    if li1[i] and li2[i]:
        ans = True
        break

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

def dijkstra(E, start):
    N_d = len(E)
    dist = [INF] * N_d
    dist[start] = 0
    q = [(0, start)]
    while q:
        dist_v, v = heappop(q)
        if dist[v] != dist_v:
            continue
        for u, dist_vu in E[v]:
            dist_u = dist_v + dist_vu
            if dist_u < dist[u]:
                dist[u] = dist_u
                heappush(q, (dist_u, u))
    return dist

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

for a, b in ab:
	E[a-1].append((b-1, 1))

d = dijkstra(E, 0)

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

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

for i in range(M):
    a,b = map(int,input().split())
    a,b = a-1, b-1
    if a == 0:
        first[b] = True
    if b == N-1:
        second[a] = True
for i,e in enumerate(first):
    if e:
        if second[i]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Solution (Python):
N, M = map(int,input().split())
AB = []
for _ in range(M):
    a,b = map(int,input().split())
    if  a == 1 or b== N:
        AB.append((a,b))
set1 = set()
set2 = set()
for ab in AB:
    if ab[0] == 1:
        set1.add(ab[1])
    if ab[1] == N:
        set2.add(ab[0])
if set1 & set2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
c = []
d = []
ans = "IMPOSSIBLE"
for i in range(M):
    if ab[i][0] == 1:
        c.append(ab[i][1])
    elif ab[i][1] == N:
        d.append(ab[i][0])
e = list(set(c + d))
if len(e) < len(c)+ len(d):
    ans = "POSSIBLE"
print(ans)

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

start = set() 
goal = set()  

for _ in range(M):
  x, y = map(int, input().split())
  if x == 1:
    start.add(y)
  elif y == N:
    goal.add(x)

if start & goal:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
N,M=map(int, input().split())
E=[[] for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,input().split())
    E[a].append(b)
    E[b].append(a)
for e1 in E[1]:
    for e2 in E[e1]:
        if e2==N:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Solution (Python):
from operator import itemgetter

N,M=list(map(int,input().split()))
a = []
b = []
for i in range(M):
    a1,b1=[int(i) for i in input().split()]
    a.append(a1)
    b.append(b1)

l1=[i for i, x in enumerate(b) if x == N]
l2=[i for i, x in enumerate(a) if x == 1]

try:
    s1=itemgetter(*l1)(a)
except:
    s1=[]
try:
    s2=itemgetter(*l2)(b)
except:
    s2=[]

if type(s1) is int:
    tmp=s1
    s1=(tmp,)
if type(s2) is int:
    tmp=s2
    s2=(tmp,)

if len(set(s1)&set(s2))>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
def main():
  N, M, *AB = map(int, open(0).read().split())

  inter, goalable = set(), set()
  
  iterator = iter(AB)
  for a, b in zip(iterator, iterator):
    if a == 1:
      inter.add(b)
    
    if b == N: 
      goalable.add(a)
      
  flag = inter & goalable
  print("POSSIBLE" if flag else "IMPOSSIBLE")
  
if __name__ == "__main__":
    main()

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

  inter, goalable = set(), set()
  for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
      inter.add(b)
    
    if b == N: 
      goalable.add(a)
      
  flag = inter & goalable
  print("POSSIBLE" if flag else "IMPOSSIBLE")
  
if __name__ == "__main__":
    main()

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

inter, goalable = set(), set()
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    inter.add(b)
    
  if b == N: 
    goalable.add(a)
      
flag = inter & goalable
print("POSSIBLE" if flag else "IMPOSSIBLE")

Solution (Python):
import sys
from collections import defaultdict


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

inter = []
goalable = defaultdict(lambda: False)
for i in range(M):
  start, end = map(int, input().split())
  if start == 1:
    inter.append(end)
  else:
    if end == N: 
      goalable[start] = True
      
for i in inter:
  if goalable[i]:
    print("POSSIBLE")
    sys.exit()
    
print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
A=set()
B=set()
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        B.add(b)
    if b==n:
        A.add(a)
    
if len(A&B)!=0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

for k in d1:
    if k in d2: 
        ans = "POSSIBLE"
        break
else:
    ans = "IMPOSSIBLE"

print(ans)

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

for i in range(m):
    if s[i][0] == 1:
        d[s[i][1]] = 1
    
for i in range(m):
    if s[i][1] == n and s[i][0] in d:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
N,M = map(int,input().split())
a=[0]*M
b=[0]*M
c=set() 

for i in range(M):
  a[i],b[i]=map(int,input().split())
  if a[i]==1:
    if b[i] not in c:
      c.add(b[i])
    
for j in range(M):
  if a[j]!=1:
    if a[j] in c:
      if b[j]==N:
        print("POSSIBLE")
        break
else:
  print("IMPOSSIBLE")

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

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

for i in x[0]:
    for j in x[i]:
        if j == n-1:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

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

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

if x[0] == []:
    print("IMPOSSIBLE")
    exit()

for i in x[0]:
    for j in x[i]:
        if j == n-1:
            print("POSSIBLE")
            exit()

print("IMPOSSIBLE")

Solution (Python):
def main():
    n,m=map(int,input().split())
    L=[list(map(int,input().split())) for _ in range(m)]
    S=[]
    G=[]
    for l in L:
        if l[0]==1: S.append(l[1])
        if l[1]==n: G.append(l[0])
    print("POSSIBLE"if len(set(S)&set(G))>0 else "IMPOSSIBLE")
main()

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

ship_list1 = []
ship_list2 = []
count = 0
loop = False

for i in range(m):
    if ab[i][0] == 1:
        ship_list1.append(ab[i][1])
    if ab[i][1] == n:
        ship_list2.append(ab[i][0])

if len(set(ship_list1) & set(ship_list2)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M = map(int, input().split())
A = [0] * M
B = [0] * M

for i in range(M):
    A[i],B[i] = map(int, input().split())
aa = []
bb = []
for i in range(M):
    if(A[i] == 1):
        aa.append(B[i])
    if(B[i] == N):
        bb.append(A[i])

aa = set(aa)
bb = set(bb)
ret = aa & bb
if (len(ret) == 0):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N, M=map(int, input().split())
x=[]
y=[]
for i in range(M):
  a, b=map(int, input().split())
  if a==1:
    x.append(b)
  if b==N:
    y.append(a)
    
nx=len(x)
ny=len(y)

if nx==0 or ny==0:
  print('IMPOSSIBLE')
  exit()

x.sort()
y.sort()
i=0
j=0
out='IMPOSSIBLE'

while i+j<nx+ny-1:
  if x[i]==y[j]:
    out='POSSIBLE'
    break
  elif x[i]>y[j]:
    j+=1
  else:
    i+=1
    
print(out)

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

Solution (Python):
import sys
import copy

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

def dfs(node, count):

    if seen[node]==True:
        return
    seen[node]=True

    if node==(N-1) and count==2:
        print("POSSIBLE")
        sys.exit()
    elif count==2:
        return
    count = count + 1
    seen[node]=True

    for next_node in V[node]:
        dfs(next_node, count)

    return

V = []
seen = [False]*N

for i in range(N):
    V.append(set())

for i in range(M):
    *l, = map(int, input().split())
    V[l[0]-1].add(l[1]-1)
    V[l[1]-1].add(l[0]-1)


dfs(0, 0)

print("IMPOSSIBLE")