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

Solution (Python):
n,m = map(int,input().split())
one_li = []
to_n_li = []
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        one_li.append(b)
    if b == n:
        to_n_li.append(a)
ll = len(set(one_li) & set(to_n_li))
if ll == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
AB = sorted(ab, reverse=True, key=lambda x:x[1])
s = [0] * n
ans = "IMPOSSIBLE"
for a,b in ab:
    if a == 1: s[b-1] = 1
    else: break
for A, B in AB:
    if B == n:
        if s[A-1] == 1:
            ans = "POSSIBLE"
    else: break
print(ans)

Solution (Python):
n,m = map(int,input().split())
from1_ls = []
togoal_ls = []
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        from1_ls.append(b)
    if b == n:
        togoal_ls.append(a)
set_from = set(from1_ls)
set_to = set(togoal_ls)
intersection = set_from & set_to
ans = 'IMPOSSIBLE'
if intersection:
    ans = 'POSSIBLE'
print(ans)

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

Solution (Python):
N, M = map(int, input().split())
dep = []
ter = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        dep.append(b)
    elif b == 1:
        dep.append(a)
    elif a == N:
        ter.append(b)
    elif b == N:
        ter.append(a)
print('POSSIBLE' if len(set(dep) & set(ter)) != 0 else 'IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
s = [0 for i in range(n)]
e = [0 for i in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    if x == 1:
        s[y] = 1
    elif y == n:
        e[x] = 1
flag = False
for i in range(n):
    if s[i] == 1 and e[i] == 1:
        flag = True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys

readline = sys.stdin.readline
N, M = map(int, readline().split())
x = set()
y = set()
for _ in range(M):
    a, b = map(int, readline().split())
    if a == 1:
        x.add(b)
    if b == N:
        y.add(a)
print('POSSIBLE' if x & y else 'IMPOSSIBLE')

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N, M = map(int, input().split())
f = [False] * N
s = [False] * N
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1

    if a == 0:
        f[b] = True
    if b == N -1:
        s[a] = True

ok = False
for i in range(N):
    if f[i] & s[i]:
        ok = True

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

Solution (Python):
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

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

for i in g[0]:
    if n-1 in g[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

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

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

Solution (Python):
n,m=map(int,input().split())
edges=[set() for i in range(n+1)]
for i in range(m):
	a,s=map(int,input().split())
	edges[a].add(s)
	edges[s].add(a)
for i in range(2,n):
	if i in edges[1] and i in edges[n]:
		print("POSSIBLE");exit()
print("IMPOSSIBLE")

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

a = [0]*m
b = [0]*m
checks = [0]*n
checkg = [0]*n
for i in range(m):
    a[i],b[i] = map(int,input().split())
    if a[i]== 1:
        checks[b[i]]=1
    if b[i]== n:
        checkg[a[i]]=1
ans = 0
for i in range(n):
    if checks[i] == checkg[i] == 1:
        ans = 1
if ans :
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
ab = [[-1] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    if ab[a-1][-1] == -1:
        ab[a-1][-1] = b-1
    else:
        ab[a-1].append(b-1)
flg = False
for i, mid in enumerate(ab[0]):
    if n-1 in ab[mid]:
        flg = True
        break

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

Solution (Python):
n,m = map(int,input().split())
ab = [[-1] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    if ab[a-1][-1] == -1:
        ab[a-1][-1] = b-1
    else:
        ab[a-1].append(b-1)
flg = False
for i, mid in enumerate(ab[0]):
    if n-1 in ab[mid]:
        flg = True
        break

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

Solution (Python):
n,m=map(int,input().split())
r=[set() for i in range(n+1)]
for i in range(m):
    ai,bi=map(int,input().split())
    if not bi in r[ai]:
        r[ai].add(bi)
        r[bi].add(ai)

if len(r[1]&r[n])==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

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

r=[set() for i in range(n+1)]
for i in range(m):
    ai,bi=map(int,input().split())
    if not bi in r[ai]:


        r[ai].add(bi)
        r[bi].add(ai)
yn=""
for i in range(2,n):
    if (i in r[1]) and (i in r[n]):
        print("POSSIBLE")
        yn="POSSIBLE"
        break
if yn=="":
    print("IMPOSSIBLE")

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)


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

Solution (Python):

N, M = map(int, input().split())
an = []
nb = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        an.append(b)
    elif b == N:
        nb.append(a)

print('IMPOSSIBLE' if len(set(an)&set(nb))==0 else 'POSSIBLE')

Solution (Python):

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

print('IMPOSSIBLE' if len(an&nb)==0 else 'POSSIBLE')

Solution (Python):
def resolve():
    N, M = list(map(int, input().split()))
    AB = [list(map(int, input().split())) for i in range(M)]
    d = {}
    for ab in AB:
        if ab[0] not in d:
            d[ab[0]] = [ab[1]]
        else:
            d[ab[0]].append(ab[1])
    if 1 not in d:
        print("IMPOSSIBLE")
        return
    for i in d[1]:
        if i not in d:
            continue
        if N in d[i]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")



if '__main__' == __name__:
    resolve()

Solution (Python):
n,m=map(int,input().split())
p1=[]
pn=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1 and b==n:
    print("POSSIBLE")
    exit()
  elif a==1:
    p1.append(b)
  elif b==n:
    pn.append(a)

x=set(p1)
y=set(pn)
if x&y==set():
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

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

def main():
    N, M = map(int, readline().rstrip().split())
    path = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, readline().rstrip().split())
        path[a-1].append(b-1)
        path[b-1].append(a-1)
    for p in path[0]:
        if N-1 in path[p]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
    return 
    

if __name__ == '__main__':
    main()

Solution (Python):
import collections

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

for i in range(m):
  x, y = map(int,input().split())
  if x == 1: 
    a.append(y)
  if y == n: 
    a.append(x)

c = collections.Counter(a)

if c.most_common()[0][1] == 2:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
E = {i+1: set() for i in range(N)}
first = set()
for m in range(M):
    a, b = lr()
    if b == N:
        first.add(a)
    E[a].add(b)
if not first.isdisjoint(E[1]):
    print("POSSIBLE")
    exit(0)
print("IMPOSSIBLE")

Solution (Python):
n,m =map(int,input().split())
visited = False
q = [[] for _ in range(n)]
flag = False
for j in range(m):
    a,b = map(int,input().split())
    q[a].append(b)

while q[1]:
    c = q[1].pop()
    if n in q[c]:
        flag = True
print('POSSIBLE' if flag==True else 'IMPOSSIBLE')

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    edge=[set() for _ in range(N)]
    for i in range(M):
        a,b=map(int1,input().split())
        edge[a].add(b)
        edge[b].add(a)
    for i in range(N):
        if i in edge[0] and N-1 in edge[i]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

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

a, b = [0] * m, [0] * m
root_i = [False] * n
root_n = [False] * n
for i in range(m):
    a[i], b[i] = map(int, input().split())

for i in range(m):
    if a[i] == 1:
        root_i[b[i]] = True
    elif b[i] == n:
        root_n[a[i]] = True

for i in range(n):
    if root_i[i] == True and root_n[i] == True:
        print("POSSIBLE")
        exit()
    
print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
one_to=[0]*(n+1)
to_n=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        one_to[b]=1
    elif b==n:
        to_n[a]=1
flag=False
for i in range(2,n):
    if one_to[i]==1 and to_n[i]==1:
        flag=True
        break
print("POSSIBLE" if flag else "IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
one_to=set()
to_n=set()
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        one_to.add(b)
    elif b==n:
        to_n.add(a)
one_to=list(one_to)
flag=False
for i in range(len(one_to)):
    if one_to[i] in to_n:
        flag=True
        break
print("POSSIBLE" if flag else "IMPOSSIBLE")

Solution (Python):
from collections import defaultdict
N, M = map(int,input().split())
d = defaultdict(int)
for _ in range(M):
    a, b = map(int,input().split())
    if a == 1:
        d[b] += 1
    if b == N:
        d[a] += 1
if 2 in d.values():
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
A = [0]*n
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    if a==0: A[b]+=1
    elif b==n-1: A[a]+=1
ok = False
for i in range(1,n-1):
    if A[i]>=2:
        ok = True
        break
if ok: print("POSSIBLE")
else: print("IMPOSSIBLE")

Solution (Python):
nim,mike = map(int,input().split())
a = set()
b = set()
for i in range(mike):
    a_,b_ = map(int,input().split())
    if a_ == 1:
        a.add(b_)
    if b_ == nim:
        b.add(a_)
print("POSSIBLE" if a&b else "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)

if sa&sb:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
def slove(n, ab_list):

    hoge = {}
    for i,j in ab_list:
        if int(i) not in hoge:
            hoge[int(i)] = []
        hoge[int(i)].append(int(j))

    ans = len([j for i in hoge[1] if i in hoge for j in hoge[i] if j == n])

    if ans >=1:
        return "POSSIBLE"
    else:
        return "IMPOSSIBLE" 

if __name__ == "__main__":
    n, m = [int(i) for i in input().split()]
    ab_list = [input().split() for i in range(m)]
    print(slove(n, ab_list))

Solution (Python):
n,m=map(int,input().split())
li=[]
for i in range(m):
    a,b=map(int,input().split())
    li.append([a,b])
li1=set([i[1] for i in li if i[0]==1])
li2=set([i[0] for i in li if i[1]==n])
li3=li1&li2
if len(li3)>=1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
s = [0 for i in range(M)]
for i in range(M):
    s[i] = list(map(int, input().split()))
ex = [[0] * 2 for i in range(N)]
for i in range(M):
    if s[i][0] == 1:
        ex[(s[i][1] - 1)][0] = 1
    if s[i][1] == N:
        ex[(s[i][0] - 1)][1] = 1
if [1, 1] in ex:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

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

for _ in range(M):
  a,b = map(int,input().split())
  if a == 1:
    if tmp[b-1] == 1:
      print('POSSIBLE')
      exit()
    else:
      tmp[b-1] = 1
  elif b == N:
    if tmp[a-1] == 1:
      print('POSSIBLE')
      exit()
    else:
      tmp[a-1] = 1
print("IMPOSSIBLE")

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

for _ in range(M):
  a,b = map(int,input().split())
  if a == 1:
    if tmp[b-1] == 1:
      print('POSSIBLE')
      exit()
    else:
      tmp[b-1] = 1
  elif b == N:
    if tmp[a-1] == 1:
      print('POSSIBLE')
      exit()
    else:
      tmp[a-1] = 1
print("IMPOSSIBLE")

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

Solution (Python):
n,m=map(int,input().split())
check=[0]*n
ans="IMPOSSIBLE"
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        if check[bi-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[bi-1]+=1
    elif bi==n:
        if check[ai-1]==1:
            ans="POSSIBLE"
            break
        else:
            check[ai-1]+=1
print(ans)

Solution (Python):
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    S = set()
    E = set()
    for m in range(M):
        a, b = il()
        if a == 1:
            S.add(b)
        if b == N:
            E.add(a)

    print('POSSIBLE' if len(S & E) == 1 else 'IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
ab=[]
for _ in range(m):
  ab.append(list(map(int,input().split())))
c1x=set([x[1] for x in ab if x[0]==1])
cxn=set([x[0] for x in ab if x[1]==n])
print('POSSIBLE'if len(c1x & cxn)>0 else 'IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
c = [False for i in range(200000)]
d = [False for i in range(200000)]
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        c[b] = True
    if b == n:
        d[a] = True
for i in range(n):
    if c[i] and d[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
c = [False for i in range(200000)]
d = [False for i in range(200000)]
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        c[b] = True 
    if b == n:
        d[a] = True
        
flag = False
for i in range(200000):
    if c[i] and d[i]:
        flag = True
        break
if flag:
    print("POSSIBLE")
    
else:
    print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
c = [False for i in range(200000)]
d = [False for i in range(200000)]
for i in range(m):
	a, b = map(int, input().split())
	if a == 1:
		c[b] = True
	if b == n:
		d[a] = True
for i in range(200000):
	if c[i] and d[i]:
		print ("POSSIBLE")
		exit()
print ("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
c = [False for i in range(200001)]
d = [False for i in range(200001)]
for i in range(m):
	a, b = map(int, input().split())
	if a == 1:
		c[b] = True
	if b == n:
		d[a] = True
for i in range(200001):
	if c[i] and d[i]:
		print ("POSSIBLE")
		exit()
print ("IMPOSSIBLE")

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

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

for i in range(m):
    a, b = map(int, input().split())
    if a==1:
        root[0][b-1] = True
    if b==n:
        root[1][a-1] = True
for j in range(n):
    if root[0][j]:
        if root[1][j]:
            print('POSSIBLE')
            exit(0)
print('IMPOSSIBLE')

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

C, D = set(), set()
for a, b in AB:
  if a == 1:
    C.add(b)
  elif b == n:
    D.add(a)

if len(C & D):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

ans = False

cnt = [0 for i in range(0, N)]
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        cnt[b] += 1
        if cnt[b] == 2:
            ans = True
            break
    elif b == N:
        cnt[a] += 1
        if cnt[a] == 2:
            ans = True
            break

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

Solution (Python):
n, m = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for i in range(m)]
list_MAP = [0]*(n+1)

for l in list_AB:
    l.sort()
    if l[0] == 1:
        list_MAP[l[1]] += 1
    if l[1] == n:
        list_MAP[l[0]] += 1

ans = "IMPOSSIBLE"

for num in list_MAP:
    if num > 1:
        ans = "POSSIBLE"

print(ans)

Solution (Python):
n, m = map(int, input().split())
list_AB = [ list(map(int,input().split(" "))) for i in range(m)]
list_MAP = [0]*(n+1)

for l in list_AB:
    l.sort()
    if l[0] == 1:
        list_MAP[l[1]] += 1
    if l[1] == n:
        list_MAP[l[0]] += 1

ans = "IMPOSSIBLE"

for num in list_MAP:
    if num > 1:
        ans = "POSSIBLE"

print(ans)

Solution (Python):
import numpy as np

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

connected_1 = {}

for i in range(m):
    a, b = [int(i) for i in input().split()]
    
    if a == 1:
        if connected_1.get(b) is None:
            connected_1[b] = 1
        elif connected_1[b] ==1:
            print("POSSIBLE")
            break
        
        
    if b == n:
        if connected_1.get(a) is None:
            connected_1[a] = 1
        elif connected_1[a] ==1:
            print("POSSIBLE")
            break
        
       
        
    if i==m-1:
        print("IMPOSSIBLE")

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

A = 0
B = 1
cnt = [0] * (n+1)
ab = []

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

for i in range(n+1):
    if cnt[i] == 2:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

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

A = 0
B = 1
mid = [0] * (n+1)
goal = [0] * (n+1)
ab = []

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




for i in range(n+1):
    if mid[i] == 1 and goal[i] == 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
l =[ list(map(int,input().split())) for i in range(m)]
l1 = set([i[1] for i in l if i[0]==1])
l2 = set([i[0] for i in l if i[1]==n])
l3 = l1&l2
if len(l3)>=1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

Solution (Python):
import sys

n, m, *ab = map(int, sys.stdin.read().split())
graph = [set() for _ in range(n + 1)]
for a, b in zip(*[iter(ab)] * 2):
    graph[a].add(b); graph[b].add(a)

def main():
    ans = 'IMPOSSIBLE'
    for x in graph[1]:
        if n in graph[x]:
            ans = 'POSSIBLE'
            break
    print(ans)

if __name__ ==  '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
s1=[]
sn=[]
ans='IMPOSSIBLE'
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    s1.append(b)
  elif b==n:
    sn.append(a)
s=sorted(s1+sn)
for i in range(len(s)-1):
  if s[i]==s[i+1]:
    ans='POSSIBLE'
    break
print(ans)

Solution (Python):
N,M=map(int,input().split())
s1=set()
sn=set()
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    s1.add(b)
  if b==N:
    sn.add(a)
print("POSSIBLE" if len(s1&sn)!=0 else "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):
n,m=map(int,input().split())
shima=dict()
for i in range(m):
    a,b=map(int,input().split())
    if a not in shima:
        shima[a]=[b]
    else:
        x=shima[a]
        x.append(b)
        shima[a]=x

flag=False
start=0

if 1 in shima:
    for next_shima in shima[1]:
        if next_shima in shima:
            if n in shima[next_shima]:
                flag=True 




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

Solution (Python):
def main():
    n, m = input().split()
    g1 = []
    g2 = []
    for _ in range(int(m)):
        x, y = input().split()
        if x == '1':
            g1.append(y)
        elif y == n:
            g2.append(x)
    sx = set(g1)
    sy = set(g2)
    sxy = sx.intersection(sy)
    if len(sxy):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    g1 = []
    g2 = []
    for _ in range(m):
        x, y = map(int, input().split())
        if x == 1:
            g1.append(y)
        elif y == n:
            g2.append(x)
    sx = set(g1)
    sy = set(g2)
    sxy = sx.intersection(sy)
    if len(sxy):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

Solution (Python):
n,m = list(map(int, input().split()))
lsta = [0 for i in range(n+1)]
lstb = [0 for i in range(n+1)]

for i in range(m):
    a,b = list(map(int, input().split()))
    if a==1:
        lsta[b]=1
    if b==n:
        lstb[a]=1

for i in range(n+1):
    if lsta[i]==1 and lstb[i]==1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
from collections import deque

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

f_inf = float("inf")
dist = [f_inf for _ in range(n)]
dist[0] = 0
q = deque()
q.append(0)
while q:
    u = q.popleft()
    for nv in tree[u]:
        if dist[nv] == f_inf:
            dist[nv] = dist[u] + 1
            q.append(nv)
if dist[n - 1] <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

Solution (Python):










"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:
    return a
  return gcd_(a,a % b) 
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""


def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
  n,m = readInts()
  A = set()
  B = set()
  for i in range(m):
    a,b = input().split()
    if a == '1':
      A.add(b)
    if b == str(n):
      B.add(a)
  print('POSSIBLE' if A & B else 'IMPOSSIBLE')
  
  
if __name__ == '__main__':
  main()

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:
        c.add(b)
    if b == n:
        d.add(a)
ans = "POSSIBLE" if len(c & d) else "IMPOSSIBLE"
print(ans)

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
a,b = [],[]
for x in l:
    if x[0] == 1:
        a.append(x[1])
    if x[1] == n:
        b.append(x[0])
print ('POSSIBLE' if set(a)&set(b) else 'IMPOSSIBLE')

Solution (Python):
from heapq import heappop,heappush
N,M = map(int,input().split())
T = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    T[a].append(b)
    T[b].append(a)
D = [5]*(N+1)
Q = [(0,1)]
while Q:
    cost,v = heappop(Q)
    if cost>2 or cost>=D[v]:continue
    D[v] = cost
    for c in T[v]:
        heappush(Q, (cost+1, c))
print("POSSIBLE" if D[N]<=2 else "IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
a_set = set()
b_set = set()
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        a_set.add(b)
    elif b == n:
        b_set.add(a)
if a_set & b_set:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

import queue
voi = [100] * (n + 1)
tf = [False] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put(v)
    tf[v] = True
    voi[v] = 0
    while not q.empty():
        now = q.get()
        for nex in graph[now]:
            if tf[nex]:
                continue
            q.put(nex)
            voi[nex] = voi[now] + 1
            tf[nex] = True

bfs(1)
if voi[n] <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
k,l=set(),set()
for i in range(m):
  s=list(map(int,input().split()))
  if 1 in s:
    k|={s[1]}
  if n in s:
    l|={s[0]}
print('POSSIBLE' if len(k&l)>0 else 'IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
start = []
goal = []
for i in ab:
  if i[0] == 1:
    start.append(i[1])
  elif i[1] == n:
    goal.append(i[0])
p = start + goal
if len(p) == len(list(set(p))):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')

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

a = []
b = []
for x in l:
    if x[0] == 1:
        a.append(x[1])
    if x[1] == n:
        b.append(x[0])

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

Solution (Python):
S = input().split(" ")
N = int(S[0])
M = int(S[1])
ARR = []

for i in range(M):
    ARR.append([int(s) for s in input().split(" ")])


def calculate(n,m,arr):
    tmp = []
    tmp2 = {}

    for ar in arr:
        f = ar[0]
        t = ar[1]
        if f == 1:
           tmp.append(t)

        tmp2.__setitem__((f,t),True)

    if tmp2.get((1,N)) == True:
        print("POSSIBLE")
        return

    for tm in tmp:
        if tmp2.get((tm,N)) == True:
            print("POSSIBLE")
            return


    print("IMPOSSIBLE")



calculate(N,M,ARR)

Solution (Python):
N,M=map(int,input().split())
A=[0]*M;D=[False]*N;p=-1
for i in range(M):
  a,b=map(int,input().split())
  A[i]=[a,b]
if M==1:
  print("IMPOSSIBLE")
else:
  for i in range(M):
    if A[i][1]==N:
      D[A[i][0]]=True
  for i in range(M):
    if A[i][0]==1 and D[A[i][1]]==True:
      p=1
  print("POSSIBLE" if p==1 else "IMPOSSIBLE")

Solution (Python):
def int_(num_str):
    return int(num_str) - 1


N, M = map(int, input().split())
graph = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int_, input().split())
    graph[a].add(b)
    graph[b].add(a)
for i in range(1, N-1):
    if (0 in graph[i]) and (N-1 in graph[i]):
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

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

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

flag = False
for kk in t.keys():
    if kk in fr:
        flag = True
        break

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