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


"""
Created on 2019/3/23
Solved on 2019/3/
@author: shinjisu
"""



import bisect


def getInt(): return int(input())

def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def zeros2(n, m): return [zeros(m) for i in range(n)] 

class Debug():
    def __init__(self):
        self.debug = True
 
    def off(self):
        self.debug = False
 
    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob():
    d = Debug()
    d.off()
    N, M = getIntList()
    d.dmp((N, M), 'N, M')
    ship = set()
    for i in range(M):
        a, b = getIntList()
        ship.add((a, b))
    d.dmp((ship), 'ship')
    for i in range(2, N):
        if ((1, i) in ship or (i, 1) in ship) and\
             ((i, N) in ship or (N, 1) in ship):
            return 'POSSIBLE'
    return 'IMPOSSIBLE'


ans = prob()
if ans is None:
    pass
elif type(ans) == tuple and ans[0] == 1:  
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

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

s = [0]*n
g = [0]*n

for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s[b] = 1
    if b == n:
        g[a] = 1
for i in range(n):
    if s[i] and g[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

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

Solution (Python):
from collections import deque
N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b)
    E[b-1].append(a)
print("POSSIBLE")if any(N in E[v-1] for v in E[0]) else print("IMPOSSIBLE")

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

Solution (Python):
import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0_bin = ["0"]*n
abn_bin = ["0"]*n
for x in ab0:
    ab0_bin[x[1]] = "1"
for x in abn:
    abn_bin[x[0]] = "1"

ab0_bin = "".join(ab0_bin)
abn_bin = "".join(abn_bin)

if bin(int(ab0_bin,2) & int(abn_bin, 2))[2:].count("1") > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

check_1 = []
check_N = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        check_1.append(b)
    if b == N:
        check_N.append(a)
        
if len(list(set(check_1) & set(check_N))) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
s = []
g = []
for _ in range(m):
    A, B = map(int, input().split())
    if A == 1 or B == 1:
        s.append(A * B)
    elif A == n or B == n:
        g.append(A + B - n)
if len(set(s) & set(g)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

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

e = [0]*N
for _ in range(M):
  a, b = map(int,input().split())
  if(a == 1):
    e[b] += 1
  elif(b == N):
    e[a] += 1
if(2 in e):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a].add(b)
        adj[b].add(a)
    for i in range(2, N):
        if i in adj[1] and N in adj[i]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()

data = [0]*N
for i in range(M):
  a,b = IL()
  if a == 1:
    if data[b]==1:
      print("POSSIBLE")
      break
    else:
      data[b]=1
  if b == N:
    if data[a]==1:
      print("POSSIBLE")
      break
    else:
      data[a]=1
else:
  print("IMPOSSIBLE")

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






def dijkstra():
    d[0] = 0
    q = [[0,0]]
    while q:
        dx, x = heappop(q)
        for y in v[x]:
            if d[y] > dx+1:
                d[y] = dx+1
                heappush(q,[d[y],y])
n,m = LI()
v = [[] for i in range(n)]
for i in range(m):
    a,b = LI()
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
d = [float("inf") for i in range(n)]
dijkstra()
if d[n-1] <= 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

a = [list(map(int,input().split()))for i in range(m)]

a.sort()

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

for i in range(m):
    if a[i][0] != 1:
        break
    else:
        k[a[i][1]-1] = 1

for i in range(m):
    if k[a[i][0]-1] == 1:
        if a[i][1] == n:
            print("POSSIBLE")
            sys.exit()
print("IMPOSSIBLE")

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

Solution (Python):
n, m = map(int, input().split())
l = [tuple(map(int, input().split())) for i in range(m)]
c = [[] for _ in range(n+1)]
for x in l:
    c[x[0]].append(x[1])
    c[x[1]].append(x[0])
if set(c[1])&set(c[n]):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict

def main():
    n, m = map(int, input().split())
    edges = defaultdict(list)

    for _ in range(m):
        a, b = map(int, input().split())
        edges[a].append(b)
        edges[b].append(a)
    
    if solve(n, edges):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

def solve(n, edges):
    x = set(edges[1])
    y = set(edges[n])

    if x & y:
        return True
    else:
        return False

main()

Solution (Python):
N,M=map(int,input().split())
ab=[[0,0] for _ in range(M)]
one=set()
n=set()
for i in range(M):
    ab[i][0],ab[i][1]=map(int,input().split())
    if ab[i][0]==1:
        one.add(ab[i][1])
    elif ab[i][1]==N:
        n.add(ab[i][0])
