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())
X = [[-1]*2 for i in range(N)]
for _ in range(M):
    a, b = sorted(map(int, input().split()))
    if a == 1:
        if X[b][1] > 0:
            print("POSSIBLE")
            break
        else:
            X[b][0] = 1
    if b == N:
        if X[a][0] > 0:
            print("POSSIBLE")
            break
        else:
            X[a][1] = 1
else:
  print("IMPOSSIBLE")

Solution (Python):



def main():
    n, m = map(int, input().split())
    is_included_1 = set()
    is_included_n = set()

    for i in range(m):
        ai, bi = map(int, input().split())

        if ai == 1:
            is_included_1.add(bi)
        elif bi == 1:
            is_included_1.add(ai)

        if ai == n:
            is_included_n.add(bi)
        elif bi == n:
            is_included_n.add(ai)

    if len(is_included_1 & is_included_n) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
a,b = map(int,input().split(" "))
ar = [[] for i in range(a+1)]
for i in range(b):
    l = list(map(int,input().split(" ")))
    ar[l[0]].append(l[1])
    ar[l[1]].append(l[0])
for r in ar[1]:
    if a in ar[r]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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

for i in range(M):
    ai, bi = input().split(' ')
    if ai == '1':
        a.append(bi)
    if bi == str(N):
        b.append(ai)
if len(set(a) & set(b)) > 0:
    print("POSSIBLE")
else:
    print('IMPOSSIBLE')

Solution (Python):
from collections import deque
def dfs(path):
    global visited, A
    q = deque([])
    q.append(path)
    for d in A[1]:
        q.append(d)
    while q:
        p = q.pop()
        for d in A[p]:
            if visited[d] == True:
                pass
            else:
                visited[d] = True


if __name__ == '__main__':
    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)
    visited = [False] * (N+1)
    dfs(1)
    if visited[N]:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Solution (Python):
N,M=map(int,input().split())
x=[0]*(N+1)
y=[0]*(N+1)
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        x[b]=1
    if b==N:
        y[a]=1
for i in range(N+1):
    if x[i]==1 and y[i]==1:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict
Liner = defaultdict(lambda: [])
def inpl(): return [int(i) for i in input().split()]
import sys
N, M = inpl()
for _ in range(M):
    a, b = inpl()
    Liner[a].append(b)
    Liner[b].append(a)
if not Liner[1]:
    print('IMPOSSIBLE')
    sys.exit()
for i in Liner[1]:
    if N in Liner[i]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Solution (Python):
from collections import defaultdict
Liner = defaultdict(lambda: [])
def inpl(): return [int(i) for i in input().split()]
import sys
N, M = inpl()
for _ in range(M):
    a, b = inpl()
    Liner[a].append(b)
    Liner[b].append(a)
if not Liner[1]:
    print('IMPOSSIBLE')
    sys.exit()
for i in Liner[1]:
    if N in Liner[i]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

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

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        s.add(b)
    elif b == n:
        e.add(a)
        
print('IM' * (1 - len(s & e)) + 'POSSIBLE')

Solution (Python):



def solve():
    from_start = set()
    to_end = set()
    n, m = map(int, input().split())

    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            from_start.add(b)
        elif b == n:
            to_end.add(a)

    if len(from_start & to_end) == 1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    solve()

Solution (Python):
N, M = map(int, input().split())
l1=[False]*(N+1)
l2=[False]*(N+1)


for i in range(M):
    a, b = map(int, input().split())
    if a==1:
        l1[b]=True
    elif b==N:
        l2[a]=True
        
fl=False
for i in range(N):
    if l1[i] and l2[i]:
        fl=True
    
if fl:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys

N, M = map(int, input().split())
ab = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]

first = dict()
for a, b in ab:
    if a == 1:
        first[b] = 1

for a, b in ab:
    if b == N:
        if a in first:
            print("POSSIBLE")
            exit()

print('IMPOSSIBLE')

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

L = [None] * M

for i in range(M):
    a, b = [int(x) for x in input().split()]
    L[i] = (a, b)

