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())
c=[]
d=[]
for _ in range(m):
  a,b=map(int,input().split())
  if a==1:
    c.append(b)
  elif b==n:
    d.append(a)
if len(set(c)&set(d))!=0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

g = [[] for i in range(N + 1)]
for pi in p:
	g[pi[0]].append(pi[1])
	g[pi[1]].append(pi[0])

for i in g[1]:
	if N in g[i]:
		print("POSSIBLE")
		exit()
print("IMPOSSIBLE")

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

g = [[] for i in range(N + 1)]
for pi in p:
	g[pi[0]].append(pi[1])
	g[pi[1]].append(pi[0])

for i in g[1]:
	if N in g[i]:
		print("POSSIBLE")
		exit()
print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
IN,OUT={},{}
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        if b in OUT:
            print("POSSIBLE")
            exit()
        else:IN[b]=1
    if b==n:
        if a in IN:
            print("POSSIBLE")
            exit()
        else:OUT[a]=1
print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
dat_m = [[] for x in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    dat_m[a].append(b)
c = False
for i in dat_m[1]:
    if n in dat_m[i]:
        c = True
print("POSSIBLE" if c else "IMPOSSIBLE")

Solution (Python):
from collections import deque
n, m = map(int, input().split())
dat = deque([])
dat2 = deque([])
dat_finish = [False] * (n + 1)

for i in range(m):
    a, b = map(int, input().split())
    dat.append((a, b))
    dat2.append((a, b))

for i in range(m):
    a, b = dat.pop()
    if b == n:
        dat_finish[a] = True

c = False
for i in range(m):
    a, b = dat2.pop()
    if a == 1:
        if dat_finish[b]:
            c = True

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
dat = deque([])
dat_finish = [False] * (n + 1)

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

for i in range(m):
    a, b = dat[i]
    if b == n:
        dat_finish[a] = True

c = False
for i in range(m):
    a, b = dat[i]
    if a == 1:
        if dat_finish[b]:
            c = True

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
dat_m = [deque([]) for x in range(n + 1)]

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

c = False
for i in dat_m[1]:
    if n in dat_m[i]:
        c = True

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

Solution (Python):
from collections import deque
n, m = map(int, input().split())
dat_m = []
for i in range(n + 1):
    dat_m.append(deque([]))

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

c = False
for i in dat_m[1]:
    if n in dat_m[i]:
        c = True

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

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

A = []
B = []
buff = [0 for i in range(N+1)]
buff2 = [0 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.append(b)
        
        buff[b] = 1
    if b == N:
        B.append(a)
        buff2[a] = 1

for i in range(N+1):
    if buff[i] == 1 and buff2[i] == 1:
        print('POSSIBLE')
        exit()






















print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
dat = []
dat_m = [[]] * (n+1)
dat_finish = [False] * (n+1)

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


for i in range(m):
    a,b = dat[i]
    if b == n:
        dat_finish[a] = True


c = False
for i in range(m):
    a,b = dat[i]
    if a == 1:
        if dat_finish[b]:
            c = True

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

Solution (Python):
N, M = map(int, input().split())
s = set()
for _ in range(M):
    a, b = map(int, input().split())
    s.add((a, b))
result = "IMPOSSIBLE"
for m in range(2, N):
    if (1, m) in s and (m, N) in s:
        result = "POSSIBLE"
        break
print(result)

Solution (Python):
n,m = map(int,input().split())
AB = {}
ans = 'IMPOSSIBLE'
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        if b in AB:
            if AB[b] == n:
                ans = 'POSSIBLE'
                break
        else:
            AB[b] = 1


    if b == n:
        if a in AB:
            if AB[a] == 1:
                ans = 'POSSIBLE'
                break
        else:
            AB[a] = n
print(ans)

Solution (Python):

from collections import defaultdict

import sys
input = sys.stdin.readline

def main():
    num_land, num_ship = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num_ship)]

    move_dic = defaultdict(set)

    for i in range(num_ship):
        a, b = data[i]
        move_dic[a].add(b)
        move_dic[b].add(a)

    next_land = move_dic[1]
    for ele in next_land:
        aaa = move_dic[ele]
        if num_land in aaa:
            print('POSSIBLE')
            break
    else:
        print('IMPOSSIBLE')

if __name__ == '__main__':
    main()

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

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().rstrip().split())
    s, d = set(), set()
    for _ in range(m):
        a, b = map(int, input().rstrip().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):

