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):
class Node:
    def __init__(self):
        pass

class Edge:
    def __init__(self,edge,cost=1):
        self.node_from=edge[0]
        self.node_to=edge[1]
        self.cost=cost

    def add_node(self,node):
        self.nodes.append(node)

class myGraph:

    def __init__(self):
        self.adj={}
        self.nodes={}

    def add_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)

        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        
        self.adj[u][v] = cost
        self.adj[v][u] = cost

    def add_directed_edge(self,edge,cost):
        if len(edge)==1:
            edge=list(edge)


        u,v=edge[0],edge[1]

        if u not in self.nodes:
            self.adj[u] = {}
            self.nodes[u] = {}

        if v not in self.nodes:
            self.adj[v] = {}
            self.nodes[v] = {}

        self.adj[u][v] = cost

    def get_edges_from(self,node):
        return [(self.adj[node][nn],node,nn) for nn in self.adj[node]]


    def makeEdgeobj(self):
        edges=[]
        for sn in self.nodes:
            for e in self.get_edges_from(sn):
                edges.append(Edge([e[1],e[2]],e[0]))

        return edges

    def _add(self,edges,add_edges):
        for e in add_edges:
            hq.heappush(edges,e)
        return edges

    def bermn_ford(self,start,init=0):

        nodes=self.nodes
        dists={}
        for n in nodes:
            dists[n]=float("inf")

        dists[start]=init
        edges=self.makeEdgeobj()

        for i in range(len(nodes)):
            update=False
            for k in range(len(edges)):
                e=edges[k]
                if  dists[e.node_from]!=float("inf") and dists[e.node_to]>dists[e.node_from]+e.cost:
                    dists[e.node_to]=dists[e.node_from]+e.cost
                    update=True

            if i==len(nodes)-1:
                return False

            if not update:
                break

        return dists


    def dijkstra(self,start, goal=None):
        import heapq
        '''
            get minimum cost
        '''

        N = len(self.adj)          
        
        dist = {k:float('inf') for k in self.nodes}
        

        dist[start] = 0
        visited = []

        koho=[]
        heapq.heappush(koho,(0,start))

        vtx=list(self.nodes)
        vtx.remove(start)

        while len(koho)!=0:
            d,mini=heapq.heappop(koho)

            if d>2:
                break

            if dist[mini]<d:
                continue


            for k in list(self.adj[mini]):
                cost=self.adj[mini][k]
                if cost != float('inf') and dist[k]>dist[mini]+cost:
                    dist[k]=dist[mini]+cost
                    heapq.heappush(koho,(dist[k],k))
                    

        return dist




def spaceinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))

if __name__=="__main__":
    n,m=spaceinput()
    g=myGraph()

    for i in range(10**6):
        try:
            ss=spaceinput()
            if not ss:
                break
        except:
            break

        g.add_edge((ss[0],ss[1]),1)
    res=g.dijkstra(start=1)
    
    if n in res and res[n]<=2:
        if res[n]==1:
            if len(set(g.adj[1]).union(g.adj[n]))>0:
                print("POSSIBLE")
            else:
                print("IMPOSSIBLE")
        else:
            print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Solution (Python):


N, M = [int(n) for n in input().split()]
islands = {n:[] for n in range(1, N+1)}
result = "IMPOSSIBLE"

for m in range(M):
    a, b = [int(n) for n in input().split()]
    islands[a].append(b)
    islands[b].append(a)

ok_isl = set()
search_isl = [1]
next_isl = set()

loop = True
for x in range(2):
    for i in search_isl:
        if N in islands[i]:
            loop = False
            result = "POSSIBLE"            
        else:
            next_isl.update(islands[i])
    
    ok_isl = ok_isl.union(search_isl)
    
    search_isl = next_isl.difference(ok_isl)
    if len(search_isl) == 0:
        break

print(result)

Solution (Python):
import sys
N,M=map(int,input().split())
come=[0]*N
for i in range(M):
  ab=list(map(int,input().split()))
  if ab[0]==1:
    if come[ab[1]]:
      print("POSSIBLE")
      sys.exit()
    come[ab[1]]=1
  if ab[1]==N:
    if come[ab[0]]:
      print("POSSIBLE")
      sys.exit()
    come[ab[0]]=1
 