set1 = set()
set2 = set()

for l in L:
    a, b = l[0], l[1]
    if a == 1:
        set1.add(b)
    if b == N:
        set2.add(a)

if set1.isdisjoint(set2):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

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

L = [0 for i in range(N)]

for i in range(M):
	a, b = list(map(int, input().split()))
	if a == 1:
		L[b - 1] += 1
	elif b == 1:
		L[a - 1] += 1
	elif a == N:
		L[b - 1] += 1
	elif b == N:
		L[a - 1] += 1
	else:
		pass

if L.count(2) >= 1:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

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

is1 = [False] * (n + 1)
isN = [False] * (n + 1)

for i in range(m):
    a, b = map(int, input().split())
    if(a > b):
        a, b = b, a
    if(a == 1):
        is1[b] = True
    if(b == n):
        isN[a] = True

import sys

for i in range(2, n):
    if(is1[i] and isN[i]):
        print("POSSIBLE")
        sys.exit(0)

print("IMPOSSIBLE")

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

Solution (Python):
import sys
N,M=map(int,input().split())
table=[set() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].add(b)
for x in table[0]:
    if N-1 in table[x]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Solution (Python):
import sys
N,M=map(int,input().split())
table=[set() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].add(b)
for x in table[0]:
    if N-1 in table[x]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Solution (Python):
import sys
N,M=map(int,input().split())
table=[set() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].add(b)
for x in table[0]:
    if N-1 in table[x]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

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

f = False
for i in l[0]:
    for j in l[i]:
        if j == n-1:
            f = True
            break
if f:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
f = lambda: map(int,input().split())

n,m = f()
s = [[] for _ in range(n)]
for _ in range(m):
    a, b = f()
    a-=1; b-=1
    s[a].append(b); s[b].append(a)
for i in s[0]:
    if n-1 in s[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,M = inpl()
ed = defaultdict(lambda:False)
for i in range(M):
	a,b = inpl()
	if a == 1:
		if ed[b]:
			print('POSSIBLE')
			sys.exit()
		else:
			ed[b] = True
	elif b == N:
		if ed[a]:
			print('POSSIBLE')
			sys.exit()
		else:
			ed[a] = True

print('IMPOSSIBLE')

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *
from heapq import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N, M = reads()
edges = set()
for _ in range(M):
  a, b = reads()
  a, b = a-1, b-1
  edges.add((a, b))
  edges.add((b, a))

for k in range(N):
  if (0, k) in edges and (k, N-1) in edges:
    print("POSSIBLE")
    exit()

print("IMPOSSIBLE")

Solution (Python):

n,m = map(int,input().split())
a = []

for i in range(m):
    l = list(map(int,input().split()))
    if l[0] == 1:
        a.append(l[1])
    elif l[1] == n:
        a.append(l[0])

b = list(set(a))
if len(a)==len(b):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):

line = input().split()
n = int(line[0])
m = int(line[1])

path = [[] for _ in range(n)]
for _ in range(m):
    line = input().split()
    a = int(line[0])-1
    b = int(line[1])-1
    path[a].append(b)

def dfs(i, s):
    if i==n-1:
        if s==2:
            return True
        else:
            return False

    for e in path[i]:
        if dfs(e, s+1):
            return True
    return False

if dfs(0,0):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

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

stomid = [0]*n
midtog = [0]*n

for i in range(m):
	f,t = map(int,raw_input().split())
	if f == 1:
		stomid[t-1] = 1

	elif t == n:
		midtog[f-1] = 1 

for i in range(n):
	if stomid[i] == midtog[i] == 1 :
		print 'POSSIBLE'
		quit()

print 'IMPOSSIBLE'

Solution (Python):
n, m = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(set)
for i in range(m):
  a, b = list(map(int, input().split()))
  d[a].add(b)
  d[b].add(a)
if d[1]&d[n]:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

a = []
b = []
for i in range(m):
    aa,bb = list(map(int,input().split()))
    a.append(aa)
    b.append(bb)
