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 queue
N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

def dfs(Graph, N, start):
    q = queue.Queue()
    dist = [-1] * N
    dist[start] = 0
    q.put(start)

    while not q.empty():
        v = q.get()
        if dist[v] >1:
            continue
        for u in G[v]:
            if dist[u] != -1:
                continue
            dist[u] = dist[v] + 1
            q.put(u)

    return dist
if dfs(G, N, 0)[-1] > 2 or dfs(G, N, 0)[-1] == -1:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):


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

for i in range(M):
    a, b = map(int, input().split())
    if b == N or a == 1:
        B[a].append(b)
for sima in B[1]:
    if N in B[sima]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):


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

for i in range(M):
    a, b = map(int, input().split())
    if b == N or a == 1:
        B[a].append(b)
for sima in B[1]:
    if N in B[sima]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

flag = False
for i in d[1]:
    if i in d.keys():
        for j in d[i]:
            if j == N:
                flag = True
                break
        if flag:
            break
if flag:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
island_1 = []
island_n = []
ans = "IMPOSSIBLE"

for i in range(m):
    AB = sorted(map(int,input().split()))
    
    if AB[0] == 1:
        island_1.append(AB[1])
        
    if AB[1] == n:
        island_n.append(AB[0])
        
island_1 = set(island_1)
island_n = set(island_n)
        
if len(island_1&island_n) > 0:
    ans = "POSSIBLE"
    
print(ans)

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

first = []
second = []
for a, b in L:
    if a == 1:
        first.append(b)
    if b == N:
        second.append(a)
flg = len(set(first) & set(second))
print('POSSIBLE' if flg else 'IMPOSSIBLE')

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n = n//a
    count += 1
  if a**count == n:
    return count
  else:
    return count+1





N,M = IL()

graph = [[] for i in range(N)]
for _ in range(M):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)

ans = "IMPOSSIBLE"  
for i in graph[0]:
  for j in graph[i]:
    if j == N-1:
      print("POSSIBLE")
      E()
P(ans)

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

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

if len(set(from_1) & set(to_n)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M= list(map(int,input().split()))
import sys
A=set()
B=set()
l=[i.rstrip().split() for i in sys.stdin.readlines()]
for i,j in l:
   if i == "1":
      A.add(j)
   if j == str(N):
      B.add(i)
if len(A&B) > 0:
   print("POSSIBLE")
else:
   print("IMPOSSIBLE")

Solution (Python):

from collections import deque
n, m = map(int, input().split())

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


def bfs(graph, start, n):
    visited = [False] * n
    visited[start] = True
    que = deque([start])
    cost = [float('inf')] * n
    cost[start] = 0
    while que:
        node = que.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = True
                cost[n] = cost[node] + 1
                que.append(n)
    return cost

cost = bfs(graph, 0, n)
if cost[-1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
d = {}
for i in range(m):
    if L[i][0] not in d:
        d[L[i][0]] = [L[i][1]]
    else:
        d[L[i][0]].append(L[i][1])
for j in d[1]:
    if j in d and n in d[j]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
from collections import defaultdict
from collections import deque

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

graph = defaultdict(list)

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

q = deque([1])
dist = [0] * (n + 1)
dist[1] = 0
curr = 0

while q and curr <= 2:
    node = q.popleft()
    after = graph[node]

    for a in after:
        if a == n:
            print("POSSIBLE")
            sys.exit()
        q.append(a)
        dist[a] = dist[node] + 1

    curr = dist[a]

print("POSSIBLE" if dist[n] == 1 or dist[n] == 2 else "IMPOSSIBLE")

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

contact = defaultdict(list)

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



for x in contact[0]:
	if N-1 in contact[x]:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

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

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



for x in contact[0]:
	if N-1 in contact[x]:
		print("POSSIBLE")
		break
else:
	print("IMPOSSIBLE")

Solution (Python):
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

graph = defaultdict(list)
for _ in range(M):
	a, b = MAP()
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)




for x in graph[0]:
	for y in graph[x]:
		if y == N-1:
			print("POSSIBLE")
			break
	else:
		continue
	break
else:
	print("IMPOSSIBLE")

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,m = map(int,readline().split())
g = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    w = 1
    g[x].append((w,y))
    g[y].append((w,x))



import heapq
def dijkstra_heap(s,edge): 
    
    d = [float("inf")] * len(edge)
    used = [True] * len(edge) 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge[1]]: 
            continue
        v = minedge[1] 
        d[v] = minedge[0] 
        used[v] = False 
        for e in edge[v]: 
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v],e[1]))
    return d 

