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):
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

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

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

    for i in edge[0]:
        if n - 1 in set(edge[i]):
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    resolve()

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

if len(ab) != len(set(ab)):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")

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

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        g[a].add(b)
        g[b].add(a)

    intersect = {u_1 for u_1 in g[0]} & {u_N for u_N in g[N - 1]}
    print('POSSIBLE' if intersect else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

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

ans="IMPOSSIBLE"
li=[0]*N

for ab in AB:
    if 1 in ab:
        for i in ab:
            if i!=1:
                if li[i-1]==-1:
                    ans="POSSIBLE"
                    break
                else:
                    li[i-1]=1
    elif N in ab:
        for i in ab:
            if i!=N:
                if li[i-1]==1:
                    ans="POSSIBLE"
                    break
                else:
                    li[i-1]=-1
print(ans)

Solution (Python):
from collections import deque
import sys

readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, readline().split())
        a -= 1; b -= 1
        graph[a].append(b)
    check = [0] * N

    que = deque()
    cnt = 0

    que.extend(graph[0])
    flag = False
    ans = 'IMPOSSIBLE'
    while len(que) > 0:
        q = que.pop()
        for i in graph[q]:
            if i == N-1:
                ans = 'POSSIBLE'
                flag = True
                break
        if flag:
            break
    print(ans)

if __name__ == "__main__":
    main()

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

X = set()
Y = set()
for i in range(M):
    a,b = map(int, input().split())
    if a == 1:
        X.add(b)
    if b == N:
        Y.add(a)

if (X & Y) == set():
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
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 == n:
        b.append(x)

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

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

x = [False for i in range(N+1)]
y = [False for i in range(N+1)]

for i in range(M):
    a,b = map(int,input().split())
    a,b = min(a,b), max(a,b)
    if a == 1:
        x[b] = True
    if b == N:
        y[a] = True

ans = 'IMPOSSIBLE'
for i in range(N+1):
    if x[i] and y[i]:
        ans = 'POSSIBLE'
print(ans)

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

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

if len(G[N - 1] & G[0]) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

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

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

print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
ans=dict()
for i in range(m):
  a,b=map(int,input().split())
  if not(a in ans):
    ans[a]={b,}
  else:
    ans[a].add(b)
  if not(b in ans):
    ans[b]={a,}
  else:
    ans[b].add(a)    
flag=False

for i in ans[1]:
  if n in ans[i]:
    flag=True
    break
    

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7


n,m=MI()
lis=[LI() for i in range(m)]
nums=[]
for i in range(m):
    if lis[i][0]==1:
        nums.append(lis[i][1])
    if lis[i][1]==n:
        nums.append(lis[i][0])

if len(nums)>len(list(set(nums))):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
def main():
    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)
    if len(sa&sb) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(4100000)
n, m = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

flag = False
def dfs(now, prev, cnt):
    global flag
    if cnt == 2:
      if now == n-1:
        flag = True
    for next in g[now]:
        if next != prev and cnt < 2:
            dfs(next, now, cnt+1)
    return flag
            
ans = dfs(0,-1,0)
if ans:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

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

print("POSSIBLE" if 2 in l else "IMPOSSIBLE")

Solution (Python):
import sys
import heapq

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

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

    
    def dijkstra_heap(s):
        
        d = [float("inf")] * n
        used = [True] * n  
        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

    L = dijkstra_heap(n - 1)

    if L[0] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    resolve()

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

first=L[0]
ok=False
for f in first:
    if N-1 in L[f]:
        ok=True
        break
if ok:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
def main():
    from collections import deque
    N, M = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    def bfs(G, s):
        dist = [-1 for _ in range(N)]
        que = deque()
        dist[s] = 0
        que.append(s)
        while que:
            u = que.popleft()
            for v in G[u]:
                if dist[v] != -1:
                    continue
                dist[v] = dist[u] + 1
                que.append(v)
        return dist

    d = bfs(edge, 0)
    if 0 <= d[N-1] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

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

first = set()
second = set()
for a, b in ab:
    if a == 1:
        first.add(b)
    elif b == N:
        second.add(a)

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

Solution (Python):
def main():
    n, m = map(int, input().split())
    f = [[False]*2 for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        if a == 1:
            f[b][0] = True
        if b == n:
            f[a][1] = True
    ans = "IMPOSSIBLE"
    for i in range(1, n+1):
        if f[i][0] and f[i][1]:
            ans = "POSSIBLE"
            break
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):

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

