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())
A=[0]*M;p=-1

for i in range(M):
    a,b=map(int,input().split())
    A[i]=[a,b]
A.sort(reverse=True, key=lambda x: x[1])



if A[0][1]!=N:
    print("IMPOSSIBLE")
else:
    d = [False] * (N + 5)
    for i in range(M):
        if A[i][1] == N:
            d[A[i][0]] = True
        if A[i][0] == 1 and d[A[i][1]]:
            p = 2
            
    if p == 2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

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

a_list = []
tmp_start = []
tmp_goal = []
for i in range(m):
    a, b = map(int, input().split())
    
    
    if a == 1:
        tmp_start.append(b)
    
    if b == n:
        tmp_goal.append(a)
    

    
    
    

agree = set(tmp_start) & set(tmp_goal)

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

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

middles1 = []
middles2 = []
ans = "IMPOSSIBLE"

for i in l:
    if i[0] == 1 and i[1] == N:
        ans = "POSSIBLE"
    elif i[0] == 1:
        middles1.append(i[1])
    elif i[1] == N:
        middles2.append(i[0])

if len(set(middles1) & set(middles2)) > 0:
    ans = "POSSIBLE"

print(ans)

Solution (Python):
import sys
from collections import deque


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

path = [float('inf')] * N
q = deque()
q.append((0, 0))
path[0] = 0
while q:
    p, step = q.popleft()
    for np in edge[p]:
        nstep = step + 1
        if path[np] > nstep and nstep <= 2:
            q.append((np, nstep))
            path[np] = nstep

ans = 'POSSIBLE' if path[N - 1] == 2 else 'IMPOSSIBLE'
print(ans)

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

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

transit = []
transit_ = []

for a,b in (map(int, input().split()) for _ in range(m)):
    if a == 1:
        transit.append(b)
    if b == n:
        transit_.append(a)

if set(transit)&set(transit_):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

transit = []
transit_ = []

for a,b in (map(int, input().split()) for _ in range(m)):
    if a == 1:
        transit.append(b)
    if b == n:
        transit_.append(a)

if set(transit)&set(transit_):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
from collections import deque