c = []
d = []
for i in range(m):
    if a[i] == 1:
        c.append(b[i])
    elif a[i] == n:
        d.append(b[i])
    elif b[i] == n:
        d.append(a[i])

ans = 'IMPOSSIBLE'
c = set(c)
d = set(d)

if len(c&d) >= 1:
    ans = 'POSSIBLE'
print(ans)

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

pos=0
i=0
g=[0 for i in range(0,200000)]
e=[]
f=[]
k=0
l=0
while i < M and pos == 0:
	if a[i] == 1:
		g[b[i]] = 1
	if b[i] == 1:
		g[a[i]] = 1
	i=i+1
i=0
while i < M and pos == 0:
	if a[i] == N:
		if g[b[i]] == 1:
			pos=1
	if b[i] == N:
		if g[a[i]] == 1:
			pos=1
	i = i + 1
if pos == 1:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Solution (Python):
nm = list(map(int, input().split()))
ships = []
for i in range(nm[1]):
    ships.append(list(map(int, input().split())))

first = []
second = []

for i in ships:
    if(i[0] == 1):
        first.append(i[1])
    if(i[1] == nm[0]):
        second.append(i[0])

if(len(set(first) & set(second)) > 0):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

Solution (Python):
from sys import stdin


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ab = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
    ab1 = [b for a, b in ab if a == 1]
    ab2 = [a for a, b in ab if b == N]
    print('POSSIBLE' if len(set(ab1) & set(ab2)) else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
n,m = [int(x) for x in input().split()]
f = set()
t = set()
ans = False
for i in range(m):
  a,b = [int(x) for x in input().split()]
  if a == 1:
    f.add(b)
  if b == n:
    t.add(a)
for i in f:
  if i in t:
    ans = True
    break
if ans:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
def getinputdata():

    
    array_result = []
    
    data = input()
    
    array_result.append(data.split(" "))

    flg = True

    try:

        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:


        return array_result

arr_data = getinputdata()


n = arr_data[0][0]
m = int(arr_data[0][1])

arr01 = []
arr02 = []
for i in range(1, 1 + m):

    if arr_data[i][0] == "1":
        
        arr01.append(arr_data[i][1])

    if arr_data[i][1] == n:
        
        arr02.append(arr_data[i][0])


print("POSSIBLE" if len(list(set(arr01) & set(arr02))) == 1 else "IMPOSSIBLE")

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


ichi = set()
enu = set()

for _ in range(m):
	a, b = list(map(int, input().split()))
	if a == 1:
		ichi.add(b)
	elif a == n:
		enu.add(b)
	elif b == 1:
		ichi.add(a)
	elif b == n:
		enu.add(a)

if ichi & enu != set():
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
trans = {}
for i in range(1, N+1):
    trans[i] = set()
for _ in range(M):
    a, b = map(int, input().split())
    trans[a].add(b)
    trans[b].add(a)

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

Solution (Python):
from collections import defaultdict

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

R = defaultdict(set)

for i in range(M):
    a,b = map(int,input().split())
    R[a].add(b)
    
isok = False
for r in R[1]:
    if N in R[r]:
        isok = True
        break
        
if isok:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
def inpl(): return list(map(int, input().split()))
N, M = inpl()
f, n = set(), set()
for i in range(M):
    temp = inpl()
    if 1 in temp:
        f.add(temp[1])
    if N in temp:
        n.add(temp[0])
if len(f & n) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
def inpl(): return list(map(int, input().split()))
N, M = inpl()
f, n = [], []
for i in range(M):
    temp = inpl()
    if 1 in temp:
        f.append(temp[1])
    if N in temp:
        n.append(temp[0])
if len(set(f) & set(n)) > 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)
    if b==N:
        B.append(a)
if set(A)&set(B):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

Solution (Python):
import sys, math, itertools, collections, heapq
sys.setrecursionlimit(10 ** 7)
pinf = float("inf")
ninf = -float("inf")
n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)
ans = "IMPOSSIBLE"
n -= 1
for e in edge[0]:
    if n in edge[e]:
        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 or b==1:
    First.add(max(a,b))
  elif a==N or b==N:
    Second.add(min(a,b))

