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 = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for _ in range(M)]
to_halfway = [0]*(N+1)
from_halfway = [0]*(N+1)
for a, b in AB:
    if a == 1:
        to_halfway[b] = 1
    elif b == N:
        from_halfway[a] = 1
for i in range(N+1):
    if to_halfway[i]*from_halfway[i] == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
n, m = [int(i) for i in input().split()]
a = [0 for i in range(m)]
b = [0 for i in range(m)]
semiGoal = [0 for i in range(n)]
for i in range(m):
    a[i], b[i] = [int(i) - 1 for i in input().split()]
    if b[i] == n-1:
        semiGoal[a[i]] = 1
for i in range(m):
    if a[i] == 0 and semiGoal[b[i]] == 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
c = []
for i in range(m):
    c.append([int(m) for m in input().split()])
c.sort(key=lambda x:(x[0], x[1]))
root = []
for i in range(n):
    root.append([])
for i in range(m):
    root[c[i][0] - 1].append(c[i][1])
root1 = root[0]
for v in root1:
    if n in root[v - 1]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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

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())
l_s,l_l,B_s,B_l = [],[],[],[]
for i in range(M):
    a,b = map(int,input().split())
    if a == 1 :
        if b < N:
            B_s.append(b) 
        elif b > N:
            B_l.append(b) 
    if a == N:
        l_l.append(b) 
    elif b == N:
        l_s.append(a) 
common_1 = len(list(set(l_s) & set(B_s)))
common_2 = len(list(set(l_l) & set(B_l)))
if common_1 > 0 or common_2 > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


N, M = map(int, input().split())
lines = []
for _ in range(M):
    a, b = map(int, input().split())
    lines.append(Line(a, b))
second_islands = []
m = {}
for line in lines:
    m.setdefault(line.a, {})
    m[line.a][line.b] = 1
for line in lines:
    if line.a == 1:
        second_islands.append(line.b)

can_reach = False
for island in second_islands:
    if island in m:
        if N in m[island]:
            can_reach = True
            break
if (can_reach):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

def bin_search(a,li):
    max_len=len(li)-1
    min_len=0
    while max_len>=min_len:
        mid=(max_len+min_len)//2
        if li[mid]==a:
            return True
        elif li[mid]<a:
            min_len=mid+1
        else:
            max_len=mid-1
s=[]
g=[]
for i in l:
    if i[0]==1:
        s.append(i[1])
    if i[1]==n:
        g.append(i[0])
g.sort()
for i in s:
    if bin_search(i,g):
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):

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

ab = []
for ai, bi in ab_tmp:
    if ai == 1 or bi == N: ab.append([ai, bi])

ab.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1] if x[0] == 1 else x[0]) 

view = 0
for ai, bi in ab:
    if ai < 2: 
        view = bi
        continue
    elif ai > view: continue 
    elif bi == N: 
        print("POSSIBLE")
        break
    else: continue 
else:
    print("IMPOSSIBLE")

Solution (Python):
a,b = map(int,input().split(" "))
ar = [[] for j in range(a+1)]
for i in range(b):
    l = list(map(int,input().split(" ")))
    ar[l[0]].append(l[1])
    ar[l[1]].append(l[0])
count = 0
for r in ar[1]:
    for s in ar[r]:
        if s == a:
            count += 1
if count == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

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

s = [0 for _ in range(n)]
t = [0 for _ in range(n)]

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

    if a == 1:
        s[b-1] = 1
    if b == n:
        t[a-1] = 1

for i in range(n):
    if s[i] * t[i] == 1:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

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

L = [tuple(map(int,input().split())) for i in range(M)]
flag = 0

P = []
for i in range(2) :
    for j in range(M) :
        if (L[j][i] == 1) or (L[j][i] == N) :
            if i == 0 :
                P.append(L[j][1])
            else :
                P.append(L[j][0])

Q = list(set(P))
if len(P) != len(Q) :
    flag = 1

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

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

t = [0] * N

for i in range(M):
    tmp = list(map(int, input().rstrip().split()))
    if tmp[0] == 1:
        t[tmp[1] - 1] |= 1
    
    if tmp[1] == N:
        t[tmp[0] - 1] |= 2


result = 'POSSIBLE' if 3 in t else 'IMPOSSIBLE'
print(result)

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

st = []
dic = {}

for i in range(M):
    s, t = list(map(int, input().rstrip().split()))
    if s == 1:
        st.append(t)
    
    if t == N:
        dic[s] = 0

