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

Solution (Python):


import sys


N,M=list(map(int,raw_input().split()))



adj=[[] for i in range(N+1)]


for i in range(M):
	x,y=list(map(int,raw_input().split()))
	
	
	adj[x].append(y)
	adj[y].append(x)




F=(N+1)*[0]


S=[]


dist=(N+1)*[0]


S.append(1)
while len(S) != 0:
	
	v=S.pop()
	
	
	if F[v]==0:
		F[v]=1
		
		for u in adj[v]:
			
			if F[u]==0:
				S.append(u)
				if dist[u] == 0:
					dist[u]=dist[v]+1
					
					



if dist[N]==2:
	print "POSSIBLE"
else:
	print "IMPOSSIBLE"

Solution (Python):
n, m = map(int, input().split())
ship_1 = [False]*(n+1)
ship_n = [False]*(n+1)
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ship_1[b] = True
    elif b == n:
        ship_n[a] = True

for i in range(len(ship_1)):
    if ship_1[i] and ship_n[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
ab_list = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]

lis = [[] for i in range(N)]

for i in range(M):
    lis[ab_list[i][0]].append(ab_list[i][1])

que = [[0, 0, lis[0], []]]
ends = []
res = False

while que:
    count, now, next_nodes, visited = que.pop()
    visited.append(now)
    if now == N - 1:
        ends = visited[:]
    for node in next_nodes:
        if node in visited or count == 2:
            continue
        que.append([count + 1, node, lis[node], visited[:]])

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

Solution (Python):
import sys
from collections import Counter




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


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


n, m = read_int_list()

a = [0] * m
b = [0] * m

for i in range(m):
    a[i], b[i] = read_int_list()

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

res = 'IMPOSSIBLE'
for i, v in c.items():
    if v == 2:
        res = 'POSSIBLE'
print(res)

Solution (Python):
import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if a == 1:
        list1.append(b)
        continue
    if b == N:
        nlist.append(a)
        continue
matched_list = list(set(list1) & set(nlist))
if len(matched_list) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

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

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

flag=False
for i in ship[1]:
    if n in ship[i]: flag=True; break

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

Solution (Python):
import sys
l = list(map(int, input().split(' ')))
N = l[0]
N_ = l[0] + 1
M = l[1]
y = []
u = set()

for i in range(M):
    k = list(map(int, input().split()))
    a = k[0]
    b = k[1]
    if (a == 1):
        y.append(b)
    elif (b == N):
        u.add(a)

for i in y:
    if (i in u):
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

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

Solution (Python):
N,M=list(map(int,input().strip().split(' ')))
graph=[[] for i in range(N)]
for _ in range(M):
    a,b=list(map(int,input().strip().split(' ')))
    a-=1
    b-=1
    graph[a]+=[b]
    graph[b]+=[a]
from collections import deque

q=deque([0])

visit=[0]*N
level=[0 for i in range(N)]
level[N-1]=3
parent=[-1]*N
while q:
    v=q.popleft()
    visit[v]=1
    for adj in graph[v]:
        if adj!=parent[v] and visit[adj]==0:
            parent[adj]=v
            visit[adj]=1
            q+=[adj]
            level[adj]=level[v]+1
if level[N-1]<=2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
input = sys.stdin.readline
def main():
   N,M = map(int,input().split())
   Set = set()
   for i in range(M):
      a,b = map(int,input().split())
      Set.add((a,b))
      Set.add((b,a))                        
   for j in range(2,N):
      if (1,j) in Set and (j,N) in Set:
         print("POSSIBLE")
         return
   print("IMPOSSIBLE")

main()

Solution (Python):



mozir=input()
hyo=mozir.split(' ')
N=int(hyo[0])
M=int(hyo[1])

a=[]
b=[]
for idx in range(0,M,1):
    mozir=input()
    hyo=mozir.split(' ')
    a.append(int(hyo[0])-1)
    b.append(int(hyo[1])-1)


myon_tbl=[False]*N

meguru_tbl=[False]*N
for idx in range(0,M,1):
    if a[idx]==0:
        myon_tbl[b[idx]]=True

    if b[idx]==N-1:
        meguru_tbl[a[idx]]=True

ans=False
for idx in range(0,N,1):
    if myon_tbl[idx] and meguru_tbl[idx]:
        ans=True
        break