for new_v in G[0]:
    if n in G[new_v - 1]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

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

for i in G[1]:
    for j in G[i]:
        if j == N:
            print ('POSSIBLE')
            exit()

print ('IMPOSSIBLE')

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


if __name__ == '__main__':
    main()

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

a = [False]*n
b = [False]*n
for i in range(m):
    left, right = map(int, input().split())
    if left == 1:
        b[right-1] = True
    if right == n:
        a[left-1] = True

ans = 'IMPOSSIBLE'
for i in range(n):
    if a[i] == True and b[i] == True:
        ans = 'POSSIBLE'
print(ans)

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


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

for i in range(len(to[0])):
    if n-1 in to[to[0][i]]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
froms = []
tos = {}
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        froms.append(b)
    else:
        if not tos.get(a) and b == n:
            tos[a] = True
for f in froms:
    if tos.get(f) and tos[f]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
ma = lambda :map(int,input().split())
n,m = ma()
st = [False]*(n+1)
goal = [False]*(n+1)
for i in range(m):
    a,b = ma()
    if a==n:
        goal[b] =True
    if b==n:
        goal[a] =True
    if a==1:
        st[b] = True
    if b==1:
        st[a] = True
f = False
for i in range(1,n+1):
    if st[i] and  goal[i]:
         f=True
print("POSSIBLE") if f else print("IMPOSSIBLE")

Solution (Python):
ma = lambda :map(int,input().split())
n,m = ma()
tr = [[] for i in range(n)]
for i in range(m):
    a,b = ma()
    tr[a-1].append(b-1)
    tr[b-1].append(a-1)
f = False
for i in tr[0]:
    for s in tr[i]:
        if s==n-1:
            f =True
print("POSSIBLE") if f else print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
c=set()
d=set()
for i in range(m):
  a,b=map(int,input().split())
  if a==1 or a==n:
    c.add(b)
  elif b==1 or b==n:
    d.add(a)
if len(c&d)==1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
from_1 = 0
to_N = 0
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_1 |= 1 << b
    if b == N:
        to_N |= 1 << a
print("POSSIBLE" if from_1 & to_N else "IMPOSSIBLE")

Solution (Python):
N,M=map(int,input().split())
S=[]
G=[]
for i in range(M):
	x,y=map(int,input().split())
	if x==1:
		S.append(y)
	if y==N:
		G.append(x)
if S==[] or G==[]:
	print("IMPOSSIBLE")
	exit()
S=set(S)
G=set(G)
T=len(S)+len(G)
k=len(G)
S=list(S)
G=list(G)
for i in range(k):
	S.append(G[i])
U=len(set(S))
if T!=U:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7



def main():
    N, M = map(int, readline().split())
    path = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int, readline().split())
        path[a].append(b)
        path[b].append(a)
    if set(path[1])&set(path[N]):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

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

goto_N = [0]*N
from_1 = [0]*N

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

for i in range(N):
    if goto_N[i] and from_1[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

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

abl1 = set()
abl2 = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.add(ab[1])
    elif ab[1] == N:
        abl2.add(ab[0])


for i in abl1:
   if i in abl2:
       print("POSSIBLE")
       exit()
print("IMPOSSIBLE")

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

set_land1 = set()
set_landN = set()
for i in range(M):
    if rows[i][0]==1 or rows[i][1]==1:
        set_land1.add(rows[i][0])
        set_land1.add(rows[i][1])
    elif rows[i][0]==N or rows[i][1]==N:
        set_landN.add(rows[i][0])
        set_landN.add(rows[i][1])

set_root = set_land1 - set_landN
ans = "POSSIBLE"
if len(set_land1) == len(set_root):
    ans = "IMPOSSIBLE"

print(ans)

Solution (Python):


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

ship = []
keiyu = []

for _ in range(M):
    a, b = map(int, input().split())
    ship.append((a, b))
    if b == N:
        keiyu.append(a)

keiyu = set(keiyu)
for a, b in ship:
    if (a in keiyu and b == 1) or (b in keiyu and a == 1):
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
str_N = str(N)
g = {str(i): set() for i in range(1, N + 1)}
for _ in range(M):
    A, B = input().split()
    if A == '1' or B == str_N:
        g[A].add(B)
        g[B].add(A)

if g['1'].intersection(g[str_N]):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
g = {i: set() for i in range(1, N + 1)}
for _ in range(M):
    A, B = map(int, input().split())
    if A in (1, N) or B in (1, N):
        g[A].add(B)
        g[B].add(A)

if g[1].intersection(g[N]):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

if g[1].intersection(g[N]):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
x=[]
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    x.append(b)
  if b==N:
    x.append(a)
l=len(x)
if len(set(x))==l:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Solution (Python):
def myAnswer(N:int,M:int,A:list,B:list) -> int:
   dic = {key:[] for key in range(1,N+1)}
   for a,b in zip(A,B):
      dic[a].append(b)
   for i in dic[1]:
      for value in dic[i]:
         if(N == value):
            return "POSSIBLE"
   else:
      return "IMPOSSIBLE"

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   A = []
   B = []
   for _ in range(M):
      a,b = map(int,input().split())
      A.append(a)
      B.append(b)
   print(myAnswer(N,M,A[:],B[:]))
if __name__ == '__main__':
   main()

Solution (Python):
def myAnswer(N:int,M:int,A:list,B:list) -> int:
   dic = {key:[] for key in range(1,N+1)}
   for a,b in zip(A,B):
      dic[a].append(b)
   for i in dic[1]:
      for value in dic[i]:
         if(N == value):
            return "POSSIBLE"
   else:
      return "IMPOSSIBLE"

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   A = []
   B = []
   for _ in range(M):
      a,b = map(int,input().split())
      A.append(a)
      B.append(b)
   print(myAnswer(N,M,A[:],B[:]))
if __name__ == '__main__':
   main()

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]
for _ in [0]*M:
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)