result = 'IMPOSSIBLE'
for s in st:
    if s in dic:
        result = 'POSSIBLE'
        break


print(result)

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

ab = []
bn = {}
for i in range(m):
    tmp = list(map(int, input().split()))
    if tmp[0] == 1:
        ab.append(tmp[1])
    elif tmp[1] == n:
        bn[tmp[0]] = 1
for i in ab:
    if i == n:
        print('POSSIBLE')
        sys.exit(0)
    elif i in bn:
        print('POSSIBLE')
        sys.exit(0)

print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, raw_input().split())
c = [0]*(N+1)
for i in range(1,M+1):
  a, b = map(int, raw_input().split())
  if a in [1, N]:
    c[b] += 1
  if b in [1, N]:
    c[a] += 1
r = 'IMPOSSIBLE'
for j in range(1,N+1):
  if c[j]==2:
    r = 'POSSIBLE'
print r

Solution (Python):
N, M = map(int, input().split())
a, b, d = [0]*M, [0]*M, [0]*M
hoge, piyo = set(), set()
for i in range(M):
    ai, bi = map(int, input().split())
    if ai == 1 and bi == N:
        print('POSSIBLE')
        exit()
    elif ai == 1:
        hoge.add(bi)
    elif bi == N:
        piyo.add(ai)
if len(hoge.intersection(piyo)) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
import sys
input = sys.stdin.readline
def 解():
    iN,iM = [int(_) for _ in input().split()]
    a1 = [0]*iN
    aN = [0]*iN
    for i in range(iM):
        a,b = [int(_) for _ in input().split()]
        if a == 1:
            a1[b] = 1
        if b == iN:
            aN[a] = 1
    for i in range(iN):
        if a1[i] and aN[i]:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")
解()

Solution (Python):
import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    a1 = [0]*iN
    aN = [0]*iN
    aAB = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    for a,b in aAB:
        if a == 1:
            a1[b] = 1
        if b == iN:
            aN[a] = 1
    for i in range(iN):
        if a1[i] and aN[i]:
            print("POSSIBLE")
            exit()
    print("IMPOSSIBLE")
解()

Solution (Python):
import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    aAB = [[int(_) for _ in sLine.split() ] for sLine in sys.stdin.readlines()]
    d1 = set()
    dN = set()
    for a,b in aAB:
        if a == 1 :
            d1.add(b)
        if b == iN:
            dN.add(a)
    if d1 & dN == set():
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")
解()

Solution (Python):
import sys
def 解():
    iN,iM = [int(_) for _ in input().split()]
    aAB = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
    dT = {}
    def addTree(dT,a,b):
        if a in dT:
            dT[a].add(b)
        else:
            dT[a] = {b}
    for a,b in aAB:
        addTree(dT,a,b)
        addTree(dT,b,a)
    if  1 not in dT or iN  not in dT:
        print("IMPOSSIBLE")
    elif 0 < len(dT[1] & dT[iN]) :
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
解()

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

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

t_a = []
t_b = []

ans = 'IMPOSSIBLE'
for i in range(M):
	if l[i][0] == 1:
		t_a.append(l[i][1])
	elif l[i][1] == N:
		t_b.append(l[i][0])
t_and = set(t_a) & set(t_b)
t_and_l = list(t_and)
if len(t_and_l) > 0:
	ans = 'POSSIBLE'
print(ans)

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

F = [0 for _ in range(N)]   
T = [0 for _ in range(N)]   

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1:
        F[b-1] = 1
    if b == N:
        T[a-1] = 1

for i in range(1, N):
    if F[i] == T[i] == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
l=[[0] for _ in range(n+1)]
for _ in range(m):
  j,k=map(int,input().split())
  l[j].append(k)
for i in l[1][1:]:
  if n in l[i]:break
  if i==l[1][-1]:print('IM',end='')
print('POSSIBLE')

Solution (Python):

N, M = map(int, input().split())
graph0 = [0 for _ in range(N)]
graphN = [0 for _ in range(N)]

for _ in range(M):
    ab = list(map(int, input().split()))
    a,b = ab[0],ab[1]
    if a == 1:
        graph0[b-1] = 1
    if b == N:
        graphN[a-1] = 1

for i in range(1,N):
    if graph0[i] == 1 and graphN[i] == 1:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

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

if len(s & t) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import bisect

n, m = map(int, input().split())
f_1 = []
t_n = []
jedge = 0
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        f_1.append(b)
    if b == n:
        t_n.append(a)