prefix='' if ans else 'IM'
print(prefix+'POSSIBLE')

Solution (Python):
N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
    temp = map(int, raw_input().split())
    if 1 == temp[0]:
        a.append(temp[1])
    elif N == temp[1]:
        b.append(temp[0])

if any(list(set(a) & set(b))):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
d = {}

def bfs(graph, start, goal): 

 
    visited, queue = set(), [start] 
    pathsTo = {} 
    pathsTo[start] = [start] 
    index = 0
    lenqueue = 1

    while index < lenqueue: 

        vertex = queue[index] 
        if vertex not in visited: 
            visited.add(vertex) 
 
 
            
            for newVertex in (graph[vertex]): 
                if newVertex not in visited: 
                    if newVertex not in pathsTo: 
                        pathsTo[newVertex] = list() 
 
                    for path in pathsTo[vertex]: 
                        pathsTo[newVertex].append(str(path)+"->"+str(newVertex)) 
                    queue.append(newVertex)
                    lenqueue += 1
        index += 1
    
    if goal not in pathsTo.keys():
        return ["8384793->8->4->7-> 9 8 23748"]
    return pathsTo[goal] 

N, M = map(int,input().split())
for i in range(M):
    a,b = map(int,input().split())
    if a not in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)

    if b not in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)

dist = len(bfs(d,1,N)[0].split("->")) - 1
if dist <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):


import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        N, M = map(lambda x: int(x), line.split(" ", 2))

        services_1 = {}
        services_n = []
        for i in xrange(M):
            a, b = map(lambda x: int(x), sys.stdin.readline().split(" ", 2))
            if a == 1:
                services_1[b] = True
            if b == N:
                services_n.append(a)

        if 1 in services_n:
            print("POSSIBLE")

        result = "IMPOSSIBLE"
        for service in services_n:
            if service == 1 or service in services_1:
                result = "POSSIBLE"
                break
        print result                

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Solution (Python):
a=input().split()
N=int(a[0])
M=int(a[1])
first=[]
second=[]
i=0
while i<M:
	y=input().split()
	if int(y[0])==1:
		first.append(y[1])
	elif int(y[1])==N:
		second.append(y[0])
	i+=1

first=set(first)
second=set(second)
if len(first.intersection(second))>0:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

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

for i in range(M):
    if a[i] == 1:
        ikeru[b[i]] = 1
ikeru_2 = [0]*(N+1)
for i in range(M):
    if ikeru[a[i]] == 1:
        ikeru_2[b[i]] = 1
if ikeru_2[N] == 1 or ikeru[N] == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
def main():
    N, M = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in range(M))

    if M == 1:
        print('IMPOSSIBLE')
        return

    relay = []
    for a, b in A:
        if a == 1:
            relay.append(b)
        elif b == N:
            relay.append(a)

    if len(relay) > len(set(relay)):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

main()

Solution (Python):


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

from_1 = set([ship[1] for ship in ships if ship[0] == 1])
to_N = set([ship[0] for ship in ships if ship[1] == N])

if from_1.intersection(to_N):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):


import sys

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

from_to = {}
for i in range(M):
    line = input()
    line = line.rstrip()
    ai, bi = map(int, line.split())

    l = from_to.get(ai, list())
    l.append(bi)
    from_to[ai] = l



next_lands = from_to.get(1, list())
if not next_lands:
    print('IMPOSSIBLE')

for n in next_lands:
    goals = from_to.get(n, list())
    if N in goals:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

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

Solution (Python):
import sys
N, M = map(int, input().split())
m = set()
m2 = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        m.add(b)
    if b == N:
        m2.add(a)
for me in m:
    if me in m2:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Solution (Python):

from queue import Queue

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

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

def is_reach(n):
    dist = [0 for i in range(N+1)]
    is_visit = [False for i in range(N+1)]
    is_visit[1] = True
    q = Queue()
    q.put(1)
    while not q.empty():
        v = q.get()
        for u in graph[v]:
            if not is_visit[u]:
                is_visit[u] = True
                q.put(u)
                dist[u] = dist[v] + 1
                if u == n and dist[u] == 2:
                    return True
                if dist[u] > 2:
                    return False
    return False

print("POSSIBLE" if is_reach(N) else "IMPOSSIBLE")