print("IMPOSSIBLE")

Solution (Python):


def main():
    N, M = map(int, input().split())
    A = []
    B = []
    d = {}

    for i in range(M):
        a, b = sorted(map(int, input().split()))
        if b in d:
            d[b] += [a]
        else:
            d[b] = [a]
    q = [N]
    cnt = 3
    while q and cnt > 0:
        cnt -= 1
        p = q
        q = []
        for i in p:
            if i == 1:
                print('POSSIBLE')
                return
            if i in d:
                q += d[i]
    print('IMPOSSIBLE')
    return
        
if __name__ == '__main__':
    main()

Solution (Python):
a=[0]*(200001)


N = list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(N[1])]


for i in x:
    if i[0]==1 :
        if a[i[1]]==1:
            print('POSSIBLE')
            quit()
        a[i[1]]=1
    if i[1]==N[0]:
        if a[i[0]]==1:
            print('POSSIBLE')
            quit()
        a[i[0]]=1

print('IMPOSSIBLE')
quit()

Solution (Python):


def main():
    N, M = map(int, input().split())
    ships = set()
    for _ in range(M):
        a, b = map(int, input().split())
        ships.add((a, b))
        ships.add((b, a))
    for i in range(2, N):
        if (1, i) in ships and (i, N) in ships:
            return "POSSIBLE"
    else:
        return "IMPOSSIBLE"


print(main())

Solution (Python):
import sys
import numpy as np
from collections import deque
import copy

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    connect_to_1_set = set([])
    connect_to_N_set = set([])
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] = [int(input_raw[0]), int(input_raw[1])]
        if a == 1:
            connect_to_1_set.add(b)
        elif b == 1:
            connect_to_1_set.add(a)

        if a == N:
            connect_to_N_set.add(b)
        elif b == N:
            connect_to_N_set.add(a)

    if len(connect_to_1_set & connect_to_N_set) == 0:
        print "IMPOSSIBLE"
    else:
        print "POSSIBLE"



if __name__ == '__main__':
    main()

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):
def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def ris(): return list(input())
def pli(a): return "".join(list(map(str, a)))

N, M = rli()
keiro = [[False for i in range(2)] for j in range(N+1)]
for i in range(M):
    a, b = rli()
    if(b == 1 or b == N):
        keiro[a][1 if b == 1 else 0] = True
    elif(a == 1 or a == N):
        keiro[b][1 if a == 1 else 0] = True

flag = False
for i in range(2, N):
    if(keiro[i][1] and keiro[i][0]):
        flag = True
if(flag):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import collections
import sys

INF = sys.maxsize // 2


def solve(num_vs, adj_list, source, dest):
    visited = [False for _ in range(num_vs)]
    dist = [INF for _ in range(num_vs)]
    q = collections.deque()
    dist[source] = 0
    q.append(source)
    while q:
        s = q.popleft()
        if s == dest:
            return dist[dest] == 2
        for t in adj_list[s]:
            if not visited[t]:
                visited[t] = True
                q.append(t)
                dist[t] = dist[s] + 1
    return False