def bfs(g, i):
    
    
    dis = [float('Inf')] * N 
    
    
    d = [False] * N
    
    que = deque()
    que.append(i)
    d[i] = True
    dis[i] = 0
    
    while que:
        p = que.popleft()
        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[k] = dis[p] + 1

    return dis
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
g = [[] for _ in range(N)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
dis = bfs(g, 0)

if dis[-1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):

n,m=map(int,input().split())
a1=set()
an=set()
for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        a1.add(bi)
    elif bi==n:
        an.add(ai)

if len(a1&an)==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

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

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

go = []
goal = []

for i in range(len(a)):
    if a[i] == 1:
        go.append(b[i])
    if b[i] == n:
        goal.append(a[i])

count = [0 for i in range(n)]
for i in range(len(go)):
    count[go[i]-1] = 1
for i in range(len(goal)):
    count[goal[i]-1] += 1
for i in range(len(count)):
    if count[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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


from_1=set([el[1] for el in ab if el[0]==1])
from_N=set([el[0] for el in ab if el[1]==N])

if from_1 & from_N:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):




def main():
    N, M = map(int, input().split())
    
    from_1 = [False] * N
    to_N = [False] * N
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            from_1[b - 1] = True
        elif b == N:
            to_N[a - 1] = True
    for i in range(1, N):
        if from_1[i] and to_N[i]:
            print('POSSIBLE')
            break
    else:
        print('IMPOSSIBLE')


if __name__ == "__main__":
    main()

Solution (Python):



def resolve():
    from heapq import heappush, heappop

    
    
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  
        dist[r] = 0  

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    V, E = map(int, input().split())
    r = 0
    g = [[] for i in range(V)]

    for i in range(E):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        d = 1
        g[s].append((d, t))
        g[t].append((d, s))  

    INF = 10 ** 10

    if dijkstra(V, g, r)[-1]==2:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


resolve()

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

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

go = []
goal = []

for i in range(len(a)):
    if a[i] == 1:
        go.append(b[i])
    if b[i] == n:
        goal.append(a[i])

count = [0 for i in range(n)]
for i in range(len(go)):
    count[go[i]-1] = 1
for i in range(len(goal)):
    count[goal[i]-1] += 1
for i in range(len(count)):
    if count[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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

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

Solution (Python):
def main ():
    n,m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    g = [[] for _ in range(n+1)]
    for a,b in ab:
        g[a].append(b)
        g[b].append(a)
    if set(g[1]) & set(g[n]) != set([]):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

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

Solution (Python):
def ABC068C():
    N, M = map(int, input().split())
    flag = [[False, False] for _ in range(N)]

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

    for i in range(N):
        if flag[i][0] and flag[i][1]:
            print('POSSIBLE')
            return

    print('IMPOSSIBLE')
    return

ABC068C()

Solution (Python):
n,m=map(int,input().split())
from collections import Counter
cc=Counter()
for _ in range(m):
    a,b=map(lambda x:int(x)-1, input().split())
    cc[(a,b)]=1
    cc[(b,a)]=1
for i in range(1,n-1):
    if cc[(0,i)] and cc[(i,n-1)]:
        print('POSSIBLE')
        import sys
        sys.exit()
print('IMPOSSIBLE')

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

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

for i in range(m):
    j,k=map(int,input().split())
    A[j-1].append(k-1)
    A[k-1].append(j-1)
for i in range(len(A[0])):
    if n-1 in A[A[0][i]]:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

Solution (Python):
n,m=map(int,input().split())
l1=[]
ln=[]

for i in range(m):
    ai,bi=map(int,input().split())
    if ai==1:
        l1.append(bi)
    if bi==n:
        ln.append(ai)
    

if len(set(l1) & set(ln))==0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

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

ship1 = [False]*n
shipn = [False]*n
ans = "IMPOSSIBLE"
for i in range(m):
  a, b = map(int, input().split())
  if a == 0 and b == n-1:
    ans = "POSSIBLE"
  elif a == 1:
    ship1[b-1] = True
  elif b == n:
    shipn[a-1] = True
  else:
    pass

for i in range(n):
  if ship1[i] and shipn[i]:
    ans = "POSSIBLE"
print(ans)

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

ab1 = []
ab2 = []

for i in ab:
    if i[0] == 1:
        ab1.append(i[1])
    elif i[1] == n:
        ab2.append(i[0])

jud = ab1 + ab2
if len(jud) == len(set(jud)):
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
l=[0]*n
for i in range(m):
  a,b=f()
  if a==1: l[b]+=1
  if b==n: l[a]+=1
print('IM'*(max(l)<2)+'POSSIBLE')

Solution (Python):
import numpy as np

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

possible1 = []
possibleN = []

for i in range(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        possible1.append(b)

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

product = set(possible1) & set(possibleN)

if len(product) != 0:
    print "POSSIBLE"
else:
    print "IMPOSSIBLE"

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

Solution (Python):
N, M = map(int, input().split())
from collections import defaultdict
edges = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)


first = edges[1]

for e in first:
    
    second = edges[e]
    if N in second:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
N,M = map(int, input().split())
from collections import defaultdict
edges = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

first = edges[1]

for fr in first:
    if N in edges[fr]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):

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

s_L = []

for i in range(m):
    L = list(map(int,input().split()))
    a = min(L)
    b = max(L)

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


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

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

step = [-1] * (N+1)
step[1] = 0
for i in range(2, N+1):
  if len(path[i]) == 0: continue
  for p in path[i]:
    if step[p] == -1: continue
    if step[i] == -1:
      step[i] = step[p] + 1
    else:
      step[i] = min(step[i], step[p] + 1)

if step[N] == 2:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
g=[[] for i in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u-1].append(v-1)
  g[v-1].append(u-1)
for x in g[0]:
  for y in g[x]:
    if y==n-1:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

Solution (Python):
import numpy as np

n, m = map(int, input().split())
from_1 = np.zeros(n+1, dtype=np.int)
to_n = np.zeros(n+1, dtype=np.int)
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        from_1[b] = 1
    elif b == n:
        to_n[a] = 1

print('IMPOSSIBLE') if np.sum(from_1*to_n) == 0 else print('POSSIBLE')

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


def solve():
    N, M = map(int, rl().split())
    graph = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].add(b)
        graph[b].add(a)
    
    for child in graph[0]:
        if N - 1 in graph[child]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    solve()

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