import sys
input = sys.stdin.readline

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


if __name__ == "__main__":
    main()

Solution (Python):
n, m = [int(i) for i in input().split()]
forward = [0 for i in range(n)]
backward = [0 for i in range(n)]
for i in range(m):
    a, b = [int(_) for _ in input().split()]
    if a == 1:
        forward[b] = 1
    elif  b == 1:
        forward[a] = 1
    elif a == n:
        backward[b] = 1
    elif b == n:
        backward[a] = 1
flag = False
for i in range(n):
    if forward[i] == 1 and backward[i] == 1:
        flag = True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict

N, M = map(int, input().split())
E = defaultdict(list)
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
for i in range(1, N+1):
    if 1 in E[i] and N in E[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
ab=[map(int,input().split()) for _ in range(m)]
t1=set()
t2=set()
for a,b in ab:
    if a==1:
        t1.add(b)
    if b==n:
        t2.add(a)
for t in t1:
    if t in t2:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

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


for i in range(m):
	if ls[i][0]==1:
		ls1.append(ls[i][1])
	elif ls[i][1]==1:
		ls1.append(ls[i][0])
	elif ls[i][0]==n:
		lsn.append(ls[i][1])
	elif ls[i][1]==n:
		lsn.append(ls[i][0])

if len(set(ls1)&set(lsn))!=0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Solution (Python):

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

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

if len(set(li))==len(li): print('IMPOSSIBLE')
else: print('POSSIBLE')

Solution (Python):


num = list(map(int,input().split()))
N = num[0]
M = num[1]

a = []
b = []

firstisland = []
islandlast = []

for i in range(M):
    num = list(map(int,input().split()))
    a.append(num[0])
    b.append(num[1])
    if (num[0] == 1):
        firstisland.append(num[1])
    if (num[1] == N):
        islandlast.append(num[0])

island = set(firstisland) & set(islandlast)

if (len(island) > 0):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

for i in range(M):
  if li[i][0]==1:
    s.append(li[i][1])
  else:
    break

li.sort(key=lambda x: x[1],reverse=True)

for i in range(M):
  if li[i][1]==N:
    g.append(li[i][0])
  else:
    break

if len(set(s)&set(g))>0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

ato = []
bto = []

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

ato = set(ato)
bto = set(bto)

dec = ato & bto

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

Solution (Python):

n, m = map(int, input().split())
arr = [[False, False] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        arr[b - 1][0] = True
    if b == n:
        arr[a - 1][1] = True

for x in arr:
    if x[0] and x[1]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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

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

islands = {}
for i in range(M):
    a,b = map(int, input().split())
    if a not in islands:
        islands[a] = {}
    if b not in islands:
        islands[b] = {}
    islands[a][b] = islands[b][a] = 1

if N not in islands:
    print('IMPOSSIBLE')
    exit()
for i in islands[1].keys():
    if i in islands[N]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
A=[]
B=[]
for _ in range(m):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
one=[]
des=[]
for i in range(m):
    if A[i]==1:
        one.append(B[i])
    if B[i]==1:
        one.append(A[i])
for j in range(m):
    if A[j]==n:
        des.append(B[j])
    if B[j]==n:
        des.append(A[j])
one=set(one)
des=set(des)
ans=one & des
if len(ans)>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

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

  l=[]
  for _ in range(m):
    a,b=LI()

    if a==1:
      l.append(b)
    elif b==n:
      l.append(a)

  x=len(l)
  y=len(list(set(l)))

  if x!=y:
    return 'POSSIBLE'
  return 'IMPOSSIBLE'

print(main())

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

n, m = map(int, input().split())
Island_1 = []
Island_n = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        Island_1.append(b)
    if b == n:
        Island_n.append(a)
if len(set(Island_1) & set(Island_n)) == 0:
    ans = 'IMPOSSIBLE'
else:
    ans = 'POSSIBLE'
print(ans)

Solution (Python):
n,m = (int(i) for i in input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
l,r = {k:False for k in range(1,n+1)},{k:False for k in range(1,n+1)}
for a,b in ab:
    if a == 1:  l[b] = True
    if b == n:  r[a] = True
for i in range(1,n+1):
    if r[i] is True and l[i] is True:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):

import sys

YES = "POSSIBLE"  
NO = "IMPOSSIBLE"  

def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(M):
        conn[a[i] - 1].append(b[i] - 1)
        conn[b[i] - 1].append(a[i] - 1)
    ret = NO
    for n in conn[0]:
        if N - 1 in conn[n]:
            ret = YES
    print(ret)
    return


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

if __name__ == '__main__':
    main()

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

from_one = set()
to_n = set()
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        from_one.add(b)
    if b == N:
        to_n.add(a)

if len(from_one & to_n) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A[b - 1] =1
    if b == N:
        B[a - 1] = 1

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

print('IMPOSSIBLE')

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

start = [0] * M
end = [0] * M

s_middle = []
middle_e = []

for m in range(M):
    line = list(map(int, input().split()))
    start[m] = line[0]
    end[m] = line[1]
    
    if start[m] == 1:
        s_middle.append(end[m])
    if end[m] == N:
        middle_e.append(start[m])
        
if not s_middle or not middle_e:
    print('IMPOSSIBLE')
    sys.exit()

if set(s_middle) & set(middle_e):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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


lst = [0] * N

flag = False 
for i in range(M): 
    a, b = map(int,input().split())
    if a == 1: 
        if lst[b-1] == 1: 
            flag = True
        else:
            lst[b-1] = 1 
    if b == N: 
        if lst[a-1] == 1: 
            flag = True
        else:
            lst[a-1] = 1 

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

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

lst = [0] * N

flag = False
for i in range(M):
    a, b = map(int,input().split())
    if a == 1:
        if lst[b-1] == 1:
            flag = True
        else:
            lst[b-1] = 1
    if b == N:
        if lst[a-1] == 1:
            flag = True
        else:
            lst[a-1] = 1

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

Solution (Python):
n,m=map(int,input().split())
d={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  d[a-1].add(b-1)
  d[b-1].add(a-1)
f=False
for x in d[0]:
  if n-1 in d[x]:
    f=True
    break
print('POSSIBLE' if f else 'IMPOSSIBLE')

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

def main():
    n = N
    s = []
    g = []
    for m in range(M):
        a, b = [int(s) for s in input().split()]
        if a == 1:
            s.append(b)
        if b == n:
            g.append(a)
    ans = 'POSSIBLE' if len(set(s) & set(g)) > 0 else 'IMPOSSIBLE'
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import math
import fractions
import copy

def j(q):
    if q==1: print("POSSIBLE")
    elif q == 0:print("IMPOSSIBLE")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in a:
        print(i)
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)



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










right = set()
left = set()
for i in range(m):
    a = [int(i) for i in input().split()]
    if a[0] == 1:
        right.add(a[1])
    elif a[1] == n:
        left.add(a[0])
right = right & left
if len(right):j(1)
j(0)

Solution (Python):
n,m=map(int,input().split())
l=[set(map(int,input().split())) for _ in range(m)]
S=set()
G=set()
for x in l:
	if 1 in x:S.add(max(x))
	elif n in x:G.add(min(x))
S=sorted(S)
G=sorted(G)
i=0
Glen=len(G)
for x in S:
	if i==Glen:break
	elif G[i]<x:
		while i<Glen and G[i]<x:
			i+=1
	if i<Glen and x==G[i]:
		print('POSSIBLE')
		exit()
print('IMPOSSIBLE')

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

sa = set()
sb = set()

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

Solution (Python):



import sys

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

memo = [[0, 0] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().rstrip().split(' '))
    a -= 1
    b -= 1
    
    if a == 0:
        memo[b][0] = 1
    elif b == N-1:
        memo[a][1] = 1
        
for i in range(N):
    if memo[i][0] == 1 and memo[i][1] == 1:
        print('POSSIBLE')
        sys.exit()
        
print('IMPOSSIBLE')

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

connect_to_1 = []
connect_to_N = []
for i in range(M):
  if edges[i][0] == 1:
    connect_to_N.append(edges[i][1])
  if edges[i][1] == N:
    connect_to_1.append(edges[i][0])

if len(set(connect_to_1) & set(connect_to_N)) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
from collections import defaultdict
N ,M = list(map(int,input().split(" ")))
di = defaultdict(lambda :[])
for _ in range(M):
    a,b = list(map(int,input().split(" ")))
    di[a].append(b)
    di[b].append(a)
ans = "IMPOSSIBLE"
for v in di.values():
    if 1 in v and N in v:
        ans = "POSSIBLE"
        break
print(ans)

Solution (Python):
N, M = map(int, input().split())
startlist = [False]
goallist = [False]
for i in range(0, N):
	startlist.append(False)
	goallist.append(False)
for i in range(0, M):
	a, b = map(int, input().split())
	if a == 1: startlist[b] = True
	if b == N: goallist[a] = True
ans = 'IMPOSSIBLE'
for i in range(0, N+1):
	if startlist[i] and goallist[i]:
		ans = 'POSSIBLE'
		break
print(ans)

Solution (Python):

n, m = [ int(v) for v in input().split() ]
first_ship = []
second_ship = []

for i in range(m):
	start, end = [ int(v) for v in input().split() ]
	if start == 1:
		first_ship.append(end)
	if end == n:
		second_ship.append(start)

if len(set(first_ship+second_ship)) == len(first_ship) + len(second_ship):
	print("IMPOSSIBLE")
else:
	print("POSSIBLE")

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


ans = "IMPOSSIBLE"
for l in land[0]:
	if n-1 in land[l]:
		ans = "POSSIBLE"
		break
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

def main():
  n,m=LI()
  
  l=[]
  for _ in range(m):
    a,b=LI()

    if a==1:
      l.append(b)
    elif a==n:
      l.append(b)
    elif b==n:
      l.append(a)

  if len(l)!=len(list(set(l))):
    return 'POSSIBLE'

  return 'IMPOSSIBLE'

print(main())

Solution (Python):
N, M = map(int, input().split())
C = set()
D = set()
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        C.add(b)
    if b == 1:
        C.add(a)
    if a == N:
        D.add(b)
    if b == N:
        D.add(a)
print('POSSIBLE' if C & D else 'IMPOSSIBLE')

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

for i in range(m):
    ta,tb = map(int, input().split())
    if not ta in a:
        a[ta] = [tb]
    else:
        a[ta].append(tb)

ans=False
for i in a[1]:
    if not i in a: continue
    if n in a[i]:
        ans = True
        
print(("IMPOSSIBLE","POSSIBLE")[ans])

Solution (Python):
n,*t=map(int,open(0).read().split())
e=[[]for i in range(n+1)]
for a,b in zip(t[1::2],t[2::2]):
  e[a].append(b)
  e[b].append(a)
i=0
for v in e[1]:
  for w in e[v]:
    if w==n:
      i=2
print('IMPOSSIBLE'[i:])

Solution (Python):
n,*t=map(int,open(0).read().split())
e=[[]for i in range(n+1)]
for a,b in zip(t[1::2],t[2::2]):
  e[a].append(b)
  e[b].append(a)
i=0
for v in e[1]:
  for w in e[v]:
    if w==n:
      i=2
print('IMPOSSIBLE'[i:])

Solution (Python):
N,M=map(int,input().split())
ab=list(list(map(int,input().split()))for _ in range(M))
graph=list([0]*N for _ in range(2))
for a,b in ab:
    if a==1:
        graph[0][b-1]=1
    elif b==N:
        graph[1][a-1]=1

for i,j in zip(graph[0],graph[1]):
    if i==1 and j==1:
        print('POSSIBLE')
        exit()
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>b:
    a,b = b,a
  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):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
L = [[int(v) for v in input().split()] for _ in range(M)]
m = [set() for _ in range(N)]

for l, r in L:
    l -= 1
    r -= 1
    
    m[l].add(r)
    
N -= 1
for v in m[0]:
    if N in m[v]:
        print("POSSIBLE")
        exit()
        
print("IMPOSSIBLE")

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

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

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

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

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys

N, M = map(int, input().split())
ship = [[] for i in range(N+1)]

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

flag = 0
for i in ship[1]:
    if N in ship[i]:
        flag = 1
if flag == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
via=set()
viaa=set()
for i in range(m):
  a,b=map(int,input().split())
  if a ==1 : 
    via.add(b)
  if b ==n:
    viaa.add(a)
if via.isdisjoint(viaa):
  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(key = lambda x:x[0])

import queue
import sys
q = queue.Queue()
memo = [True] * (N+1)
memo[1] = False
cnt = 0
for i in range(M):
    if ab[i][0] == 1:
        q.put(ab[i][1])
        cnt += 1
    else :break
ab2 = [[0]] * (N+1)
for j in range(i,M):
    ab2[ab[j][0]] = ab2[ab[j][0]] + [ab[j][1]]
idx = 0
while not q.empty():
    s = q.get()
    memo[s] = False
    if s==N:
        print('POSSIBLE')
        sys.exit()
    if idx < cnt:
        for i in ab2[s][1:]:
            if memo[i]: q.put(i)
    idx += 1
print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
l=[]
m=[]
for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        l.append(b)
    elif b==N:
        m.append(a)
o=set(l)&set(m)

if len(o):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

l = []
r = []
for x, y in X:
    if x == 1:
        l.append(y)
    if y == N:
        r.append(x)
        
print('POSSIBLE' if len(set(l) & set(r)) > 0 else 'IMPOSSIBLE')

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

s, e = set(), set()
for ab in AB:
    a, b = ab
    if a == 1:
        s.add(b)
    elif b == N:
        e.add(a)
if len(s & e) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

s, e = set(), set()
for ab in AB:
    a, b = ab
    if a == 1:
        s.add(b)
    elif b == N:
        e.add(a)
if len(s & e) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(m)]
gragh = [[] for i in range(n+1)]
for e in edge:
    gragh[e[0]].append(e[1])
    gragh[e[1]].append(e[0])