def main():
    n, m = (int(x) for x in input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        a, b = (int(x) - 1 for x in input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    res = solve(n, adj_list, 0, n - 1)
    print("POSSIBLE" if res else "IMPOSSIBLE")


if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int, raw_input().split())
aa = set()
bb = set()
for _ in range(m):
  a,b = map(int, raw_input().split())
  a,b = min(a,b),max(a,b)
  if a == 1:
    aa.add(b)
  if b == n:
    bb.add(a)
for i in range(1,n+1):
  if i in aa and i in bb:
    print 'POSSIBLE'
    exit()
print 'IMPOSSIBLE'

Solution (Python):
import bisect

ans = "IMPOSSIBLE"
n, m = map(int, input().split())
ac = []
bc = []
for _ in range(m):
    a, b = map(int, input().split())
    if min(a, b) == 1:
        ac.append(max(a, b))
    elif max(a, b) == n:
        bc.append(min(a, b))
ac = list(sorted(ac))
bc = list(sorted(bc))
for c in ac:
    i = bisect.bisect_left(bc, c)
    if i < len(bc) and bc[i] == c:
        ans = ans[2:]
        break
print(ans)

Solution (Python):




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

for i in range(m):
    u,v=map(int,input().split())
    if u==1:
        a.add(v)
    if v==n:
        b.add(u)

    

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

Solution (Python):
import sys
from collections import Counter




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


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


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


def read_str():
    return input()


def solve():
    possible = 'POSSIBLE'
    impossible = 'IMPOSSIBLE'
    n, m = read_int_list()
    c = Counter()
    res = impossible
    for i in range(m):
        a, b = read_int_list()
        if a == 1:
            c[b] += 1
        if b == n:
            c[a] += 1
        if c[a] == 2 or c[b] == 2:
            res = possible
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
import math

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


Ss = set()
Es = set()
for _ in range(M):
    a_orig, b_orig = list(map(int, sys.stdin.readline().rstrip().split()))
    for a, b in [(a_orig, b_orig), (b_orig, a_orig)]:
        if a== 1:
            Ss.add(b)
        if a == N:
            Es.add(b)

if len(Ss.intersection(Es)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
exit(0)

Solution (Python):
n, m = map(int, input().split())
one = [0 for i in range(n + 1)]
edges = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        one[b] = 1
    if b == 1:
        one[a] = 1
    else:
        edges.append((a, b))
for a, b in edges:
    if one[a] and b == n or one[b] and a == n:
        print('POSSIBLE')
        exit(0)
print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
for e in edges[0]:
    if any(c == N - 1 for c in edges[e]):
        print("POSSIBLE")
        quit()
print("IMPOSSIBLE")

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

memo = [False]*N
result = False

for i in range(M):
  a,b = map(int, input().split())
  if a == 1:
    result |= memo[b]
    memo[b] = True
  elif b == N:
    result |= memo[a]
    memo[a] = True

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

Solution (Python):

from collections import defaultdict

INF = 10 ** 20
MOD = 10 ** 9 + 7


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


def read():
    N, M = ILI()
    edges = defaultdict(list)
    for __ in range(M):
        a, b = ILI()
        edges[a].append(b)
        edges[b].append(a)
    return N, M, edges


def solve(N, M, edges):
    s_from_1 = set(edges[1])
    s_from_n = set(edges[N])
    set_and = s_from_1 & s_from_n
    ans = ""
    if len(set_and) == 0:
        ans = "IMPOSSIBLE"
    else:
        ans = "POSSIBLE"
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Solution (Python):

import numpy as np
N, M = map(int, input().split())

alpha = np.zeros(N+1)
omega = np.zeros(N+1)

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        alpha[b] = 1
    if b == N:
        omega[a] = 1
        
if (alpha*omega).sum() > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
E1 = set()
EN = set()
for n in range(M):
    a, b = map(int, input().split())
    if a == 1:
        E1.add(b)
    if b == 1:
        E1.add(a)
    if a == N:
        EN.add(b)
    if b == N:
        EN.add(a)
for a in E1:
    if a in EN:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys

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

a = [0] * (n + 1)
for _ in xrange(m):
	x, y = map(int, raw_input().split())
	if x > y:
		x, y = y, x
	if x == 1:
		a[y] += 1
	if y == n:
		a[x] += 1
for i in xrange(2, n):
	if a[i] == 2:
		print "POSSIBLE"
		sys.exit(0)
print "IMPOSSIBLE"

Solution (Python):
n, m = [int(_) for _ in raw_input().split()]
s = set()
e = set()
for i in xrange(m):
    a, b = [int(_) for _ in raw_input().split()]
    if a == 1:
        e.add(b)
    if b == n:
        s.add(a)

if s & e:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"

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

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

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()
    a = [LI() for _ in range(M)]
    t = set()
    s = set()
    for i,j in a:
        if i==1:
            t.add(j)
        elif i==N:
            s.add(j)
        if j==1:
            t.add(i)
        elif j==N:
            s.add(i)
    if t&s:
        return 'POSSIBLE'

    return 'IMPOSSIBLE'



print(main())