def solve():
    N, M = map(int, rl().split())
    graph = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].add(b)
        graph[b].add(a)
    
    for child in graph[0]:
        if N - 1 in graph[child]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    solve()

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


def solve():
    N, M = map(int, rl().split())
    graph = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].add(b)
        graph[b].add(a)
    
    for child in graph[0]:
        if N - 1 in graph[child]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    solve()

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


def solve():
    N, M = map(int, rl().split())
    graph = [set() for _ in range(N)]
    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].add(b)
        graph[b].add(a)
    
    for child in graph[0]:
        if N - 1 in graph[child]:
            print('POSSIBLE')
            exit()
    print('IMPOSSIBLE')


if __name__ == '__main__':
    solve()

Solution (Python):
n, m = map(int, input().split())
start, end = [], []
for _ in range(m):
    t1, t2 = map(int, input().split())
    if t1==1:
        start.append(t2)
    if t2==n:
        end.append(t1)

start, end = set(start), set(end)
if len(start)+len(end)==len(start | end):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')

Solution (Python):

import math
import heapq
import bisect
import numpy as np
from collections import Counter


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

A = []
B = []

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

B.sort()
for a in A:
    if bisect.bisect_left(B, a) < len(B) and B[bisect.bisect_left(B, a)]==a:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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

f, s = [],[]

for i in range(m):
    if l[i][0] == 1:
        f += [l[i][1]]
    if l[i][1] == n:
        s += [l[i][0]]

print('POSSIBLE') if set(f) & set(s) else print('IMPOSSIBLE')

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

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

ans = 'IMPOSSIBLE'
for x in root[n]:
  if 1 in root[x]:
    ans = 'POSSIBLE'
    break

print(ans)

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

boat_dict = {}

for boat in range(M):
    a, b = [int(i) for i in input().split()]
    boat_dict.setdefault(a, [])
    boat_dict[a].append(b)
        
flag = False

for i in boat_dict[1]:
    if i in boat_dict.keys():
        if N in boat_dict[i]:
            flag = True
            break

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

Solution (Python):
N, M, *A = map(int, open(0).read().split())
A = [(A[i], A[i+1]) for i in range(0, M*2, 2)]
E = [[] for _ in range(N)]
for a, b in A:
    a -= 1; b -= 1
    E[a].append(b)
    E[b].append(a)

def search(d=2, v=0, g=N-1):
    if d == 0:
        if v == g:
            return True
        else:
            return False

    for to in E[v]:
        if search(d-1, to, g):
            return True
    return False

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

Solution (Python):
N,M=map(int,input().split())
to=[]
fr=[]
for _ in range(M):
  A,B=map(int,input().split())
  if A==1:
    to.append(B)
  if B==N:
    fr.append(A)
print('POSSIBLE' if len(set(to) & set(fr)) else 'IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
start = []
goal = []
flag = False
for x in range(M):
    if ab[x][0] == 1:
        start.append(ab[x][1])

    if ab[x][1] == N:
        goal.append(ab[x][0])

start_goal = set(start) & set(goal)

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

Solution (Python):
n,m = [int(x) for x in input().split()]
ab = []
for _ in range(m):
    tmp = [int(x) for x in input().split()]
    ab.append(tmp)

start = [x[1] for x in ab if x[0] == 1]
goal = [x[0] for x in ab if x[1] == n]

ans = "IMPOSSIBLE"

if len(set(start) & set(goal)) > 0:
    ans = "POSSIBLE"

print(ans)

Solution (Python):
n, m = map(int, input().split())
l = set()
r = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l.add(b)
    if b == n:
        r.add(a)
for x in l:
    if x in r:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

Solution (Python):
n, m = map(int, input().split())
first = [False for _ in range(n + 1)]
second = [False for _ in range(n + 1)]

for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        first[b] = True
    if b == n:
        second[a] = True

for i, j in zip(first, second):
    if i and j:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    d[a].append(b)

for j in d[1]:
    if N in d[j]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):