f_1.sort()
t_n.sort()
for i in range(len(f_1)):
    p = bisect.bisect_left(t_n, f_1[i])
    if p < len(t_n)-1 and f_1[i] == t_n[p]:
        jedge = 1
        break
    elif p == len(t_n)-1 and f_1[i] == t_n[p]:
        jedge = 1
        break
if jedge == 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
SetFrom, SetTo = set(), set()
for i in range(M):
    a, b = map(int, input().split())
    a, b = min(a, b), max(a, b)
    if a == 1:
        SetFrom |= {b}
    elif b == N:
        SetTo |= {a}
print("POSSIBLE" if SetFrom & SetTo else "IMPOSSIBLE")

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

print("POSSIBLE" if set(S[0]) & set(S[N-1]) else "IMPOSSIBLE")

Solution (Python):
import bisect

N, M = map(int,input().split())
AB = []
for m in range(M):
    a,b = map(int,input().split())
    AB.append((a,b))

AB = sorted(AB)

first = []
for a,b in AB:
    if a == 1:
        first.append(b)
    else:
        break

AB = sorted(AB, key=lambda x:x[1], reverse=True)
sec = []
for a,b in AB:
    if b == N:
        sec.append(a)
    else:
        break

if len(sec) >= 100:
    for f in first:
        ind = bisect.bisect_left(sec, f, 0, len(sec))
        if sec[ind] == f:
            print('POSSIBLE')
            exit()
else:
    for f in first:
        if f in sec:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

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

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

Solution (Python):
N, M = map(int, input().split())
starts = set([])
ends = set([])

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b  == 1:
        starts.add(a if b == 1 else b)
    if a == N or b == N:
        ends.add(a if b == N else b)

ans = "POSSIBLE" if len(starts&ends)>=1 else "IMPOSSIBLE"
print(ans)

Solution (Python):
p=[]
q=[]
n,m = map(int,input().split())
for _ in [0]*m:
  a,b = map(int,input().split())
  if a == 1:
    p += [b]
  elif b == n:
    q += [a]
p.sort()
q.sort()
i,j = 0,0
while i<len(p) and j<len(q):
    if p[i]<q[j]:
      i += 1
    elif p[i]>q[j]:
      j += 1
    else:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

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

s = []

for i in range(m):
	s.append(list(map(int,input().split())))

a1 = []
an = []
for i in range(m):
	if s[i][0]==1:
		a1.append(s[i][1])

for i in range(m):
	if s[i][1]==n:
		an.append(s[i][0])

if len(list(set(a1)&set(an)))>0:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

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

if len(s & t) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m = map(int, input().split())
list_ab = []
for i in range(m):
    list_ab.append(list(map(int, input().split())))
list1 = []
listn = []
for i in range(m):
    if list_ab[i][0] == 1:
        list1.append(list_ab[i][1])
for i in range(m):
    if list_ab[i][1] == n:
        listn.append(list_ab[i][0])

listn.sort()
def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return "NOT_FOUND"
ans = "IMPOSSIBLE"
for i in range(len(list1)):
    if binarySearch(listn, list1[i]) != "NOT_FOUND":
        ans = "POSSIBLE"
        break

print(ans)

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

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

def bfs(s):
    d = 0
    flag[s] = 1
    q = deque([(s, d)])

    while len(q) > 0:
        v = q.popleft()
        for i in g[v[0]]:
            if flag[i]:
                continue
            flag[i] = 1
            if v[1] < 1:
                q.append((i, d+1))
            if v[1] == 1 and i == n-1:
                return True
    return False

print("POSSIBLE" if bfs(0) else "IMPOSSIBLE")

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

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()

from1 = set()
toN = set()

for _ in range(m):
    a,b = li()
    if a==1:
        from1.add(b)
    elif b==1:
        from1.add(a)
        
    elif a==n:
        toN.add(b)
    elif b==n:
        toN.add(a)

if from1 & toN:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
s1 = set()
sn = set()
for a,b in src:
    if a == 1:
        s1.add(b)
    elif a == N:
        sn.add(b)
    if b == 1:
        s1.add(a)
    elif b == N:
        sn.add(a)