Solution (Python):


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

l = [[] for i in range(N)]
for pi in p:  
    l[pi[0]-1].append(pi[1])
    l[pi[1]-1].append(pi[0])

flag = False

for li in l[0]:
    if( N in l[li-1] ):
        flag = True
        break

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

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

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

    if a == 1:
        dest_list_1.append(b)
    elif b == 1:
        dest_list_1.append(a)
    elif a == N:
        dest_list_2.append(b)
    elif b == N:
        dest_list_2.append(a)

len_dest_1 = len(dest_list_1)
len_dest_2 = len(dest_list_2)

if len(set(dest_list_1 + dest_list_2)) == len_dest_1 + len_dest_2:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

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

head = [-1 for _ in range(N + 1)]
edge= [-1 for _ in range(M + 1)]
next = [-1 for _ in range(M + 1)]

tot = 0

def add_edge(a, b):
  global tot
  edge[tot] = b
  next[tot] = head[a]
  head[a] = tot
  tot += 1

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

def find(start, step):
  if step == 0:
    if start == N:
      return True
    else:
      return False
  p = head[start]
  while p != -1:
    if find(edge[p], step - 1) == True:
      return True
    p = next[p]
  return False

if find(1, 2) == True:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
ab = [[0 for i in range(2)] for j in range(M)]
s = set()
ispossible = False
for i in range(M):
	ab[i] = list(map(int, input().split()))
	if ab[i][0] == 1:
		s.add(ab[i][1])
for i in range(M):
	if ab[i][0] in s and ab[i][1] == N:
		ispossible = True
		break
if ispossible:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Solution (Python):
N, M = [int(x) for x in input().split()]
S1 = []
S2 = []
for i in range(M):
	S1 = [int(x) for x in input().split()]
	if S1[0] == 1:
		S2.append(S1[1])
	if S1[1] == N:
		S2.append(S1[0])
		
if len(S2) == len(set(S2)):
	print("IMPOSSIBLE")
else:
	print("POSSIBLE")

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


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

for i in range(M):
	if c[i][1] == N:
		e.append(c[i][0])

l = list(set(d) & set(e))

if l == []:
	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)


set_x = set(x)
set_y = set(y)
z = list(set_x & set_y)

if(len(z)>0):
	ans="POSSIBLE"
else:
	ans="IMPOSSIBLE"

print(ans)

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

boat = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(v) for v in input().split()]
    boat[a-1].append(b-1)
    boat[b-1].append(a-1)
    
ans = False
for island in boat[N-1]:
    ans |= any(t == 0 for t in boat[island])
    
print ("POSSIBLE" if ans else "IMPOSSIBLE")

Solution (Python):
import sys

n, m = list(map(int, input().split()))
mid_set1 = set([])
mid_set2 = set([])

for i in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        mid_set1.add(b)
    elif b == n:
        mid_set2.add(a)

if len(mid_set1&mid_set2) > 0:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')

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

p1 = []
p2 = []
def solve():
    for i in range(M):
        a,b = map(int, input().split())
        if a == 1:
            p1.append(b)
        elif b == N:
            p2.append(a)
    return len(set(p1) & set(p2)) > 0

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

Solution (Python):
n,m = (int(i) for i in input().split())
abstart=[]
abgoal=[]
for i in range(0,m):
    inp=[int(i) for i in input().split()]
    if inp[0]==1:
        abstart.append(inp[1])
    elif inp[1]==n:
        abgoal.append(inp[0])

start = set(abstart)
goal = set(abgoal)
matched = list(start & goal)

if len(matched)>0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys

input = sys.stdin.readline

def main():
  N,M = map(int,input().split())
  m = set()
  for _ in range(M):
    a,b = map(int,input().split())
    if a < b:
      m.add((a,b))
    else:
      m.add((b,a))
  for i in range(2,N):
    if (1,i) in m and (i,N) in m:
      print('POSSIBLE')
      break
  else:
    print('IMPOSSIBLE')

main()

Solution (Python):
def c():
    n, m = map(int, input().split())
    ship_loot = []
    for _ in range(m):
        a, b = map(int, input().split())
        ship_loot.append( (a, b) )

    loot = { x:set() for x in range(1, n+1)}
    for l in ship_loot:
        a, b = l
        loot[a].add(b)
        loot[b].add(a)

    print('POSSIBLE' if loot[1] & loot[n] else 'IMPOSSIBLE')
    
    
    