start = 1
for k in gragh[start]:
    if n in gragh[k]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

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

  l=[]

  for _ in range(m):
    a,b=LI()
    if a==1:
      l.append(b)
    elif b==1:
      l.append(a)
    elif a==n:
      l.append(b)
    elif b==n:
      l.append(a)

  if len(l)==len(set(l)):
    print('IMPOSSIBLE')
  else:
    print('POSSIBLE')

main()

Solution (Python):
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
flag=False
for i in g[1]:
  for j in g[i]:
    if j==n:
      flag=True
if flag==True:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

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

if len(mae&ato) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):


def solve():
    N, M = list(map(int, input().split()))
    """方針
    from1 := 1から行ける島番号のリスト
    canN[i] := 島iがNに行くことができるか否か
    from1の中の島bのうち、canN[b] == Trueのものがあるならば、POSSIBLE
    計算量はO(N)
    """
    from1 = []
    canN = [False] * (N+1)
    for i in range(M):
        a, b = list(map(int, input().split()))
        if a == 1:
            from1.append(b)
        elif b == N:
            canN[a] = True
    
    for b in from1:
        if canN[b]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")
        

if __name__ == "__main__":
    solve()

Solution (Python):


def solve():
    N, M = list(map(int, input().split()))
    """
    from1 := 1から行ける島番号のリスト
    canN[i] := 島iがNに行くことができるか否か
    from1とtoNの両方に同じ島番号が存在するとき、POSSIBLE
    """
    from1 = []
    canN = [False] * (N+1)
    for i in range(M):
        a, b = list(map(int, input().split()))
        if a == 1:
            from1.append(b)
        elif b == N:
            canN[a] = True
    
    for b in from1:
        if canN[b]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")
        