if one.isdisjoint(n):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
n,m=map(int,input().split())
a=[0]*n
b=[0]*n
for i in range(m):
    x,y=map(int,input().split())
    if x==1:
        a[y-1]+=1
    if y==n:
        b[x-1]+=1
ans='IMPOSSIBLE'
for i in range(n):
    if a[i]*b[i]>0:
        ans='POSSIBLE'
        break
print(ans)

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

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

B = []
for i in range(M):
    if A[i][0] == 1:
        B.append(A[i][1])
    if A[i][1] == N:
        B.append(A[i][0])
        
if len(set(B)) != len(B):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
input = sys.stdin.readline
N , M = map(int,input().split())
L = []
transit1 = set()
transit2 = set()
for _ in range(M):
    t = tuple(map(int,input().split()))
    L.append(t)
for x in L :
    if x[1] == N:
        transit1.add(x[0])
    if x[0] == 1:
        transit2.add(x[1])
if transit1 & transit2 == set():
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N , M = map(int,input().split())
L = []
transit1 = set()
transit2 = set()
for _ in range(M):
    t = tuple(map(int,input().split()))
    L.append(t)
for x in L :
    if x[1] == N:
        transit1.add(x[0])
    if x[0] == 1:
        transit2.add(x[1])
if transit1 & transit2 == set():
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N , M = map(int,input().split())
L = []
transit1 = set()
transit2 = set()
for _ in range(M):
    t = tuple(map(int,input().split()))
    L.append(t)
for x in L :
    if x[1] == N:
        transit1.add(x[0])
    if x[0] == 1:
        transit2.add(x[1])
if transit1 & transit2 == set():
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N , M = map(int,input().split())
L = []
transit = set()
for _ in range(M):
    t = tuple(map(int,input().split()))
    L.append(t)
for x in L :
    if x[1] == N:
        transit.add(x[0])
for x in L:
    if x[0] == 1:
        if x[1] in transit:
            print("POSSIBLE")
            quit()
print("IMPOSSIBLE")

Solution (Python):
N , M = map(int,input().split())
L = []
transit = set()
for _ in range(M):
    t = tuple(map(int,input().split()))
    L.append(t)
for x in L :
    if x[1] == N:
        transit.add(x[0])
for x in L:
    if x[0] == 1:
        if x[1] in transit:
            print("POSSIBLE")
            quit()
print("IMPOSSIBLE")

Solution (Python):

N,M=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for m in range(M):
	I=list(map(int,input().split()))
	if I[0]==1:
		A.append(I[0])
		B.append(I[1])
	elif I[1]==N:
		C.append(I[0])
		D.append(I[1])
if len(set(B)&set(C))>0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
Ship_1,Ship_n=[False]*n,[False]*n
for _ in range(m):
    a,b=map(int,input().split())
    if a==1:
        Ship_1[b-1]=True
    if a==n:
        Ship_n[b-1]=True
    if b==1:
        Ship_1[a-1]=True
    if b==n:
        Ship_n[a-1]=True
for i in range(n):
    if Ship_1[i] and Ship_n[i]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