ok = len(s1 & sn) > 0
print('POSSIBLE' if ok else 'IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
mid, las = [], []
ans = 0

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        mid.append(b)
    
    elif b == N:
        las.append(a)

if len(set(mid) & set(las)) != 0:
    ans =1

print('POSSIBLE' if ans == 1 else 'IMPOSSIBLE')

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

s = 1
stack = []
ans = 'IMPOSSIBLE'
if adj[s]:
    stack.extend(adj[s])
    for nextild in stack:
        if n in adj[nextild]:
            ans = 'POSSIBLE'
            break
print(ans)

Solution (Python):
import sys
from collections import defaultdict
from heapq import heappop, heappush

input = sys.stdin.readline

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


class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    def __init__(self, graph, start):
        g = graph.graph

        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0
        self.prev = defaultdict(lambda: None)

        Q = []
        heappush(Q, (self.dist[start], start))

        while Q:
            dist_u, u = heappop(Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(Q, (alt, v))

    def shortest_distance(self, goal):
        return self.dist[goal]

    def shortest_path(self, goal):
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
for i in range(M):
    a, b = map(int, input().split())
    g.add_edge(a - 1, b - 1)
    g.add_edge(b - 1, a - 1)
d = Dijkstra(g, 0)
if d.shortest_distance(N - 1) == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
fn = lambda: map(int, input().split())
N, M = fn()
a, b = [0]*M, [0]*M
ones, goals = set(), set()
for i in range(M):
    ai, bi = fn()
    if ai == 1 and bi == N:
        print('POSSIBLE')
        exit()
    elif ai == 1:
        ones.add(bi)
    elif bi == N:
        goals.add(ai)

if len(ones.intersection(goals)) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):
N, M = map(int, input().split())
V = [[0, 0] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    V[b - 1][0] = 1
  if b == 1:
    V[a - 1][0] = 1
  if a == N:
    V[b - 1][1] = 1
  if b == N:
    V[a - 1][1] = 1
for v in V:
  if v[0] and v[1]:
    print('POSSIBLE')
    break
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("IM", end="")
print("POSSIBLE")

Solution (Python):
N, M = map(int, input().split())
ab = []
ans = -1
for i in range(M):
    a, b = map(int, input().split())
    ab.append([min(a, b), max(a, b)])
root_1i = [0 for i in range(N)]
root_iN = [0 for i in range(N)]
ab.sort()
for i in ab:
    if i[0] == 1:
        root_1i[i[1] - 1] = 1          
    elif i[1] == N and root_1i[i[0] - 1] == 1:
        print("POSSIBLE")
        ans = 1
        break

if ans == -1:
    print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def main():
    N, M = map(int, input().split())

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

    for a in s:
        if a in t:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")


if __name__ == '__main__':
    main()

Solution (Python):

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

island_score=[0]*N

for i in range(M):
    if ab[i][0]==1:
        island_score[ab[i][1]]+=1

for i in range(M):
    if ab[i][1]==N:
        
        if island_score[ab[i][0]]==1:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

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

for i in range(M):
    ab = list(map(int, input().split()))
    line.append(ab)

start = 1
end = N
first = set()
second = set()

for l in line:
    if end in l:
        second.add(l[0])
        second.add(l[1])
    elif start in l:
        first.add(l[1])
        first.add(l[0])


for f in first:
    if f in second:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

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

    islands_to_1 = [0 for _ in range(n+1)]
    islands_to_n = []
    for _ in range(m):
        boat = list(map(int, input().split()))
        if 1 in boat:
            islands_to_1[boat[1]] = 1

        if n in boat:
            islands_to_n.append(min(boat))

    for island_to_n in islands_to_n:
        if islands_to_1[island_to_n] == 1:
            print("POSSIBLE")
            return

    print("IMPOSSIBLE")
    return


if __name__ == "__main__":
    main()

Solution (Python):
N, M=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(M)]
b=set()
for i,j in ab:
    if i==1 or j==N:
        b.add((i,j))
print("IM"*(not(any(((1,i) in b and (i,N) in b) for i in range(N))))+"POSSIBLE")

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

forw = set()
backw = set()

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

if len(forw&backw) > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

forw = set()
backw = set()

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

if len(forw&backw) > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

connect_1 = {}
connect_n = {}
for i in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        connect_1[b] = 1
    if b == n:
        connect_n[a] = 1


ans = 'IMPOSSIBLE'
for k in connect_1.keys():
    if k in connect_n.keys():
        ans = 'POSSIBLE'
print(ans)

Solution (Python):
import sys
import math
import collections
import itertools
import array
import inspect


sys.setrecursionlimit(1000000)



def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))



def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v



def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk



def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return




dp = None


def main():
    N, M = li_input()
    L = []

    for i in range(M):
        a, b = li_input()

        if a == 1:
            L.append(b)

        if b == N:
            L.append(a)

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


main()