c()

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

m_1=[0]*(N+1)
m_N=[0]*(N+1)
for _ in range(M):
    a,b=map(int,raw_input().split(' '))
    if a==1:
        m_1[b]=1
    if b==N:
        m_N[a]=1

a=''.join(map(str,m_1))
b=''.join(map(str,m_N))

c=int(a,2)
d=int(b,2)


if c&d==0:
    print 'IMPOSSIBLE'
else:
    print 'POSSIBLE'

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

Solution (Python):
N, M = [int(i) for i in input().split()]
edge = dict()
for i in range(1,N+1):
    edge[i] = set()
for i in range(M):
    a, b = [int(i) for i in input().split()]
    edge[a].add(b)
    edge[b].add(a)
c = edge[1].intersection(edge[N])
if len(c) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
nums=[int(x) for x in input().split()]
V,E = nums[0],nums[1]
graph = {x:[] for x in range(V)}

for i in range(E):
    nums=[int(x) for x in input().split()]
    a,b = nums[0]-1,nums[1]-1
    graph[a].append(b)
    graph[b].append(a)


if __name__ == '__main__':
	goal = V - 1
	mids = graph[0]
	for isl in mids:
		if goal in graph[isl]:
			print("POSSIBLE")
			exit(0)
	print("IMPOSSIBLE")

Solution (Python):
N, M = map(int,input().split())
ships_1 = []
ships_2 = []
for m in range(M):
    tmp = list(map(int,input().split()))
    if tmp[0]==1:
        ships_1.append(tmp[1])
    elif tmp[1] == N:
        ships_2.append(tmp[0])

matched_list = list(set(ships_1) & set(ships_2))
if matched_list:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):


if __name__ == "__main__":
    n, m = map(int, input().split())

    connected_1 = []
    connected_n = []

    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            connected_1.append(b)
            continue
        elif a == n:
            connected_n.append(b)
            continue
        elif b == 1:
            connected_1.append(a)
            continue
        elif b == n:
            connected_n.append(a)
            continue
        else:
            continue

    if len(set(connected_1).intersection(set(connected_n))) >= 1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

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

if set(n) & set(o):
    print ('POSSIBLE')
else:
    print ('IMPOSSIBLE')

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

rl = [[] for x in range(n + 1)]

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

now = 1
next_node = rl[now]
if n in next_node or n == 1:
    print("POSSIBLE")
    __import__("sys").exit()


for node in next_node:
    if n in rl[node]:
        print("POSSIBLE")
        __import__("sys").exit()
print("IMPOSSIBLE")

Solution (Python):

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

aa = []
bb = []

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

    if b == n:
        bb.append(a)

aa = set(aa)
bb = set(bb)

ret = aa & bb

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

Solution (Python):


def main():
	n, m = list(map(int, input().split()))
	ships = [list(map(int, input().split())) for _ in range(m)]
	frm1 = [x[1] for x in ships if x[0] == 1]
	toN = [x[0] for x in ships if x[1] == n]
	out = set(frm1).intersection(set(toN))
	if len(out) >= 1:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
		
if __name__ == '__main__':
	main()

Solution (Python):
N, M = map(int, raw_input().split(" "))
frs = {}
tos = {}
for m in xrange(M):
  fr, to = map(int, raw_input().split(" "))
  if fr == 1:
    if to in tos:
      print "POSSIBLE"
      break
    frs[to] = 1
  elif to == N:
    if fr in frs:
      print "POSSIBLE"
      break
    tos[fr] = 1
else:
  print "IMPOSSIBLE"

Solution (Python):



import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)



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

    mid1 = set()
    mid2 = set()
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            mid1.add(b)
        elif b == N:
            mid2.add(a)

    result = bool(mid1 & mid2)
    print("POSSIBLE" if result else "IMPOSSIBLE")

if __name__ == "__main__": main()

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

graph = [list() for i in range(N+1)]
for i in range(M):
    a, b = tuple(map(int, input().split()))
    graph[a].append(b)
    graph[b].append(a)

pos_flag = False
for u in graph[1]:
    if N in graph[u]:
        pos_flag = True
        break
if pos_flag == True:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")