for v in G[0]:
    if N-1 in G[v]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    q = [0]
    for _ in range(2):
        q2 = []
        while q:
            i = q.pop()
            for j in g[i]:
                q2.append(j)
        q = q2
    if n-1 in q:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    edge = [[] for _ in range(N)]
    for i in range(M):
        a, b = (int(i) for i in input().split())
        edge[a-1].append((1, b-1))
        edge[b-1].append((1, a-1))
    from heapq import heappop, heappush

    def dijkstra(G, s):
        d = [10**12]*N
        used = [True] * N  
        d[s] = 0
        used[s] = False
        edges = []
        for e in G[s]:
            heappush(edges, e)
        while len(edges):
            c, v = heappop(edges)
            if not used[v]:
                continue
            d[v] = c
            used[v] = False
            for nexc, nexv in G[v]:
                if used[nexv]:
                    heappush(edges, (nexc+c, nexv))
        return d

    dist = dijkstra(edge, 0)
    if dist[N-1] <= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G

n, m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
G = Graph(ab)

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

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

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

G = [tuple(map(int, input().split())) for _ in range(M)]
G.sort(key = lambda x: x[0])

check = [False] * (N + 1)

for a, b in G:
    if a == 1:
        check[b] = True
    else:
        if check[a] and b == N:
            print ('POSSIBLE')
            exit()

print ('IMPOSSIBLE')

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


from collections import defaultdict
tree = defaultdict(lambda: []) 

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

    tree[a].append(b)
    tree[b].append(a)

for item in tree[1]:
    if n in tree[item]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

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

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

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

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

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

edges =[set() for _ in range(N + 1)]
one = set()
for _ in range(M):
    fr, to = map(int, input().split())
    edges[fr].add(to)
    edges[to].add(fr)
    if fr == 1:
        one.add(to)
    if to == 1:
        one.add(fr)

for fr in one:
    if N in edges[fr]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):

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

route = {}
for _ in range(m):
    a, b = map(int, input().split())
    route.setdefault(a, []).append(b)


flag = False
for r1 in route[1]:
    if n in route.get(r1, []):
        flag = True
        break

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

Solution (Python):
N,M=list(map(int,input().split()))
s=set();t=set();
for i in range(M):
  a,b=list(map(int,input().split()))
  if(a==1):
    s.add(b)
  if(b==N):
    t.add(a)
print("POSSIBLE"if s&t else"IMPOSSIBLE")

Solution (Python):
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections


