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

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque
import marshal


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if t>=2:
                    continue
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return True
                self.parent[q] = p
                next_set.append((q, t + 1))
        return False


N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)

if graph.bfs(start=1, goal=N, time=0, save=False):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')







def solve():
    N, M = MI()
    
    
    S = [0] * N
    for i in range(M):
        a, b = MI()
        if a == 1:
            S[b] += 1
        elif b == N:
            S[a] += 1
    
    for s in S:
        if s >= 2:
            print('POSSIBLE')
            return 
    print('IMPOSSIBLE')

if __name__ == '__main__':
    solve()

Solution (Python):
n, m = map(int, input().split())
l = [0]*n

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

for i in l:
    if i >= 2:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
X = [0]*N
for _ in range(M):
    a, b = map(int, input().split())
    if a==1 or a==N: X[b-1]+=1
    if b==1 or b==N: X[a-1]+=1

print('POSSIBLE' if max(X)>=2 else 'IMPOSSIBLE')

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m,*ab = map(int,read().split())

m = iter(ab)

s1 = set()
s2 = set()
for a,b in zip(m,m):
    a -= 1
    b -= 1
    if a==0: s1.add(b)
    if a==n-1: s2.add(b)
    if b==0: s1.add(a)
    if b==n-1: s2.add(a)



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

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

Solution (Python):
n,m = map(int,input().split())
x = [0 for _ in range(n)]
y = [0 for _ in range(n)]
for _ 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(1,n):
  if x[i] == 1 and y[i] == 1:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
a=[]
edge=[[] for i 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]:
    for j in edge[i]:
        a.append(j)
    a.append(i)
print('POSSIBLE' if n-1 in a else 'IMPOSSIBLE')

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

near = [set([]) for _ in range(n)]
for a, b in ab:
    near[a - 1].add(b - 1)
    near[b - 1].add(a - 1)

for i in near[0]:
    if i in near[n - 1]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
def main():
    N, M = map(int, input().split())
    d = {}
    for _ in range(M):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for x in d[1]:
        if N in d[x]:
            return 'POSSIBLE'
    return 'IMPOSSIBLE'
print(main())

Solution (Python):
import sys


def main():
  n, m, *lst = map(int, sys.stdin.read().split())
  set1, setn = set(), set()
  for i, j in zip(*[iter(lst)] * 2):
    if i == 1:
      set1.add(j)
    if j == n:
      setn.add(i)
  print('POSSIBLE' if set1 & setn else 'IMPOSSIBLE')


if __name__ == '__main__':
  main()

Solution (Python):
import sys


def main():
  n, m = map(int, sys.stdin.readline().split())
  lst = map(int, sys.stdin.read().split())
  set1, setn = set(), set()
  for i, j in zip(lst, lst):
    if i == 1:
      set1.add(j)
    if j == n:
      setn.add(i)
  if set1 & setn:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')


if __name__ == '__main__':
  main()

Solution (Python):
import sys


def main():
  n, m = map(int, sys.stdin.readline().split())
  set1, setn = set(), set()
  for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    if i == 1:
      set1.add(j)
    if j == n:
      setn.add(i)
  if set1 & setn:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')


if __name__ == '__main__':
  main()

Solution (Python):
import sys
n, m = map(int, sys.stdin.readline().split())
set1, setn = set(), set()
for _ in range(m):
  i, j = map(int, sys.stdin.readline().split())
  if i in [1, n] or j in [1, n]:
    if i == 1:
      set1.add(j)
    if i == n:
      setn.add(j)
    if j == 1:
      set1.add(i)
    if j == n:
      setn.add(i)
if set1 & setn:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):


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


N, M = LI()
A, B = [None] * M, [None] * M
for i in range(M):
    A[i], B[i] = LI()
    A[i] -= 1
    B[i] -= 1


def solve(link):
    for i in link[0]:
        if N - 1 in link[i]:
            return "POSSIBLE"
    return "IMPOSSIBLE"


def main():
    link = [set() for _ in range(N)]
    for a, b in zip(A, B):
        link[a].add(b)
        link[b].add(a)
    
    ans = solve(link)
    print(ans)


if __name__ == "__main__":
    main()

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

