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())
AB = [list(map(int, input().split())) for _ in range(M)]
res = []
for a, b in AB:
    if a == 1:
        res.append(b)
    if b == N:
        res.append(a)
print('IMPOSSIBLE' if len(res) == len(set(res)) else 'POSSIBLE')

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

Solution (Python):
from collections import deque

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

ok = False
for v in G[0]:
    s = G[v]
    if n-1 in s:
        ok = True

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

Solution (Python):

"""
Created on Sun Sep 27 02:05:32 2020

@author: liang
"""

N, M = map(int, input().split())
first = list()
second = set()

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        first.append(b)
    if b == N:
        second.add(a)
        
for a in first:
    if a in second:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
import heapq
import sys
input = lambda :sys.stdin.readline().rstrip()

def INPUT(mode=int):
    return list(map(mode, input().split()))

def Dijkstra_heap(s, edge):
    
    d = [10**20] * n
    used = [False] * n
    d[s] = 0
    used[s] = True
    edgelist = []
    for i, j in edge[s]:
        heapq.heappush(edgelist, i+j*(10**6))
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        v = minedge % (10**6)
        
        if used[v]: continue
        d[v] = minedge // (10**6)
        used[v] = True
        for e in edge[v]:
            if not used[e[0]]:
                heapq.heappush(edgelist, e[0]+(e[1]+d[v]) * (10**6))
    return d

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

dist = Dijkstra_heap(0, edge)
if dist[-1] <= 2:
  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:
    B.append(b)
  if b == N:
    A.append(a)

if len(set(A) & set(B)) != 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

re = [[] for i in range(n+1)]
for i in range(m):
  a,b = map(int, input().split())
  re[a].append(b)
  re[b].append(a)
  
reach = [0]*(n+1)
reach[1] = 1
for i in re[1]:
  if reach[i] == 0:
    for j in re[i]:
      reach[j] = 1

if reach[n] == 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):

def main():
    n, m = map(int, input().split())
    li = [0]*200001

    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            if li[b] == 0:
                li[b] = 1
            else:
                print('POSSIBLE')
                exit()
        if b == n:
            if li[a] == 0:
                li[a] = 1
            else:
                print('POSSIBLE')
                exit()
    else:
        print('IMPOSSIBLE')

if __name__ ==  "__main__":
    main()

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

print(s)

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

c = []
d = []

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

for i in range(M):
    if b[i] == N:
        d.append(a[i])

e = set(c) & set(d)

if len(e) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

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

K = [-1] * N
def dfs(now,time):
    K[now] = time
    for i in ki[now]:
        time += 1
        dfs(i,time)
        time -= 1

dfs(0,0)
print('POSSIBLE' if K[N-1] == 2 else 'IMPOSSIBLE')

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




pot_starts = []
pot_ends = []

for i in a:
    if i[0] == 1:
        pot_starts.append(i[1])
    elif i[1] == n:
        pot_ends.append(i[0])