n,m = map(int,input().split())
edge = [[] for i 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 i in edge[0]:
    if n-1 in edge[i]:
        print("POSSIBLE")
        sys.exit()
print("IMPOSSIBLE")

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

Solution (Python):
def main():
    n, m = list(map(int, input().split()))
    root_start = []
    root_goal = []
    ans = {}
    for i in range(m):
        li = list(map(int, input().split()))
        if li[0] == 1:
            ans.setdefault(li[1], 0)
            ans[li[1]] += 1
        elif li[1] == n:
            ans.setdefault(li[0], 0)
            ans[li[0]] += 1
    flg = False
    for k in ans:
        if ans[k] >= 2:
            flg = True

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



if __name__ == '__main__':
    main()

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

set_1=set()
set_n=set()
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    set_1.add(b)
  if b==N:
    set_n.add(a)
    

for x in set_1:
  if x in set_n:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
a=[0]*n
for i in range(m):
  if l[i][0]==1:
    a[l[i][1]]+=1
  elif l[i][1]==n:
    a[l[i][0]]+=1
for i in range(n):
  if a[i]==2:
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

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

Solution (Python):
def main():
    N, M = map(int, input().split())
    query = [ [int(a) for a in input().split()] for i in range(M)]
    query.sort(key=lambda x : x[0])
    mid = set()

    possible = False
    for q in query:
        a = q[0]
        b = q[1]

        if a == 1:
            mid.add(b)

        if b == N:
            if a in mid:
                possible = True
                break
    if possible:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
if __name__ == "__main__":
    main()

Solution (Python):
n , m = map(int,input().split())
iki = set()
nori = set()
for i in range(m):
    a , b = map(int,input().split())
    if a == 1:
        iki.add(b)
    if b == n:
        nori.add(a)

if iki.isdisjoint(nori):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
n,m = map(int,input().split())
graph = {i:[] for i in range(1,n+1)}

for _ in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
if len(set(graph[1]).intersection(set(graph[n]))) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):

def resolve():
    n,m = map(int, input().split())
    d = {}
    for i in range(m):
        a,b = map(int, input().split())
        if a not in d:
            d[a] = {}
        if b not in d:
            d[b] = {}
        d[a][b] = d[b][a] = 1

    if 1 not in d or n not in d:
        print('IMPOSSIBLE')
        return

    for a in d[1].keys():
        if a in d[n]:
            print('POSSIBLE')
            break
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    resolve()

Solution (Python):
N,M = map(int,(input().split()))
line = [[] for _ in range(N)]
for i in range(M):
    a,b = map(int,(input().split()))
    line[a-1].append(b-1)
    line[b-1].append(a-1)
ans = []
for i in line[0]:
    ans.append(i)
for i in line[N-1]:
    ans.append(i)

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

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

se1 = set()
se2 = set()

for a,b in AB:
  if a == 1:
    se1.add(b)
  if b == N:
    se2.add(a)
    
se = se1 & se2
if se:
  ans = 'POSSIBLE'
else:
  ans = 'IMPOSSIBLE'
print(ans)

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

se1 = set()
se2 = set()

for a,b in AB:
  if a == 1:
    se1.add(b)
  if b == N:
    se2.add(a)
    
se = se1 & se2
answer = 'POSSIBLE' if se else 'IMPOSSIBLE'
print(answer)

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

Solution (Python):
def resolve():
	n, m = map(int, input().split())
	v = [[] for i in range(n+1)]
	for i in range(m):
		a, b = list(map(int, input().split()))
		v[a].append(b)
	ans = 'IMPOSSIBLE'
	for i in range(len(v[1])):
		if n in v[v[1][i]]:
			ans = 'POSSIBLE'
			break
	print(ans)
resolve()

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

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

for a in G[1]:
    if a in G[N]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

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

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

for a in G[1]:
    if a in G[N]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

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

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

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split()))for i in range(m)]
from1 = []
to_n = []
for i in range(m):
    if ab[i][0] == 1:
        from1.append(ab[i][1])
    if ab[i][1] == n:
        to_n.append(ab[i][0])
from1.sort()
to_n.sort()
'''
for i in range(len(from1)):
    if from1[i] in to_n:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')
二分探索で実装できそう
'''
def bisearch(data,value):
  left = 0
  right = len(data) - 1
  while left <= right:
    mid = (left + right)//2
    if data[mid] == value:
      return mid
    elif data[mid] < value:
      left = mid + 1
    else:
      right = mid - 1
  return -1
for i in range(len(from1)):
    if bisearch(to_n,from1[i]) != -1:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')

Solution (Python):
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)
  if b==n:
    t.add(a)

res=s&t
if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
p=tuple(tuple(map(int,input().split())) for _ in range (m))
s=set()
t=set()
for i in range(m):
    if 1 in p[i]:
        s.add(p[i][0])
        s.add(p[i][1])
    if n in p[i]:
        t.add(p[i][0])
        t.add(p[i][1])
res=s&t
if res:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")