Solution (Python):
n, m = [int(v) for v in input().split()]
from_one = []
to_n = {}
for i in range(m):
    a, b = [int(v) for v in input().split()]
    if a == 1:
        from_one.append(b)
    elif b == n:
        to_n[a] = True

ans = 'IMPOSSIBLE'
for v in from_one:
    if v in to_n:
        ans = 'POSSIBLE'

print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
X = [0] * N
Y = [0] * N
for i in range(M):
    S, E = list(map(int, input().split()))
    if S == 1:
        X[E-1] = 1
    if E == N:
        Y[S-1] = 1
for i in range(N):
    if X[i] == 1 and Y[i] == 1:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map( int, input().split())
fromN = set([])
from1 = set([])
ans = 'IMPOSSIBLE'
for _ in range(M):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    if a == 0:
        if b == N-1:
            ans = 'POSSIBLE'
            break
        else:
            from1.add(b)
    elif b == N-1:
        fromN.add(a)
if len( fromN & from1) != 0:
    ans = 'POSSIBLE'
print(ans)

Solution (Python):
n,m,*T=map(int,open(0).read().split())
*S,=zip(T[::2],T[1::2])
f=lambda e:set(s[e<2]for s in S if e in s)
print('IM'*(f(1)&f(n)==set())+'POSSIBLE')

Solution (Python):
N,M=map(int,input().split())
x=y=1
for _ in[0]*M:
    a,b=map(int,input().split())
    if a==1: x|=1<<b
    if b==N: y|=1<<a
print('IM'*(x&y==1)+'POSSIBLE')

Solution (Python):
N,M=map(int,input().split())
dp=[[0,0]for _ in[0]*N]
for _ in[0]*M:
    a,b=map(int,input().split())
    if a==1:
        dp[b][0]+=1
    elif b==N:
        dp[a][1]+=1
for i in range(N):
    if sum(dp[i])==2:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
import itertools

n,m = map(int,input().split())
ship = []
for _ in range(m):
    a,b = map(int,input().split())
    if a==1:
        ship.append(b)
    if b==n:
        ship.append(a)
ship = sorted(ship)
g = itertools.groupby(ship)
for k,v in g:
    if len(list(v))==2:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
s1 = raw_input().split(' ')
n, m = int(s1[0]), int(s1[1])
i2il = {}
for _ in range(m):
    s = raw_input().split(' ')
    if s[0] in i2il:
        i2il[s[0]].append(s[1])
    else:
        i2il[s[0]] = [s[1]]
    if s[1] in i2il:
        i2il[s[1]].append(s[0])
    else:
        i2il[s[1]] = [s[0]]
if '1' not in i2il or s1[0] not in i2il:
    print 'IMPOSSIBLE'
else:
    mid = i2il['1']
    bhit = False
    for m in mid:
        if s1[0] in i2il[m]:
            print 'POSSIBLE'
            bhit = True
            break
    if not bhit:
        print 'IMPOSSIBLE'

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

N,M = map(int, sdin().split())
AB = []
for i in range(M):
    AB.append(tuple(map(int, sdin().split())))
    
to_mid = set()
from_mid = set()

for a,b in AB:
    if a==1:
        to_mid.add(b)
    if b==N:
        from_mid.add(a)
        
if to_mid & from_mid:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import deque

def bfs(graph:list, node:int, start:int) -> list:
    
    INF = float("inf")
    dist = [INF]*node
    
    
    dist[start] = 0
    que = deque([(0,start)])
    
    
    while que:
        cost, cur_node = que.popleft()
        
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                que.append((dist[nex_node], nex_node))
                
    return dist

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



adj_list = [[] for _ in range(N)]
for a,b in AB:
    a -= 1
    b -= 1
    adj_list[a].append((1,b))
    adj_list[b].append((1,a))
    
dist = bfs(adj_list, N, 0)

if dist[N-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import itertools

n, m = [int(_) for _ in input().split()]
a = []
b = []
for i in range(0, m):
    ai, bi = [int(_) for _ in input().split()]
    a.append(ai)
    b.append(bi)

first = [b[i] for i in range(0, m) if a[i] == 1]
second = [a[i] for i in range(0, m) if b[i] == n]

if set(first) & set(second):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

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

N,M = inpl()
dd = defaultdict(int)

for i in range(M):
	a,b = inpl()
	if a == 1:
		if dd[b] == 1:
			print('POSSIBLE')
			sys.exit()
		else:
			dd[b] = 1

	if b == N:
		if dd[a] == 1:
			print('POSSIBLE')
			sys.exit()
		else:
			dd[a] = 1

print('IMPOSSIBLE')