edge = [[] for _ in range(n)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
if n - 1 in edge[0]:
    print("POSSIBLE")
    exit()
else:
    for e in edge[0]:
        if n -1 in edge[e]:
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

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

tree = [[] for i in range(n)]
for i in range(m):
  tmp_a,tmp_b = map(int,input().split())
  tree[tmp_a-1].append(tmp_b-1)
  tree[tmp_b-1].append(tmp_a-1)
def bfs():
  q = deque()
  visited =[False]*n
  visited[0]=True
  for elem in tree[0]:
    q.append([elem,1])
  while q:
    i,cnt = q.popleft()
    if i == n-1 and cnt <=2 :
      print("POSSIBLE")
      exit()
    if not visited[i]:
      visited[i] = True
      if cnt<=1:
        for elem in tree[i]:
          q.append([elem,cnt+1])

bfs()
print("IMPOSSIBLE")

Solution (Python):
from collections import deque

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

island_map = {}
for a,b in route:
    if a not in island_map:
        island_map[a] = [b]
    else:
        island_map[a].append(b)

first_island = deque()
first_island += island_map[1]
second_island = deque()

for i in first_island:
    if i in island_map:
        second_island += island_map[i]
    else:
        pass
    for j in second_island:
        if j == N:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
lst = set()
fst = set()
for i in range(m): 
  r = list(map(int,input().split()))
  if r[1] == n:
    lst.add(r[0])
  elif r[0] == 1:
    fst.add(r[1])
print('IMPOSSIBLE' if len(fst & lst) == 0 else 'POSSIBLE')

Solution (Python):
from collections import deque
H, W = map(int, input().split())
k=[0]*200000
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k[tb-1]+=1
    if tb == H:
        k[ta-1]+=1
s = 0
for i in range(len(k)):
    if k[i]>=2:s=1
if s ==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import deque
H, W = map(int, input().split())
k=[0]*200000
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k[tb-1]+=1
    if tb == H:
        k[ta-1]+=1
s = 0
for i in range(len(k)):
    if k[i]>=2:s=1
if s ==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N,M=map(int,input().split())
from collections import defaultdict

d1=defaultdict(int)
d2=defaultdict(int)

for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        d1[b]=1
        if d2[b]==1:
            print('POSSIBLE')
            exit()
    if b==N:
        d2[a]=1
        if d1[a]==1:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

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

e = [0]*N
for _ in range(M):
  a, b = map(int,input().split())
  if(a == 1):
    e[b] += 1
  elif(b == N):
    e[a] += 1
if(2 in e):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
n, m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
nl = [[0,0] for i in range(n+1)]
for a,b in s:
    if a == 1: nl[b][0] = 1
    if b == n: nl[a][1] = 1
ans = "POSSIBLE" if [1,1] in nl else "IMPOSSIBLE"
print(ans)

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

Solution (Python):
from collections import defaultdict
N,M = map(int,input().split())
dic = defaultdict(list)
for i in range(M):
    a,b = map(int,input().split())
    dic[a].append(b)
def solve(dic):
    for s in dic[1]:
        for m in dic[s]:
            if m == N:
                return True
if solve(dic): print('POSSIBLE')
else: print('IMPOSSIBLE')

Solution (Python):
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
J = [False]*(N+1)
K = [False]*(N+1)
J[0] = False
K[N] = False
J[1] = False
K[1] = False
for j in range(M):
  if L[j][0] == 1:
    J[L[j][1]] = True
for k in range(M):
  if L[k][1] == N:
    K[L[k][0]] = True
flag = False
for l in range(N+1):
  if J[l] and K[l]:
    flag = True
    break
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):



















from collections import defaultdict, Counter
import math
from bisect import bisect_left, bisect_right
import numpy as np


n, m= map(int,input().split())
fune = []
for _ in range(m):
    li = list(map(int,input().split()))
    if 1 in li:
        li.remove(1)
        fune.append(li[0])
    elif n in li:
        li.remove(n)
        fune.append(li[0])

if len(fune)-len(set(fune))>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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


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

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

Solution (Python):
N,M = map(int,input().split())
voy = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    voy[a-1].append(b)
alen = len(voy[0])
flag = 0
for j in range(alen):
    qu = voy[0][j]-1
    if N in voy[qu]:
        print("POSSIBLE")
        flag = 1
        break
if flag == 0:
    print("IMPOSSIBLE")

Solution (Python):
def solve(N, M, ABs):
    from1 = set()
    toN = set()
    for a, b in ABs:
        a, b = min(a, b), max(a, b)
        if a == 1:
            from1.add(b)
        if b == N:
            toN.add(a)
    return "POSSIBLE" if len(from1.intersection(toN)) else "IMPOSSIBLE"

if __name__ == "__main__":
    N, M = map(int, input().split(" "))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))

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

for i in range(m):
    if a[i][0] == "1":
        A.append(a[i][1])
    if a[i][1] == str(n):
        B.append(a[i][0])
print("POSSIBLE" if set(A) & set(B) else "IMPOSSIBLE")

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

    from_1 = set()
    to_N = set()
    for i in range(M):
        u, v = [int(x) for x in input().split()]

        if u == 1:
            from_1.add(v)

        if v == N:
            to_N.add(u)

    ss = from_1.intersection(to_N)
    return len(ss) != 0


def main():
    ans = solve()
    if ans:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

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

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

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

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

for i in range(m):
    s, g = map(int, input().split())
    if s == 1:
        G.add(g)
    if g == n:
        S.add(s)

if len(S&G) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M = map(int,input().split())
onelist,nlist = [],[]
for i in range(M):
    aa,bb = map(int,input().split())
    if aa == 1:
        onelist.append(bb)
    if bb == N:
        nlist.append(aa)