dist = dijkstra_heap(0,g)[-1]
print("POSSIBLE" if dist == 2 else "IMPOSSIBLE")

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

if m == 1:
  print("IMPOSSIBLE")

else:
  root = [[] for i in range(n)]
  for a, b in ab:
    root[a-1].append(b-1)
  
  flag = False
  for j in root[0]:
    if n-1 in root[j]:
      flag = True
      break

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

Solution (Python):
N,M=map(int, input().split())
p="POSSIBLE"
S=set()
a=[]
for _ in range(M):
    A, B = map(int, input().split())
    if A == 1:
        a.append(B)
    else:
        S.add((A,B))
print(p if any([(i,N) in S for i in a]) else "IM"+p)

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 len(set(a) & set(b)) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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


def dfs(now, count):
    if count <= 2 and visit[n] == 0:
        visit[now] = 1
        if count <= 1:
            for x in graph[now]:
                dfs(x, count + 1)


flag = False
if ab[0][0] == 1:
    graph = [[] for _ in range(n + 1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    visit = [0] * (n + 1)
    dfs(1, 0)

    if visit[n] == 1:
        flag = True

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

Solution (Python):
n,m = map(int,input().split())
ab_list = [list(map(int,input().split())) 
           for nesya in range(m)]
start = set()
end = set()
for ab in ab_list:
  if ab[0] == 1:
    start.add(ab[1])
  elif ab[1] == n:
    end.add(ab[0])
ans = start&end
if len(ans) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
ab_list = [list(map(int,input().split())) 
           for nesya in range(m)]
start = set()
end = set()
for ab in ab_list:
  if ab[0] == 1:
    start.add(ab[1])
  if ab[1] == n:
    end.add(ab[0])
ans = start&end
if len(ans) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

for _ in range(M):
    ai, bi = map(int, input().split())
    memo[ai].append(bi)
    memo[bi].append(ai)

queue = memo[1]


if N in queue:
    print("POSSIBLE")
    quit()


while queue:
    island = queue.pop()
    for connected_island in memo[island]:
        if connected_island == N:
            print("POSSIBLE")
            quit()

print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
  if b==n:
    tempb.append(a)
if len(temp)>=1 and ans==0:
  temp=set(temp)
  tempb=set(tempb)
  c = temp&tempb
  
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  """
else:
  print("IMPOSSIBLE")

Solution (Python):

from collections import defaultdict
n,m = list(map(int, input().split()))

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

for src in d[n]:
    if 1 in d[src]:
        print('POSSIBLE')
        exit()
        
print('IMPOSSIBLE')

Solution (Python):
N,M = map(int, input().split())
one2other = [0]*N
other2goal = [0]*N
for i in range(M):
    a,b = map(int, input().split())
    if a == 1:
        one2other[b-1] = 1
    if b == N:
        other2goal[a-1] = 1
for i in range(N):
    if one2other[i] == 1 and other2goal[i] == 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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

ans = "IMPOSSIBLE"

start_candidate = [X[1] for X in s if X[0]==1 ]
goal_candidate = [X[0] for X in s if X[1]==N]

ans = len(start_candidate)+len(goal_candidate)-len(set(start_candidate+goal_candidate))
if ans != 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

G = [[] for _ in range(N)]
for x, y in L:
  x, y = x-1, y-1
  G[x].append(y)
  G[y].append(x)

for v in G[0]:
  if N-1 in G[v]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

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

G = [[] for _ in range(N)]
for x, y in L:
  x, y = x-1, y-1
  G[x].append(y)
  G[y].append(x)

for v in G[0]:
  for nv in G[v]:
    if nv == N-1:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))
n,m = iim()
cand = []
check = []
for i in range(m):
    a,b = iim()
    if a == 1:
        cand.append(b)
    if b == n:
        check.append(a)

cand = set(cand)
flag=False
for i in check:
    if i in cand:
        flag = True

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

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

    if A == 1 :
        one.append(B)
    elif B == 1:
        one.append(A)

    if A == N or B == N:
        goal.append(A)
        goal.append(B)

if set(goal) & set(one):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

goal = {i:0 for i in range(1, N+1)}
N = str(N)

ne = []
for i in ab:
    if i[0] == "1":
        goal[int(i[1])] = 1

for j in ab:
    if goal[int(j[0])] and j[1] == N:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
N,M = map(int,input().split())
 
s = []
g = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        s.append(b)
    elif b == N:
        g.append(a)
    
ans = set(s) & set(g)
 
if len(ans) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

Solution (Python):


import numpy as np
import math
import sys
input = sys.stdin.readline
n,m= map(int,input().split())
A = []
B = []
for i in range(m):
    x,y = map(int,input().split())
    if x==1:
        A.append(y)
    elif y==1:
        A.append(x)
    elif x==n:
        B.append(y)
    elif y==n:
        B.append(x)
s  ="IMPOSSIBLE" if len(set(A + B)) ==len(A)+len(B) else "POSSIBLE"
print(s)

Solution (Python):
n,m = map(int,input().split())
d = {str(x):[] for x in range(1,n+1)}
n = str(n)
ans = "IMPOSSIBLE"
for i in range(m):
    t = input().split()
    d[t[0]].append(t[1])

for l1 in d["1"]:
    if l1==n:
        ans="POSSIBLE"
        break
    else:
        for l2 in d[l1]:
            if l2==n:
                ans="POSSIBLE"
                break
print(ans)

Solution (Python):
n,m = map(int,input().split())
d = {str(x):[] for x in range(1,n+1)}
n = str(n)
ans = "IMPOSSIBLE"
for i in range(m):
    t = input().split()
    d[t[0]].append(t)

for l1 in d["1"]:
    if l1[1]==n:
        ans="POSSIBLE"
    else:
        for l2 in d[l1[1]]:
            if l2[1]==n:
                ans="POSSIBLE"
print(ans)

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

n1 = set()
nN = set()

for _ in range(M):
    a, b = map(int, input().split())
    if (a == 1) or (b == 1):
        n1.add(b if a == 1 else a)
    if (a == N) or (b == N):
        nN.add(b if a == N else a)

ans = 'IMPOSSIBLE'
if len(n1 & nN) > 0:
    ans = 'POSSIBLE'
print(ans)

Solution (Python):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
li = []
for ab in AB:
    if ab[0] == 1:
        li.append(ab[1])
    if ab[1] == N:
        li.append(ab[0])
se = set(li)
if len(se) != len(li):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

s = []
g = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        s.append(b)
    elif b == N:
        g.append(a)
    
ans = set(s) & set(g)

if len(ans) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
from collections import defaultdict

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

paths = defaultdict(set)

for start, end in edges:
    if start == 1:
        paths[end] |= {start, end}
    elif end == N:
        paths[start] |= {start, end}

for path in paths.values():
    if {1, N}.issubset(path):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)


def input():
    return sys.stdin.readline()[:-1]


N, M = map(int, input().split())
from_1 = {}
to_n = {}
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1[b] = True
    elif b == N:
        to_n[a] = True

for key in to_n.keys():
    if key in from_1:
        print('POSSIBLE')
        exit(0)
print('IMPOSSIBLE')

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


def dfs(s):
    from collections import deque
    check = [0] * (n + 1)
    stack = deque([s])
    check[s] = 0
    while stack:
        now = stack.pop()
        for next in graph[now]:
            if check[next] != 0 and next != n:
                continue
            if next == n and check[now] == 1:
                print('POSSIBLE')
                exit()
            check[next] += check[now] + 1
            stack.appendleft(next)


dfs(1)
print('IMPOSSIBLE')

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


def readstr():
    return input().strip()


def readint():
    return int(input())


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


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


def main():
    N, M = readnums()
    ab = [tuple(readnums()) for _ in range(M)]
    
    al = {x[1] for x in ab if x[0] == 1}
    bl = {x[0] for x in ab if x[1] == N}
    print('POSSIBLE' if al & bl else 'IMPOSSIBLE')


if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
starts = []
goals = []
for _ in range(M):
    s, g = map(int, input().split())
    if s == 1:
        starts.append(g)
    elif g == N:
        goals.append(s)

ans = set(starts) & set(goals)

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

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

A = [0] * n
B = [0] * n

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        A[b-1] = 1
    elif b == 1:
        A[a-1] = 1
    elif a == n:
        B[b-1] = 1
    elif b == n:
        B[a-1] = 1

for i in range(n):
    if A[i] == B[i] == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):

"""
Created on Tue May 12 14:41:02 2020

@author: shinba
"""

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

data = []
relay = []

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

ans = set(relay) & set(data)

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

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

k=[]
l=[]
ans=0
for i in range(m):
    input_l = sorted(list(map(int,input().split())))
    if input_l[0]==1:
        k.append(input_l[1])
    if input_l[1]==n:
        l.append(input_l[0])
print('IMPOSSIBLE' if len(set(k)&set(l))==0 else 'POSSIBLE')

Solution (Python):
island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
temp = []
for i in range(fune):
    if route[i][0] == 1:
        temp.append(route[i][1])
for j in range(fune):
    if route[j][1] == island:
        temp.append(route[j][0])
 
 
print("POSSIBLE") if len(temp) != len(list(set(temp))) else print("IMPOSSIBLE")

Solution (Python):
N,M = map(int, input().split())
li = []
for n in range(M):
    A,B = map(int, input().split())
    li.append([A,B])
p = []
q = []
for i in li:
    if i[0]==1:
        p.append(i[1])
for i in li:
    if i[1]==N:
        q.append(i[0])
if set(p) &set(q):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE ')

Solution (Python):
I=lambda:map(int,input().split());n,m=I();p="POSSIBLE";c={tuple(I())for _ in[0]*m}
for i in range(2,n):
 if{(1,i),(i,n)}<=c:print(p);exit()
print("IM"+p)

Solution (Python):
n, m = map(int, input().split())
c = {tuple(map(int, input().split())) for _ in [None]*m}
for i in range(2, n):
    if {(1, i), (i, n)} <= c:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
island, fune = map(int, input().split(" "))
route = []
for i in range(fune):
    route.append(list(map(int, input().split(" "))))
temp = []
for i in range(fune):
    if route[i][0] == 1:
        temp.append(route[i][1])
for j in range(fune):
    if route[j][1] == island:
        temp.append(route[j][0])


print("POSSIBLE") if len(temp) != len(list(set(temp))) else print("IMPOSSIBLE")

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))


def resolve():
    N,M=pin()
    a=set()
    b=set()
    for i in range(M):
        s,t=pin()
        if s==1:a.add(t)
        if t==N:b.add(s)
    x=len(a&b)
    print(["IMPOSSIBLE","POSSIBLE"][x>0])    
        

    
        

resolve()

Solution (Python):
n,m=map(int,input().split())
d={i:[] for i in range(n)}
n-=1
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
for i in d[0]:
    if n in d[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
import sys
from collections import Counter
from collections import deque
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
x=[]
y=[]
for i in range(m):
    a,b=mp()
    if a==1:
        x.append(b)
    if b==n:
        y.append(a)
if len(list(set(x) & set(y)))>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
def check():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a,b = map(int, input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    for v in edge[0]:
        if N-1 in edge[v]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'
print(check())

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy





sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))




def main():
    n, m = ns()
    d = [[] for i in range(n)]

    for _ in range(m):
        a, b = ns()
        a -= 1
        b -= 1
        d[a].append(b)
        d[b].append(a)

    start = set(d[0])
    term = set(d[n-1])

    for si in start:
        if si in term:
            print("POSSIBLE")
            exit(0)

    print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

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


def readstr():
    return input().strip()


def readint():
    return int(input())


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


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


def main():
    N, M = readnums()
    ab = [list(readnums()) for _ in range(M)]

    s1 = {x[1] for x in ab if x[0] == 1}
    s2 = {x[0] for x in ab if x[1] == N}

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


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

def main():
  n,m=nii()

  tree=[[] for i in range(n)]
  for i in range(m):
    a,b=nii()
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)

  for i in tree[0]:
    for j in tree[i]:
      if j==n-1:
        print('POSSIBLE')
        exit()
  print('IMPOSSIBLE')

if __name__=="__main__":
  main()

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

def main():
  n,m=nii()

  tree=[[] for i in range(n)]
  for i in range(m):
    a,b=nii()
    a-=1
    b-=1
    tree[a]+=[b]
    tree[b]+=[a]

  for i in tree[0]:
    for j in tree[i]:
      if j==n-1:
        print('POSSIBLE')
        exit()
  print('IMPOSSIBLE')

if __name__=="__main__":
  main()

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

def main():
  n,m=nii()

  tree=[[] for i in range(n)]
  for i in range(m):
    a,b=nii()
    a-=1
    b-=1
    tree[a].append(b)
    tree[b].append(a)

  for i in tree[0]:
    for j in tree[i]:
      if j==n-1:
        print('POSSIBLE')
        exit()
  print('IMPOSSIBLE')

if __name__=="__main__":
  main()

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n,m=nii()

tree=[[] for i in range(n)]
for i in range(m):
  a,b=nii()
  a-=1
  b-=1
  tree[a].append(b)
  tree[b].append(a)

for i in tree[0]:
  for j in tree[i]:
    if j==n-1:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

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

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

for i in tree[0]:
  for j in tree[i]:
    if j==n-1:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')