Ans= First & Second

if len(Ans):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
sb=[0]*(n+1)
db=[0]*(n+1)
for _ in range(m):
    s,d=map(int,input().split())
    if s==1:
        sb[d]=1
    if d==n:
        db[s]=1

for i in range(n):
    if sb[i]==1 and db[i]==1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):


import sys, math, copy




HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def main():
    n, m = map(int, input().split())
    edges = []
    for i in range(m):
        a, b = map(int, input().split())
        edges.append([a, b])
    from_one = set()
    from_n = set()
    for i in range(m):
        if edges[i][0] == 1:
            from_one.add(edges[i][1])
        if edges[i][1] == n:
            from_n.add(edges[i][0])
    common = from_one & from_n
    print("POSSIBLE" if len(common) > 0 else "IMPOSSIBLE")

main()

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

for i in range(m):
  temp = list(map(int, input().split()))
  ship[temp[0]-1].append(temp)

for i in range(len(ship[0])):
  now = ship[0][i]
  if [now[1], n] in ship[now[1]-1]:
    flag = True
    break

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

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

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

from1 = set()
gotoN = set()

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

	if b == 1:
		from1.add(a)
	elif b == N:
		gotoN.add(a)

res = from1 & gotoN

print("POSSIBLE" if len(res) > 0 else "IMPOSSIBLE")

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

from1 = []
gotoN = []

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

res = set(from1) & set(gotoN)

print("POSSIBLE" if len(res) > 0 else "IMPOSSIBLE")

Solution (Python):


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

from1 = []
gotoN = []

for m in range(M):
    a, b = list(map(int, input().split()))
    if a==1:
        from1.append(b)
    if b==N:
        gotoN.append(a)

can = set(from1) & set(gotoN)

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

Solution (Python):
[N, M] = [int(x) for x in input().split()]
list_all = []
for i in range(M):
	list_all.append([int(x) for x in input().split()])
	
list_mid = []
for i in range(M):
	if 1 in list_all[i]:
		list_mid.append(list_all[i][1])
	if N in list_all[i]:
		list_mid.append(list_all[i][0])

if len(list_mid) == len(set(list_mid)):
	print("IMPOSSIBLE")