Solution (Python):
from collections import deque
N,M=list(map(int,input().split()))
N_l=set()
one_l=set()
for i in range(M):
   A,B=list(map(int,input().split()))
   if A == 1:
      one_l.add(B)
   elif B==N:
      N_l.add(A)
if len(N_l & one_l) > 0:
   print("POSSIBLE")
else:
   print("IMPOSSIBLE")

Solution (Python):
n,m=[int(x) for x in input().split()]
t=[0 for i in range(n)]
for i in range(m):
  a,b=[int(x) for x in input().split()]
  if a==1:
    t[b-1]+=1
  if b==n:
    t[a-1]+=1
    
if 2 in t:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
n,m= list(map(int, input().split()))
li=[list(map(int,input().split())) for _ in range(m)]
hub1=set()
hub2=set()
for i in li:
    if n in i:
        hub1.add(sum(i)-n)
    if 1 in i:
        hub2.add(sum(i)-1)
if hub1&hub2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split( ))
s1=set()
sn=set()
for _ in range(m):
    a,b=map(int, input().split( ))
    if a==1 and b not in s1:
        s1.add(b)
    elif b==1 and a not in s1:
        s1.add(a)
    if a==n and b not in sn:
        sn.add(b)
    elif b==n and a not in sn:
        sn.add(a)
if s1&sn:
    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())
  a-=1
  b-=1
  E[a].append(b)
  E[b].append(a)
dist=[10**7]*n
dist[0]=0
seen=[0]*n
seen[0]=1
stack=deque([0])
while stack:
  u=stack.popleft()
  for v in E[u]:
    if seen[v]!=1:
      dist[v]=min(dist[u]+1,dist[v])
      seen[v]=1
      stack.append(v)
if dist[n-1]==2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

for value in graph[1]:
    if(N in graph[value]):
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
def examC():
    def bfs(n, e, fordfs):
        
        W = [-1] * n
        
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N, M = LI()
    V = [[]for _ in range(N)]
    for i in range(M):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    L = bfs(N,0,V)
    if L[N-1]==2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    return