from collections import defaultdict
N, M = map(int, input().split())
d = defaultdict(list)
for i in range(M):
    a,b = map(int, input().split())
    d[a].append(b)

for i,j in list(d.items()):
    if i!=1:
        continue
    for k in j:
        if N in d[k]:
            print('POSSIBLE')
            exit()
print('IMPOSSIBLE')

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n,m=mii()
arr=[[] for i in range(n)]
for i in range(m):
    x,y=mii()
    arr[x-1].append(y-1)
chk=False

for i in arr[0]:
    if n-1 in arr[i]:
        print("POSSIBLE")

        exit()
print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict

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

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

Solution (Python):
from collections import defaultdict

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

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

Solution (Python):
import numpy as np
N, M = input().split()
N = int(N)
M = int(M)


boat = 2
ab = np.zeros(M)
ab1 = []
abN = []
ok = "IMPOSSIBLE"
for i in range(M):
    a,b = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        ab1.append(b)
    elif b == N:
        abN.append(a)
if len(set(abN) & set(ab1))>=1:
    ok = "POSSIBLE"
print(ok)

Solution (Python):
N,M=map(int,input().split())
scan=[]
gcan=[]
flag=0
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        scan.append(b)
    if b==N:
        gcan.append(a)
if set(scan)&set(gcan):
    flag=1
if flag==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys

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

for key in canMove[1]:
  if N in canMove[key]:
    print('POSSIBLE')
    sys.exit()

print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
ship=[list(map(int,input().split())) for _ in range(M)]
port1=[]
port2=[]
for i in range(M):
    if ship[i][0]==1:
        port1.append(ship[i][1])
    if ship[i][1]==N:
        port2.append(ship[i][0])

port1=set(port1)
port2=set(port2)
if len(port1&port2)>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N,M=map(int,input().split())
ship=[list(map(int,input().split())) for _ in range(M)]
port1=[]
port2=[]
for i in range(M):
    if ship[i][0]==1:
        port1.append(ship[i][1])
    if ship[i][1]==N:
        port2.append(ship[i][0])

port1=set(port1)
port2=set(port2)
if len(port1&port2)>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

print("IMPOSSIBLE")

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
path = [LIST() for _ in range(M)]

graph = [[] for _ in range(N)]

for a, b in path:
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)

for i in range(len(graph[0])):
	a = sorted(graph[graph[0][i]])
	if a[len(a) - 1] == N - 1:
		print("POSSIBLE")
		exit()

print("IMPOSSIBLE")

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]


class UnionFind():
    def __init__(self, n):
        self.n = n
        
        
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

graph = defaultdict(list)

for a, b in L:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)


    
s = set(graph[0]) & set(graph[N-1])



if not s:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):


import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

N, M = na()
ab = nan(M)

G = [[] for _ in range(N)]
for i in range(M):
    a, b = ab[i]
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

def dfs(i, j, p):
    if j > 2:
        return False
    if i == N - 1 and j == 2:
        return True
    flag = False
    for k in range(len(G[i])):
        if G[i][k] == p:
            continue
        if dfs(G[i][k], j + 1, i):
            flag = True
    return flag

print("POSSIBLE" if dfs(0, 0, -1) else "IMPOSSIBLE")

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
graph = defaultdict(list)

for _ in range(M):
	a, b = MAP()
	graph[a-1].append(b-1)
	graph[b-1].append(a-1)


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

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

Solution (Python):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i 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):
N, M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]

c = {ab[i][1] for i in range(M) if ab[i][0] == 1}
d = {ab[i][0] for i in range(M) if ab[i][1] == N}

if c & d :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

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

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

if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

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

if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
import collections
n, m = map(int, input().split())
c = 0
B = []
C = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        B.append(b)
    elif b == n:
        B.append(a)
C = collections.Counter(B)
for i in C:
    if C[i] > 1:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(m)])
relaypoint = []
for i in range(m):
  if ab[i][0] == 1:
    relaypoint.append(ab[i][1])
  else:
    break
ab.sort(key = lambda ab:ab[1],reverse = True)
relaypoint = set(relaypoint)
x = len(relaypoint)
j = 0
flag = 0
while(ab[j][1] == n):
  if ab[j][0] in relaypoint:
    flag = 1
  j += 1
if flag == 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")