else:
	print("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 == 1:
        f.add(b)
    elif a == N:
        t.add(b)
    if b == 1:
        f.add(a)
    elif b == N:
        t.add(a)
 
pos = "IMPOSSIBLE"
 
if f&t:
    pos = "POSSIBLE"
 
print(pos)

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

f = dict()
for i in range(m):
    a, b = map(int, raw_input().split())
    if a in f:
        f[a].append(b)
    else:
        f[a] = [b]
if m < 2:
    print("IMPOSSIBLE")
    exit()

for k, v in f.iteritems():
    if k == 1:
        for vv in v:
            if vv not in f:
                continue
            if n in f[vv]:
                print("POSSIBLE")
                exit()
print("IMPOSSIBLE")

Solution (Python):


N, M = map(int, raw_input().split())
a = []
for i in xrange(M):
    a.append(map(int, raw_input().split()))

s1=set()
s2=set()
for i in xrange(M):
    if a[i][0]==1:
        s1.add(a[i][1])
    if a[i][1]==N:
        s2.add(a[i][0])
if s1 & s2:
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'

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

probInit = set([])
probEnd  = set([])

for i in range(m):
    edge = input().split(" ")
    if edge[0] == "1":
        probInit.add(edge[1])

    if edge[1] == str(n):
        probEnd.add(edge[0])

sec = probEnd.intersection(probInit)
if (len(sec) == 0):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

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

if len(ls[1]) == 0:
    print('IMPOSSIBLE')
    sys.exit()

for i in ls[1]:
    if (N in ls[i]):
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

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

from_1 = [0 for i in range(N)]
to_N = [0 for i in range(N)]

for f in ferry:
    if f[0]==1:
        from_1[f[1]-1] = 1
    if f[1]==N:
        to_N[f[0]-1] = 1


flag = 0

for k in range(N):
    if from_1[k]==1 and to_N[k]==1:
        print('POSSIBLE')
        flag = 1
        break

if flag==0:
    print('IMPOSSIBLE')

Solution (Python):

import sys
N, M = map(int, input().split())
A = [ 0 for tmp in range(N) ]
B = [ 0 for tmp in range(N) ]
for tmp in range(M):
    a, b = map(int, input().split())
    if a == N or b == N:
        c = a if a != N else b
        B[c-1] = 1
    if a == 1 or b == 1:
        c = a if a != 1 else b
        A[c-1] = 1

for tmp in range(N):
    if A[tmp] and B[tmp]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Solution (Python):
n, m = [int(s) for s in raw_input().split(" ")]
routes = []
for i in xrange(m):
    routes.append([int(s) for s in raw_input().split(" ")])
x = set([r[1] for r in routes if r[0] == 1])
y = set([r[0] for r in routes if r[1] == n])
print "POSSIBLE" if x & y else "IMPOSSIBLE"

Solution (Python):
[n, m] = [int(num) for num in input().split()];
a = [];
b = [];

for i in range(m):
	[t1, t2] = [int(num) for num in input().split()];
	a.append(t1);
	b.append(t2);

start = [];
end = [];
for i in range(n):
	start.append(False);
	end.append(False);
	
for i in range(m):
	if a[i] == 1:
		start[b[i]] = True;
	elif b[i] == n:
		end[a[i]] = True;
		
flag = False;
for i in range(n):
	if start[i] & end[i]:
		flag = True;
		
if flag:
	print('POSSIBLE');
else:
	print('IMPOSSIBLE');

Solution (Python):
n,m=map(int,raw_input().split())
g=[[] for i in range(2*10**5+1)]
for i in range(m):
	a,b=map(int,raw_input().split())
	g[a].append(b)
	g[b].append(a)
for i in g[1]:
	for j in g[i]:
		if j==n:
			print "POSSIBLE"
			exit(0)
print "IMPOSSIBLE"

Solution (Python):
n,m=map(int,raw_input().split())
g=[[] for i in range(2*10**5+1)]
for i in range(m):
	a,b=map(int,raw_input().split())
	g[a].append(b)
	g[b].append(a)
for i in g[1]:
	for j in g[i]:
		if j==n:
			print "POSSIBLE"
			exit(0)
print "IMPOSSIBLE"

Solution (Python):
n, m = [int(x) for x in input().split()]

s = [0]*(n+1)
d = [0]*(n+1)

for i in range(m):
	a, b = [int(x) for x in input().split()]
	if a == 1:
		s[b] = 1
		if d[b] == 1:
			print('POSSIBLE')
			break
	elif b == n:
		d[a] = 1
		if s[a] == 1:
			print('POSSIBLE')
			break
else:
	print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
_1, _n = set(), set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        _1.add(b)
    elif b == n:
        _n.add(a)
print('POSSIBLE' if _1 & _n else 'IMPOSSIBLE')

Solution (Python):


n,m=map(int,raw_input().split())
l=[]
for i in xrange(m):
 a,b=map(int,raw_input().split())
 l.append([a,b])
s1=set()
s2=set()
for i in xrange(m):
 if l[i][0]==1:
  s1.add(l[i][1])
 if l[i][1]==n:
  s2.add(l[i][0])
if s1&s2:
 print 'POSSIBLE'
else:
 print 'IMPOSSIBLE'

Solution (Python):
n,m,*T=map(int,open(0).read().split());*S,=zip(T[::2],T[1::2]);s=lambda e:set(s[e<2]for s in S if e in s);print("IM"*(len(s(1)&s(n))<1)+"POSSIBLE")

Solution (Python):
if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    a = []
    b = []
    for i in range(M):
        tmp_a, tmp_b = list(map(int, input().split()))
        a.append(tmp_a)
        b.append(tmp_b)

    c = set([b[i] for i in range(0, M) if a[i] == 1])

    for i in range(0, M):
        if a[i] in c and b[i] == N:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")

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 == 1:
        f.add(b)
    elif a == N:
        t.add(b)
    if b == 1:
        f.add(a)
    elif b == N:
        t.add(a)

pos = "IMPOSSIBLE"

if f&t:
    pos = "POSSIBLE"

print(pos)

Solution (Python):
from sys import stdin
n,m = map(int,stdin.readline().split())
ans = 'IMPOSSIBLE'
di = set()
for i in xrange(m):
 x,y = map(int,stdin.readline().split())
 di.add((min(x,y),max(x,y)))
for i in xrange(2,n):
 fir = (1,i)
 sec = (i,n)
 if fir in di and sec in di:
  ans = 'POSSIBLE'; break
print ans

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

ax = []
bx = []
for _ in xrange(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        bx.append(b)
    if b == N:
        ax.append(a)
if len(set(ax) & set(bx)) > 0:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"

Solution (Python):
def f():
    n,m = map(int,input().split(" "))
    s = []
    w = [[] for i in range(n+2)]
    for i in range(m):
        a,b = map(int,input().split(" "))
        
        if a==1:
            s.append(b)
        if b==1:
            s.append(a)
        w[a].append(b)
        w[b].append(a)
    for i in s:
        if n in w[i]:
            print("POSSIBLE")
            return 0
    print("IMPOSSIBLE")
    return 0
f()

Solution (Python):
n,m=map(int,input().split())
s=[False]*200001
g=[False]*200001
r='POSSIBLE'
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        if g[b]:
            break
        s[b]=True
    elif b==n:
        if s[a]:
            break
        g[a]=True
else:
    r='IMPOSSIBLE'
print(r)

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

one_to_routes = set()
other_routes_contains_N = set()

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

    if a == 1:
        one_to_routes.add(b)
    elif b == N:
        other_routes_contains_N.add(a)

if one_to_routes.isdisjoint(other_routes_contains_N):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
def main():
    n, m = list(map(int, input().split(' ')))

    mid1 = [False]*(n+1)
    mid2 = [False]*(n+1)

    for _ in range(m):
        a, b = list(map(int, input().split(' ')))
        if a == 1:
            mid1[b] = True
        if b == n:
            mid2[a] = True

    for i in range(n+1):
        if mid1[i] and mid2[i]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

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

n, m = map(int,input().split())
from1 = [0]*(n+1)
ton = [0]*(n+1)
for i in range(m):
    a, b = map(int,input().split())
    if a == 1: from1[b] = 1
    if b == n: ton[a] = 1
for i in range(n+1):
    if from1[i] and ton[i]:
        print("POSSIBLE")
        break
else: print("IMPOSSIBLE")

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

A = set({})
B = set({})
for j in range(M):
    tmp = []
    tmp = [int(i) for i in input().split()]
    if tmp[0] == 1:
        A.add(tmp[1])
    elif tmp[1] == N:
        B.add(tmp[0])

if len(A.intersection(B)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict as dd
def main():
    N, M = map(int, input().split())

    D = dd(list)

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

    for d in D[0]:
        if N-1 in D[d]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
        

if __name__ == "__main__":
    
    
    main()

Solution (Python):
n, m = map(int, raw_input().split())
paths = []
for _ in xrange(m):
	a, b = map(int, raw_input().split())
	paths.append((a, b))
hop2 = set()
for a, b in paths:
	if a == 1:
		hop2.add(b)
flag = 0
for a, b in paths:
	if a in hop2:
		if b == n:
			flag = 1
			break

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

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

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

if route_1&route_N:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

def step(step_num, n, path, reachable):
    reachable[n] = 1
    step_num += 1

    if step_num > 2:
        return
    if not n in path:
        return

    for b in path[n]:
        if reachable[b]:
            continue
        step(step_num, b, path, reachable)

path = {}
for i in range(M):
    a, b = map(int, input().split())
    if a in path:
        path[a].append(b)
    else:
        path[a] = [b]

reachable = [0] * (N + 1)
step(0, 1, path, reachable)

if reachable[N] == 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')