def examD():
    K = I()
    N = 50
    A = [i for i in range(N)]
    for i in range(N):
        A[-1-i] +=((K-i+49)//N)
    print(N); print(" ".join(map(str,A)))
    return

def examE():
    N = I()
    A = LI()
    ans = 0
    while(True):
        cur = 0
        for i in range(N):
            cur += A[i]//N
        for i in range(N):
            A[i] = A[i]%N + cur-A[i]//N
        ans += cur
        if cur==0:
            break
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Solution (Python):
def main():
  N,M = map(int,input().split())
  ships = [list(map(int,input().split())) for i in range(M)]
  start, goal = set(), set()
  for i in range(M):
    if ships[i][0] == 1:
      start.add(ships[i][1])
    if ships[i][1] == N:
      goal.add(ships[i][0])
  flg = start & goal
  print("POSSIBLE" if flg else "IMPOSSIBLE")
 
main()

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
from _collections import defaultdict
from functools import lru_cache

class Scanner():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def map_int():
        return [int(x) for x in Scanner.string().split()]
    def string_list(n):
        return [input() for i in range(n)]
    def int_list_list(n):
        return [Scanner.mapInt() for i in range(n)]
    def int_cols_list(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def lcm(a,b):
        return (a * b) // Math.gcd(a,b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3,d + 1,2):
            if n % i == 0:
                return False
        return True

MOD = int(1e09) + 7

def main():
    N,M = Scanner.map_int()
    G = [[] for i in range(N)]
    for i in range(M):
        a,b = Scanner.map_int()
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)
    for i in G[0]:
        for j in G[i]:
            if j == N-1:
                print("POSSIBLE")
                return
    print("IMPOSSIBLE")
    return

if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
ab = {}
for _ in range(m):
    a, b = map(int, input().split())
    if not a in ab:
        ab[a] = []
    if not b in ab:
        ab[b] = []
    ab[a].append(b)
    ab[b].append(a)

def dfs(i: int, l:list) -> bool:
    if i > 2:
        return False

    ret = False
    for _l in l:
        if _l == n:
            ret = True

        if _l > i:
           ret |= dfs(i+1, ab[_l])

    return ret

print("POSSIBLE" if dfs(1, ab[1]) else "IMPOSSIBLE")

Solution (Python):
def inpl():
    return list(map(int, input().split()))


N, M = inpl()
AB = [inpl() for i in range(M)]

n1 = []
nN = []

for a, b in AB:
    if a == 1:
        n1.append(b)
    elif b == N:
        nN.append(a)

n1 = set(n1)
nN = set(nN)

print('POSSIBLE' if len(n1 & nN) > 0 else 'IMPOSSIBLE')

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


connections = dict()
answer = 'IMPOSSIBLE'


def add_to_set(a, b):
    if a in connections:
        connections[a].add(b)
    else:
        connections[a] = set([b])

    if b in connections:
        connections[b].add(a)
    else:
        connections[b] = set([a])


for i in range(m):
    a, b = list(map(int, input().split()))
    add_to_set(a, b)

island_1 = connections.get(1)
island_N = connections.get(n)


for e in island_1:
    if island_N and e in island_N:
        answer = 'POSSIBLE'

print(answer)

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

islands = [0 for i in range(n)]

for i in range(m):
  a, b = map(int, input().split())
  
  if a == 1:
    if islands[b-1] == 2:
      print('POSSIBLE')
      break
    islands[b-1] = 1
  if b == n:
    if islands[a-1] == 1:
      print('POSSIBLE')
      break
    islands[a-1] = 2
    
  if i == m-1:
    print('IMPOSSIBLE')

Solution (Python):







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

ends = []
starts = []
possible = False
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        starts.append([a, b])
    elif b == n:
        ends.append([a, b])

starts.sort(key=lambda x: x[1])
ends.sort(key=lambda x: x[0])

if not (starts and ends):
    print("IMPOSSIBLE")
    import sys

    sys.exit()

i = 0
j = 0
while i != len(starts) and j != len(ends):
    to = starts[i][1]
    fr = ends[j][0]

    if to == fr:
        possible = True
        break

    if to < fr:
        i += 1
    elif fr < to:
        j += 1

while j != len(ends):
    fr = ends[j][0]
    if to == fr:
        possible = True
        break
    j += 1

while i != len(starts):
    to = starts[i][1]
    if to == fr:
        possible = True
        break
    i += 1

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

Solution (Python):

def main():
    N, M, *AB = map(int, open(0).read().split())
    from_1, to_N = set(), set()
    for a, b in zip(*[iter(AB)] * 2):
        if a == 1:
            from_1.add(b)
        if b == N:
            to_N.add(a)
    flg = from_1 & to_N  
    print("POSSIBLE" if flg else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = [False] * n
    q = p[:]
    for i in range(m):
        j, k = map(int, input().split())
        if j == 1:
            p[k] = True
        if j == n:
            q[k] = True
        elif k == n:
            q[j] = True
    for i in range(n):
        if p[i] and q[i]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")


main()

Solution (Python):
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    d = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        if a == 1 or a == n:
            d[a] += [b]
        if b == 1 or b == n:
            d[b] += [a]
    if 1 in d and n in d:
        dd = collections.defaultdict(list)
        for v in d[n]:
            dd[v]
        for i in d[1]:
            if i in dd:
                print("POSSIBLE")
                exit()
    print("IMPOSSIBLE ")


if __name__ == '__main__':
    slove()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    
    N,M = map(int,input().split())
    one = {}
    enu = {}
    
    for i in range(M):
        a,b = map(int,input().split())
        if a==1:
            one[b] = 1
        elif b==1:
            one[a] = 1
        elif a==N:
            enu[b] = 1
        elif b==N:
            enu[a] = 1
    flag = 0
    for i in one:
        if i in enu:
            flag = 1
            break
    if flag==1:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
    
    
main()

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

bridge1 = []
bridge1_right = set()
bridge2 = []
bridge2_left = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        bridge1.append((a, b))
        bridge1_right.add(b)
    if b == N:
        bridge2.append((a, b))
        bridge2_left.add(a)

if len(bridge1) == 0 or len(bridge2) == 0:
    print('IMPOSSIBLE')
    exit()

if len(bridge1_right & bridge2_left) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    ad = collections.defaultdict(list)
    bd = collections.defaultdict(list)
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        if a == 1:
            ad[b] = 1
        if b == 1:
            ad[a] = 1

        if a == n:
            bd[b] = 1
        if b == n:
            bd[a] = 1
    for k, v in ad.items():
        if k in bd:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")


if __name__ == '__main__':
    slove()

Solution (Python):
N, M = map(int, input().split())
C1 = [0]*(N+1)
C2 = [0]*(N+1)

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        C1[b] +=1
    if b == N:
        C2[a] +=1

for i in range(1,N+1):
    if C1[i]==1 and C2[i]==1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
N, M = map(int,input().split())
S = [False for _ in range(N)]
G = [False for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    if a == 0 and b == N - 1:
        print("POSSIBLE")
        exit()
    if a == 0:
        if G[b]:
            print("POSSIBLE")
            exit()
        S[b] = True
    if b == N - 1:
        if S[a]:
            print("POSSIBLE")
            exit()
        G[a] = True

print("IMPOSSIBLE")

Solution (Python):
a,b=map(int,input().split())
c=[list(map(int,input().split()))for i in[0]*b]
d=[]
e=[]
for i in c:
  if i[0]==1:d+=[i[1]]
  elif i[1]==a:e+=[i[0]]
print((set(d)&set(e)==set())*'IM'+'POSSIBLE')

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  g[a - 1].append(b - 1)
  g[b - 1].append(a - 1)
q = deque([0])
dis = [-1] * n
dis[0] = 0
while q:
  d = q.popleft()
  for node in g[d]:
    if dis[node] == -1:
      q.append(node)
      dis[node] = dis[d] + 1
if dis[n - 1] == 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):

n,m=map(int,input().split())
s=[set()for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  s[a-1].add(b)
for i in s[0]:
  if n in s[i-1]:print("POSSIBLE");exit()
print("IMPOSSIBLE")

Solution (Python):
from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

def main():
	n, m = map(int,input().split())
	s=set()
	t=set()
	for _ in range(m):
		a, b = map(int, input().split())
		if a == 1:
			s.add(b)
		elif b == n:
			t.add(a)
	for i in s:
		if(i in t):
			print('POSSIBLE')
			exit()
	print('IMPOSSIBLE')

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()

Solution (Python):
import copy
import sys
import math

def main():
	n,m = map(int,input().split())
	ab = [list(map(int,input().split())) for _ in range(m)]
	b = {}
	for i in ab:
		try:
			b[i[0]].append(i[1])
		except:
			b[i[0]] = [i[1]]
		try:
			b[i[1]].append(i[0])
		except:
			b[i[1]] = [i[0]]
	ab = copy.deepcopy(b)
	for i in ab[1]:
		if(n in ab[i]):
			print('POSSIBLE')
			sys.exit()
	print('IMPOSSIBLE')


def listtodict(a):
	b = {}
	for i in a:
		try:
			b[i] += 1
		except:
			b[i] = 1
	return b

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

main()

Solution (Python):
import copy
import sys
import math

def main():
	n,m = map(int,input().split())
	ab = [list(map(int,input().split())) for _ in range(m)]
	b = {}
	for i in ab:
		try:
			b[i[0]].append(i[1])
		except:
			b[i[0]] = [i[1]]
		try:
			b[i[1]].append(i[0])
		except:
			b[i[1]] = [i[0]]
	ab = copy.deepcopy(b)
	for i in ab[1]:
		if(n in ab[i]):
			print('POSSIBLE')
			sys.exit()
	print('IMPOSSIBLE')


def listtodict(a):
	b = {}
	for i in a:
		try:
			b[i] += 1
		except:
			b[i] = 1
	return b

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

main()

Solution (Python):
N,M=map(int,input().split())
ab=[list(map(int,input().split())) for _ in [0]*M]
g=[set() for _ in [0]*N]
[g[b-1].add(a-1) for a,b in ab]
[g[a-1].add(b-1) for a,b in ab]
a=g[0]
for i in a:
	if N-1 in g[i]:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

Solution (Python):
import numpy as np

n, m = list(map(int, input().split()))
ablist = [list(map(int, input().split())) for _ in range(m)]

from1 = np.zeros(n, dtype=int)
ton = np.zeros(n, dtype=int)

for ab in ablist :
    if ab[0] == 1 :
        from1[ab[1]-1] = 1
    elif ab[1] == n :
        ton[ab[0]-1] = 1

if sum(from1*ton) > 0 :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    s, d = set(), set()  
    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            s.add(b)  
        elif b == n:
            d.add(a)  
    
    print("POSSIBLE" if s & d else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

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

sp = [False for _ in range(N + 1)]
pg = [False for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, input().split())
    if a == N:
        pg[b] = True
    if b == N:
        pg[a] = True
    if a == 1:
        sp[b] = True
    if b == 1:
        sp[a] = True

for i in range(1, N + 1):
    if pg[i] and sp[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
from_1 = [False]*N
to_N = [False]*N
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1[b-1] = True
    elif b == N:
        to_N[a-1] = True
for i in range(1, N):
    if from_1[i] and to_N[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
from collections import defaultdict, deque

INF = 10**12
N, M = map(int, input().split())
E = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
dist = [INF]*N
q = deque([(0, 0)])
while q:
    v, d = q.popleft()
    dist[v] = d
    for u in E[v]:
        if dist[u] == INF:
            q.append((u, d+1))
print('POSSIBLE' if dist[N-1] == 2 else 'IMPOSSIBLE')

Solution (Python):
from collections import defaultdict

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

import sys

teiki = defaultdict(set)
for i in range(M):
    a, b = map(int, input().split())
    teiki[a].add(b)


if 1 not in teiki:
    print('IMPOSSIBLE')
    sys.exit()

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

print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split(' '))
route={ int(i):[] for i in range(N) }
for i in range(M):
  a,b=map(int,input().split(' '))
  route[a-1].append(b-1)
  route[b-1].append(a-1)
ans='IMPOSSIBLE'
for island in route[0]:
  if N-1 in route[island]:
    ans='POSSIBLE'
    break
print(ans)

Solution (Python):
from collections import defaultdict
import sys
N,M = map(int,input().split())
d = defaultdict(list)
for i in range(M):
    a,b = map(int,input().split())
    d[a].append(b)
for i in d[1]:
    if N in d[i]:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

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

A = []
B = [0]*(N+1)
for a,b in ab:
  if a==1:
    A.append(b)
  if b==N:
    B[a]=1

for a in A:
  if B[a]==1:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, raw_input().split())
ab = []
for _ in range(M):
  _ab = map(int, raw_input().split())
  ab.append(_ab)
  
sorted_a = sorted(ab, key=lambda x:x[0])
sorted_b = sorted(ab, key=lambda x:x[1])

from_1 = set([b for a, b in sorted_a if a == 1])
to_N = set([a for a, b in sorted_b if b == N])

if len(from_1 & to_N) > 0:
  print 'POSSIBLE'
else:
  print 'IMPOSSIBLE'

Solution (Python):
s=set()
N,M=map(int,input().split())
for i in range(M):
    a,b=map(int,input().split())
    s.add((a,b))

for i in range(N):
    if((1,i)in s and (i,N) in s):
        print("POSSIBLE")
        exit()
    
print("IMPOSSIBLE")

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

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
n,m = (int(i) for i in input().split())
uf = UnionFind(n-1)
for i in range(m):
  a,b = (int(i) for i in input().split())
  if a == 1 or b ==n: uf.union(a-1,b-1)

if uf.same_check(0,n-1): print('POSSIBLE')
else:print('IMPOSSIBLE')

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
cand_1 = []
cand_2 = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cand_1.append(b)
    elif b == N:
        cand_2.append(a)

ans = "IMPOSSIBLE"
heapq.heapify(cand_1)
heapq.heapify(cand_2)


while len(cand_1) != 0 and len(cand_2) != 0:
    if cand_1[0] < cand_2[0]:
        heapq.heappop(cand_1)
    elif cand_1[0] > cand_2[0]:
        heapq.heappop(cand_2)
    else:
        ans = "POSSIBLE"
        break
print(ans)

Solution (Python):



import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

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


dicts = [set() for _ in range(N)]
for m in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    dicts[a].add(b)
    dicts[b].add(a)


if dicts[0] & dicts[N-1]:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')