if set(pot_starts).intersection(set(pot_ends)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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




pot_starts = []
pot_ends = []

for i in a:
    if i[0] == 1:
        pot_starts.append(i[1])
    elif i[1] == n:
        pot_ends.append(i[0])

if set(pot_starts).intersection(pot_ends):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
X = [list(map(int,input().split())) for i in range(m)]
a_list = []
b_list = []
for i in range(m):
  if X[i][0] == 1:
    a_list.append(X[i][1])
  elif X[i][1] == n:
    b_list.append(X[i][0])
c_set = set(a_list) & set(b_list)
if len(c_set) ==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Solution (Python):


def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    ans = "IMPOSSIBLE"
    list_1 = []
    list_n = []
    for i in range(m):
        if ab[i][0] == 1:
            list_1.append(ab[i][1])
        elif ab[i][1] == n:
            list_n.append(ab[i][0])
    if len(set(list_1) & set(list_n)) > 0:
        ans = "POSSIBLE"
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

N, M = [int(i) for i in input().split()]
map = {k: [] for k in range(1, N + 1)}

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


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


print('IMPOSSIBLE')

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

for i in range(m):
  a, b = map(int, input().split())
  if a == 1:
    a1.append(b)
  elif b == n:
    bn.append(a)
la = len(a1)
lb = len(bn)
sa = set(a1)
sb = set(bn)
if len(sa | sb) < la + lb:
  print('POSSIBLE')
  exit()
print('IMPOSSIBLE')

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

print('IMPOSSIBLE')

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

N,M = map(int,readline().split())
G = [[] for i in range(N)]

for i in range(M):
  a,b = map(int,readline().split())
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  
for child in G[0]:
  for gchild in G[child]:
    if gchild == N - 1:
      print("POSSIBLE")
      exit(0)
print("IMPOSSIBLE")

Solution (Python):
def main():
    n, m = map(int, input().split())
    ab_lst = []
    for i in range(m):
        ab_lst.append(list(map(int, input().split())))

    flag = False
    lst = []
    for i in range(m):
        a = ab_lst[i][0]
        b = ab_lst[i][1]

        if a == 1:
            lst.append(b)
    st = set(lst)

    for i in range(m):
        a = ab_lst[i][0]
        b = ab_lst[i][1]

        if b == n:
            if a in st:
                flag = True
                break

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


if __name__ == '__main__':
    main()

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

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

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

possible = False
for to in edge[0]:
    if n-1 in edge[to]:
        possible = True
        break

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

Solution (Python):









import os
import sys


from collections import deque


def main():
    N, M = map(int, input().split())
    path = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    Q = deque(path[1])
    flag = False
    while Q and flag is False:
        u = Q.popleft()
        for v in path[u]:
            if v == N:
                flag = True
    if flag:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == "__main__":
    main()

Solution (Python):
import typing
from typing import Deque, Set, Dict

class Island:
    def __init__(self, id: int) -> None:
        self.id: int = id
        self.connection: List['Island'] = []
        self.rank: int = 0
    
    def addConnection(self, other: 'Island') -> None:
        self.connection.append(other)
        other.connection.append(self)

    def setRank(self, other: 'Island') -> None:
        self.rank = other.rank +1

class Islands(Dict[int, Island]):
    def __init__(self, num: int):
        for id in range(1, num+1):
            self[id] = Island(id)

def bfs(root: Island, max_depth: int) -> None:
    reserved: Deque[Island] = Deque([root])
    seen: Set[int] = {root.id}
    while len(reserved) != 0:
        current: Island = reserved.popleft()
        if current.rank > max_depth:
            break
        for connected in current.connection:
            if connected.id in seen:
                continue
            connected.setRank(current)
            seen.add(connected.id)
            reserved.append(connected)

def main() -> None:
    with open(0) as f:
        N, M = map(int, f.readline().split())
        ab = [map(int, line.split()) for line in f.readlines()]
    
    islands: Islands = Islands(N)
    
    for a, b in ab:
        islands[a].addConnection(islands[b])
    
    bfs(islands[1], 2)
    
    print('POSSIBLE' if islands[N].rank in (1, 2) else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
import typing
from typing import Deque, Set, Dict

class Island:
    def __init__(self, id: int) -> None:
        self.id: int = id
        self.connection: List['Island'] = []
        self.parent: 'Island' = None
        self.rank: int = 0
    
    def addConnection(self, other: 'Island') -> None:
        self.connection.append(other)
        other.connection.append(self)

    def setAsRoot(self):
        self.parent = self
    
    def setParent(self, other: 'Island') -> None:
        self.parent = other
        self.rank = other.rank +1

class Islands(Dict[int, Island]):
    def __init__(self, num: int):
        for id in range(1, num+1):
            self[id] = Island(id)

def bfs(root: Island, max_depth: int) -> None:
    root.setAsRoot()
    reserved: Deque[Island] = Deque([root])
    seen: Set[int] = {root.id}
    while len(reserved) != 0:
        current: Island = reserved.popleft()
        if current.rank > max_depth:
            break
        for connected in current.connection:
            if connected.id in seen:
                continue
            connected.setParent(current)
            seen.add(connected.id)
            reserved.append(connected)

def main() -> None:
    with open(0) as f:
        N, M = map(int, f.readline().split())
        ab = [map(int, line.split()) for line in f.readlines()]
    
    islands: Islands = Islands(N)
    
    for a, b in ab:
        islands[a].addConnection(islands[b])
    
    bfs(islands[1], 2)
    
    print('POSSIBLE' if islands[N].rank in (1, 2) else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
N,M=map(int,input().split())
G=[list() for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
G[0].sort()
G[N-1].sort()
i=0
j=0
while i<len(G[0]) and j<len(G[N-1]):
    if G[0][i]==G[N-1][j]:
        print("POSSIBLE")
        break
    elif G[0][i]<G[N-1][j]:
        i+=1
    else:
        j+=1
else:
    print("IMPOSSIBLE")

Solution (Python):
N,M = map(int, input().split())
L = [list(map(int,input().split())) for _ in range(M)]
L.sort(key=lambda x: x[0])
funes1 = [False]*N
for a,b in L:
    if a == 1:
        funes1[b] = True
    else:
        if funes1[a]:
            if b == N:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')

Solution (Python):


import sys

YES = "POSSIBLE"  
NO = "IMPOSSIBLE"  


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    AB = sorted(zip(a, b))
    s = set([b for a, b in AB if a == 1])
    g = set([a for a, b in AB if b == N])
    return YES if s & g else NO


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    print(solve(N, M, a, b))

def test():
    import doctest
    doctest.testmod()

def perf():
    import cProfile
    cProfile.run("main()")

if __name__ == '__main__':
    
    
    main()

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

dic = {}
for (a, b) in ab:
  if a in dic.keys():
    dic[a].append(b)
  else:
    dic[a] = [b]
  
check = False
for i in dic[1]:
  if i in dic.keys():
    for j in dic[i]:
      if j == N:
        check = True

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

Solution (Python):
n, m = map(int, input().split())
root_map = dict()
root_map[1] = set()
root_map[n] = set()

for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or a == n:
        root_map[a].add(b)
    if b == 1 or b == n:
        root_map[b].add(a)

if root_map[1] & root_map[n]:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
root_map = dict()
root_map[1] = set()
root_map[n] = set()

for i in range(m):
    a, b = map(int, input().split())
    if a == 1 or a == n:
        root_map[a].add(b)
    if b == 1 or b == n:
        root_map[b].add(a)

for i in root_map[1]:
    if i in root_map[n]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
root_map = dict()
root_map[1] = set()
root_map[n] = set()

for i in range(m):
    a, b = map(int, input().split())
    if a not in root_map:
        root_map[a] = set()
        root_map[a].add(b)
    else:
        root_map[a].add(b)
    if b not in root_map:
        root_map[b] = set()
        root_map[b].add(a)
    else:
        root_map[b].add(a)

for i in root_map[1]:
    if i in root_map[n]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

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

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n,m = i_map()
    s = set()
    g = set()

    for _ in range(m):
        a,b = i_map()
        if a == 1:
            s.add(b)
        elif b == 1:
            s.add(a)
        elif a == n:
            g.add(b)
        elif b == n:
            g.add(a)

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

if __name__=="__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
L = [list(map(int, input().split())) for i in range(M)]
s = []
g = []
for i in range(M):
    if 1 == L[i][0]:
        s.append(L[i][1])
    if 1 == L[i][1]:
        s.append(L[i][0])
        
for i in range(M):
    if N == L[i][0]:
        g.append(L[i][1])
    if N == L[i][1]:
        g.append(L[i][0])
        
if set(g)&set(s):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right 
from heapq import heapify, heappop, heappush
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1

N,M = mint()
ship = [set() for _ in range(N+1)]
for _ in range(M):
    a,b = mint()
    ship[a].add(b)
    ship[b].add(a)
ans = False
for a in ship[1]:
    if N in ship[a]:
        ans = True
        break
judge(ans,['POSSIBLE','IMPOSSIBLE'])

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial

from functools import reduce
from pprint import pprint
from statistics import mean,median,mode
import sys
sys.setrecursionlimit(10 ** 6)

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

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

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]







n,m = MI()
ab = LI(m)

ls_s = []
ls_e = []
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    if a==1:
        ls_s.append(b)
    elif b==n:
        ls_e.append(a)

ls = set(ls_s) & set(ls_e)
if len(ls)!=0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys
input=sys.stdin.readline
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Solution (Python):
import sys
def ipnput():
    return sys.stdin.readline()[:-1]
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Solution (Python):
import sys
def ipnput():
    return sys.stdin.readline()[:-1]
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Solution (Python):
import sys
input = sys.stdin.readline
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

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

f=1
for i in range(2,n+1):
    if edg1[i]==1 and edgn[i]==1:
        f=0
print("POSSIBLE" if f==0 else "IMPOSSIBLE")

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

Solution (Python):
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Solution (Python):
from _collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    edg[a].append(b)
    edg[b].append(a)
dep=[-1]*(n+1)
dep[1]=0
data=deque([1])
while len(data)>0:
    p=data.popleft()
    for i in edg[p]:
        if dep[i]==-1:
            dep[i]=dep[p]+1
            data.append(i)
print("POSSIBLE" if dep[n]==2 else "IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
l = [[] for i in range(n)]
ab.sort()
for i in range(m):
    x = ab[i]
    l[x[0]-1].append(x[1]-1)
    l[x[1]-1].append(x[0]-1)
for i in l[0]:
    if n-1 in l[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,M = MI()
d1 = {}  
d2 = {}  
for i in range(1,N+1):
    d1[i] = 0
    d2[i] = 0
for _ in range(M):
    a,b = MI()
    if a == 1:
        d1[b] = 1
    if b == N:
        d2[a] = 1
for i in d1.keys():
    if d1[i] == d2[i] == 1:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
from collections import defaultdict

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

g = defaultdict(list)

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

visited = [False]*n

q = [0]
visTime = 0
Found = False
while q and visTime < 2:
    
    nL = []
    for vert in q:
        visited[vert] = True
        for v in g[vert]:
            if v == n-1:
                Found = True
                break
            if not visited[v]:
                nL.append(v)
    if Found:
        break
    q = nL
    visTime += 1
    
print('POSSIBLE' if Found else 'IMPOSSIBLE')

Solution (Python):
from collections import deque


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

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

def main():
    dist = [-1] * N
    dist[0] = 0
    que = deque([0])
    
    while que:
        v = que.popleft()
        for nv in to[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                que.append(nv)
                
    print('POSSIBLE' if dist[N - 1] == 2 else 'IMPOSSIBLE')
    
    
if __name__ == '__main__':
    main()

Solution (Python):

from collections import deque
N,M = map(int,input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)


dist = [-1]*N
que = deque([])


dist[0] = 0
que.append(0)

while (len(que) != 0):
    v = que.popleft()
    for next_v in G[v]:
        if (dist[next_v] != -1):
            continue
        
        dist[next_v] = dist[v] + 1
        que.append(next_v)
        
if dist[N-1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
from collections import deque
n, m = map(int, input().split())
E = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
dis = [200000 for i in range(n)]
dis[0] = 0
Q = deque([0])
while Q:
    now = deque.popleft(Q)
    for i in E[now]:
        if dis[i] == 200000:
            dis[i] = dis[now]+1
            deque.append(Q, i)
print("POSSIBLE" if dis[-1] == 2 else "IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
voyage = [set() for i in range(n+1)]
for i in range(m):
  a,b = map(int,input().split())
  voyage[a].add(b)
  voyage[b].add(a)
ans = 0
for v in voyage[1]:
  if v in voyage[n]:
    ans = 1
print('POSSIBLE' if ans else 'IMPOSSIBLE')

Solution (Python):
import collections
[n,m] = [int(i) for i in input().split()]
dic = collections.defaultdict(int)
for i in range(m):
  [a,b] = [int(j)-1 for j in input().split()]
  if a == 0:
    dic[b] += 1
  elif b == n-1:
    dic[a] += 1
if max(dic.values()) >= 2:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):



import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 2
1 2
2 3"""
        output = """POSSIBLE"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 3
1 2
2 3
3 4"""
        output = """IMPOSSIBLE"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100000 1
1 99999"""
        output = """IMPOSSIBLE"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """5 5
1 3
4 5
2 3
2 4
1 4"""
        output = """POSSIBLE"""
        self.assertIO(input, output)


def resolve():
    N, M = map(int, input().split())
    S = [0] * N
    E = [0] * N
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            S[b-1] = 1
        if b == N:
            E[a-1] = 1

    ans = "IMPOSSIBLE"
    for i in range(N):
        if S[i] == E[i] == 1:
            ans = "POSSIBLE"
            break
    print(ans)


if __name__ == "__main__":
    
    resolve()

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())
'''
check = 0


for i in range(m):
    if a[i] == 1:
        check = b[i]
        for j in range(m):
            if a[j] == check and b[j] == n:
                print("POSSIBLE")
                exit()

print("IMPOSSIBLE")

'''
start = []
leave = []
for i in range(m):
    if a[i] == 1:
        start.append(b[i])
    elif b[i] == n:
        leave.append(a[i])

if set(start) & set(leave):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

hyou=[]

for i in range(m):
    hyou.append([int(i) for i in input().split()])


next_island=set()
pre_island=set()
for go in hyou:
    one,two=go
    newone=min(one,two)
    newtwo=max(one,two)

    if newone==1:
        next_island.add(newtwo)
    if newtwo==n:
        pre_island.add(newone)

ans=next_island&pre_island

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

Solution (Python):
N,M=map(int,input().split())
nekotyann=[0]*N
wanntyann=[0]*N
ans="IMPOSSIBLE"
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        nekotyann[b-1]+=1
    if b==N:
        wanntyann[a-1]+=1
for k in range(N):
    if nekotyann[k]!=0 and wanntyann[k]!=0:
        ans="POSSIBLE"
        break
print(ans)

Solution (Python):
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
for i in edge[0]:
    if n-1 in edge[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")