if __name__ == "__main__":
    solve()

Solution (Python):
N,M = map(int, input().split())
AtN,Bf1 = set(),set()
for i in range(M):
    a,b = map(int, input().split())
    if a == 1:
        Bf1.add(b)
    elif b == N:
        AtN.add(a)

if (any((b in AtN) for b in Bf1)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

for s,e in ship:
    if s==1:
        mid_first.append(e)
    if e==n:
        mid_last.append(s)
print("POSSIBLE" if len(set(mid_first) & set(mid_last))>0 else "IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
lst_1_to_i = [False] * N
lst_i_to_N = [False] * N
ans = "IMPOSSIBLE"


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


for x, y in zip(lst_1_to_i, lst_i_to_N):
    if x and y:
        ans = "POSSIBLE"


print(ans)

Solution (Python):
N,M = [int(x) for x in input().split()]
dict={1:[]}
for _ in range(M):
    a,b = [int(x) for x in input().split()]
    if(a==1):
        dict[1].append(b)
    elif(b==N):
        dict[a]=b
flag = False
for i in dict[1]:
    if(i in dict):
        flag = True
        break
if(flag):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):


import math



def main():
  N,M = map(int, input().split())
  route = [0 for _ in range(N+1)]

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

  if max(route) >= 2:
    return True
  else:
    return False


if __name__ == "__main__":
  if main():
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')

Solution (Python):
a=[]
b={}
n,m=map(int,input().split())
for _ in range(m):
	i,j=map(int,input().split())
	if i==1:
		a.append(j)
	elif j==n:
		b[i]=1
for i in a:
	if i in b:
		print('POSSIBLE')
		break
else:
	print('IMPOSSIBLE')

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

goal, 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==goal:
    sa.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")