if len(set(onelist) & set(nlist)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n,m=IL()
nl=[[] for i in range(n)]
for i in range(m):
    a,b=IL()
    nl[a-1].append(b-1)
for i in nl[0]:
    if n-1 in nl[i]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
p = [False]*(N+1)
for _ in range(M):
    res = None
    a, b = map(int, input().split())
    if a == 1:
        res = b
    if b == N:
        res = a
    if res is not None:
        if p[res]:
            print('POSSIBLE')
            exit()
        else:
            p[res] = True
print('IMPOSSIBLE')

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
fir = []
sec = []

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        fir.append(b)
    elif a == n:
        sec.append(b)
    if b == 1:
        fir.append(a)
    elif b == n:
        sec.append(a)
fir.sort()
sec.sort()
flag = True
for i in fir:
    j = 0
    while flag and sec:
        if i > sec[j]:
            del sec[j]
        elif i == sec[j]:
            print("POSSIBLE")
            flag = False
        else:
            break
if flag == True:
    print("IMPOSSIBLE")

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

print("POSSIBLE" if A[0] & A[N-1] != set() 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):
import sys
n,m = map(int,input().split())
if m == 1:
    input()
    print('IMPOSSIBLE')
    sys.exit()
mid = [];move = [None]*m
for i in range(m):
    a,b = map(int,input().split())
    move[i] = [a,b]
    if a == 1:mid.append(b)
    if b == 1:mid.append(a)
    if a == n:mid.append(b)
    if b == n:mid.append(a)
check = False
if len(mid) != len(set(mid)):check = True
if check == True:print('POSSIBLE')
else:print('IMPOSSIBLE')

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


mylist = [[int(i) for i in input().split()] for i in range(m)] 


mylist1=[mylist[i][1] for i in range(m) if mylist[i][0]==1]


mylist2=[mylist[i][0] for i in range(m) if mylist[i][1]==n]



if len(set(mylist1) & set(mylist2)) > 0:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

a=[]
b=[]
l1=[False for i in range(n)]
ln=[False for i in range(n)]

for i in range(m):
    c=[int(i) for i in input().split()]
    a.append(c[0])
    b.append(c[1])
    if c[0]==1 or c[1]==1:
        l1[c[0]*c[1]]=True
    if c[0]==n or c[1]==n:
        ln[c[0]*c[1]//n]=True

for i in range(n):
    if l1[i] and ln[i]:
        print("POSSIBLE")
        sys.exit()

print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
matrix = [[] for i in range(N)]
check1 = [0] * N
check1[0] = 1

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

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

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

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

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

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

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

from1 = set()
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.add(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)

Solution (Python):
N,M = map(int,input().split())
edge = []
p = 'POSSIBLE'
i = 'IMPOSSIBLE'
for _ in range(M):
    edge.append(tuple(map(int,input().split())))

from1 = set()
is_reach = False
for go,to in sorted(edge,key=lambda x:x[0]):
    if go == 1:
        from1.add(to)
    else:
        if go in from1 and to == N:
            is_reach = True
            break
print(p if is_reach else i)

Solution (Python):
def abc068_c():
    from collections import Counter
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    candidates = []

    for i in range(m):
        if ab[i][0] == 1:
            candidates.append(ab[i][1])
        elif ab[i][1] == n:
            candidates.append(ab[i][0])

    if max(Counter(candidates).values()) >= 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


abc068_c()

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

ab = []
for _ in range(M):
  ab.append(tuple(map(int, input().strip().split())))

from1 = set()
is_reach = False
for a, b in sorted(ab, key=lambda x: x[0]):
  if a == 1:
    from1.add(b)
  else:
    if a in from1 and b == N:
      is_reach = True
      break
if is_reach:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
Check1 = [False]*n
Check2 = [False]*n
for i in range(m):
    a,b = map(int,input().split())
    if a ==1:
        Check1[b-1] = True
    elif a == n:
        Check2[b-1] = True
    elif b == 1:
        Check1[a-1] = True
    elif b == n:
        Check2[a-1] = True
for i in range(n):
    if Check1[i] and Check2[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

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

for i in range(len(tmp)):
  if(check[i] == 1 and tmp[i] == 1):
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

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

if(2 in tmp):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
"""

Solution (Python):
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)

for e1 in g[1]:
    for e2 in g[e1]:
        if e2 == N:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
list=[[] for i in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    list[a].append(b)
    list[b].append(a)
c=0
for i in list[N]:
    if list[i]:
        list[i].sort()
        if list[i][0]==1:
            c=1
            break
if c==1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
def main():
    n, m = map(int, input().split())
    ss = [set(), set()]
    for _ in range(m):
        a, b = map(lambda s: int(s) - 1, input().split())
        if a == 0:
            ss[0].add(b)
        elif a == n - 1:
            ss[1].add(b)
        if b == 0:
            ss[0].add(a)
        elif b == n - 1:
            ss[1].add(a)
    if ss[0] & ss[1]:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
ship1 = set()
ship2 = set()
for _ in range(m):
	a, b = map(int, input().split())
	if a==1:
		ship1.add(b)
	if b==n:
		ship2.add(a)
if len(ship1&ship2) != 0:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
L=[];l=[]
for k in range(n):
  L.append(0)
for i in range(m):
  x=list(map(int,input().split()))
  l.append(x)
  if x[0]==1:
    L[x[1]]+=1
  if x[1]==1:
    L[x[0]]+=1
  if x[0]==n:
    L[x[1]]+=1
  if x[1]==n:
    L[x[0]]+=1
if max(L)==2:print('POSSIBLE')
else:print('IMPOSSIBLE')

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

Start=[]
Goal=[]

for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        Start.append(b)
    elif b==1:
        Start.append(a)
    if a==N:
        Goal.append(b)
    elif b==N:
        Goal.append(a)
    
S=set(Start)
G=set(Goal)
if len(S&G)>0:
    print("POSSIBLE")
elif len(S&G)==0:
    print("IMPOSSIBLE")

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

a = [tuple(map(int, input().split())) for _ in range(m)]

p = []
q = []

for i in range(m):
    if a[i][0] == 1:
        p.append(a[i][1])
    elif a[i][1] == n:
        q.append(a[i][0])

if len(set(p)&set(q)) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
x=list(map(int,input().split()))
flg=0
a=[[] for i in range(x[0])]
for i in range(x[1]):
    y=list(map(int,input().split()))
    a[y[0]].append(y[1])
for i in range(1,x[0]):
    a[i].sort(reverse=True)
for i in range(len(a[1])):
    if len(a[a[1][i]]) > 0 and a[a[1][i]][0]==x[0]:
        flg=1
        break
if flg==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N,M = list(map(int,input().split()))
path = [[False,False] for i in range(N)]
flag=False
for i in range(M):
    a,b = list(map(int,input().split()))
    if a==N:
        if path[b-1][0]:
            flag=True
            
        path[b-1][1]=True
    if a==1:
        if path[b-1][1]:
            flag=True
            
        path[b-1][0]=True
    if b==N:
        if path[a-1][0]:
            flag=True
            
        path[a-1][1]=True
    if b==1:
        if path[a-1][1]:
            flag=True
            
        path[a-1][0]=True

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

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

to_one = [False] * N
to_N = [False] * N
for m in range(M):
    a, b = map(int, input().strip().split(" "))
    if a == 1:
        to_one[b] = True
    if b == N:
        to_N[a] = True

res = False
for n in range(2, N):
    if to_N[n] and to_one[n]:
        print("POSSIBLE")
        res = True
        break

if not res:
    print("IMPOSSIBLE")

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

to_one = [False] * N
to_N = [False] * N
for m in range(M):
    a, b = map(int, input().strip().split(" "))
    if a == 1:
        to_one[b] = True
    if b == N:
        to_N[a] = True

res = False
for n in range(2, N):
    if to_N[n] and to_one[n]:
        print("POSSIBLE")
        res = True
        break

if not res:
    print("IMPOSSIBLE")

Solution (Python):
from sys import stderr, setrecursionlimit
from functools import reduce
from operator import add
from collections import defaultdict as dd
setrecursionlimit(2147483647)
def f(): return [int(i) for i in input().split()]
def yes(n): print("Yes" if n else "No")
def debug(*x, sep=" ", end="\n"):
    for item in x:
        stderr.write(str(item))
        stderr.write(sep)
    stderr.write(end)

n, m = f()
graph = dd(list)
for i in range(m):
    a, b = f()
    graph[a].append(b)

for a in graph[1]:
    if n not in graph[a]:
        continue
    print("POSSIBLE")
    break
else:
    print("IMPOSSIBLE")