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())
x=[0]*n
s=0
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        if x[b-1]==0:
            x[b-1]=1
        elif x[b-1]==-1:
            s+=1
    elif b==n:
        if x[a-1]==0:
            x[a-1]=-1
        elif x[a-1]==1:
            s+=1
if s>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N,M = map(int,input().split())
I = set()
n = set()
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        I.add(b)
    if b == N:
        n.add(a)
if  I & n == set():
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
N,M = map(int,input().split())
I = set()
n = set()
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        I.add(b)
    if b == 1:
        I.add(a)
    if a == N:
        n.add(b)
    if b == N:
        n.add(a)
if  I & n == set():
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
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)
  g[b-1].append(a)
ls = g[0]
flag = 0
for i in range(len(g[0])):
  ls2 = g[ls[i]-1]
  for j in range(len(ls2)):
    if ls2[j] == N:
      flag += 1
      print("POSSIBLE")
      break
if flag == 0:
  print("IMPOSSIBLE")

Solution (Python):
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)
  g[b-1].append(a)
ls = g[0]
flag = 0
for i in range(len(g[0])):
  ls2 = g[ls[i]-1]
  for j in range(len(ls2)):
    if ls2[j] == N:
      flag += 1
      print("POSSIBLE")
      break
if flag == 0:
  print("IMPOSSIBLE")

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

cnt = 0
for i in x[0]:
    if n in x[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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

Solution (Python):
N,M = map(int,input().split())
ab_s = [list(map(int,input().split())) for _ in range(M)]
ONES = set()
NS = set()
for ab in ab_s:
    a = ab[0]
    b = ab[1]
    if a==1 or b==1:
        if a in NS or b in NS:
            print('POSSIBLE')
            break
        ONES.add(a)
        ONES.add(b)
    if a==N or b==N:
        if a in ONES or b in ONES:
            print('POSSIBLE')
            break
        NS.add(a)
        NS.add(b)
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M=map(int, input().split())
from collections import defaultdict
G=defaultdict(lambda: [])
for _ in range(M):
    a,b=map(int, input().split())
    G[a].append(b)
    G[b].append(a)
for nx in G[1]:
    if N in G[nx]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):

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



dic = {}
for i in range(m):
    a, b = map(int, input().split())
    dic[(a, b)] = True
    dic[(b, a)] = True
ans = 'IMPOSSIBLE'
for i in range(2, n):
    if dic.get((1, i), False):
        if dic.get((i, n), False):
            ans = 'POSSIBLE'
            break
print(ans)

Solution (Python):
from sys import stdin
def input():
    return stdin.readline().strip()

n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    i, j = map(int, input().split())
    i -= 1
    j -= 1
    edge[i].append(j)
    edge[j].append(i)

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

Solution (Python):
import collections

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

Solution (Python):
N,M = map(int,input().split())
ans = ('IMPOSSIBLE')
f1tob = []
fbtoN = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        f1tob.append(b)
    elif b == N:
        fbtoN.append(a)
f1toba = set(f1tob)
fbtoNa = set(fbtoN)
if bool(fbtoNa & f1toba):
    ans = 'POSSIBLE'
print(ans)

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)
    ans = False

    for i in route[n]:
        if 1 in route[i]:
            ans = True
    print("POSSIBLE" if ans else "IMPOSSIBLE")
        

main()

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

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

G = [[] for j in range(n + 1)]

for a, b in edges:
    G[a].append(b)
    G[b].append(a)

for b in G[1]:
    if n in G[b]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

dic1 = {}
for i in range(M):
    a,b = map(int,input().split())
    a,b = min(a,b),max(a,b)
    if b == N:
        dic[a]=0
    if a==1:
        dic1[b]=0
ans = False
for tmp in dic1:
    if tmp in dic:
        ans = True
        break
print("POSSIBLE" if ans else "IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
start = [0]*200001
goal = [0]*200001

for i in range(m):
  a,b = map(int,input().split())
  if a == 1:
    if goal[b] == 1:
      print("POSSIBLE")
      exit()
    start[b] = 1
    a
  elif b == n:
    if start[a] == 1:
      print("POSSIBLE")
      exit()
    goal[a] = 1
print("IMPOSSIBLE")

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

Solution (Python):
def main():
  N, M = map(int,input().split())
  fromOne = set()
  toM = set()
  for i in range(M):
    a, b = map(int,input().split())
    if a == 1:
      fromOne.add(b)
    elif b == N:
      toM.add(a)
  return 'POSSIBLE' if fromOne & toM else 'IMPOSSIBLE'
print(main())

Solution (Python):
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()

t = [0]*(n+1)

for _ in range(m):
    a, b = inintm()
    if a == 1:
        if t[b] == 1:
            print("POSSIBLE")
            exit()
        t[b] = 1
    elif b == n:
        if t[a] == 1:
            print("POSSIBLE")
            exit()
        t[a] = 1

print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict

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

graph = defaultdict(list)

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

for hop in graph[1]:
    for goal in graph[hop]:
        if goal == n:
            print("POSSIBLE")
            quit()
        else:
            continue

print("IMPOSSIBLE")

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


def main():
    N, M = map(int, input().split())
    from_one = set([])
    to_n = set([])
    for _ in range(M):
        a, b = map(int, input().split())
        if a == 1:
            from_one.add(b)
        elif b == N:
            to_n.add(a)
    if len(from_one & to_n) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

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

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

print(("IMPOSSIBLE","POSSIBLE")[len(set(N_List) & set(O_List)) > 0])

Solution (Python):
from collections import defaultdict

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

connections = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())

    connections[a].append(b)
    connections[b].append(a)

for v in connections[1]:
    if N in connections[v]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):
from collections import deque

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

e = [[] for i in range(n)]
for i in range(m):
    f, t = map(int,input().split())
    f -= 1
    t -= 1
    e[f].append(t)
    e[t].append(f)

INF = 10**9
dist = [INF] * n
dist[0] = 0
d = deque()
d.append([0, 0])

while d:
    f, c = d.pop()
    if c >= 2:
        break
    for t in e[f]:
        if c + 1 < dist[t]:
            dist[t] = c + 1
            d.appendleft([t, c+1])
print('POSSIBLE') if dist[n-1] <= 2 else print('IMPOSSIBLE')

Solution (Python):
from collections import deque

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

e = [[] for i in range(n)]
for i in range(m):
    f, t = map(int,input().split())
    f -= 1
    t -= 1
    e[f].append(t)
    e[t].append(f)

INF = 10**9
dist = [INF] * n
dist[0] = 0
d = deque()
d.append([0, 0])

while d:
    f, c = d.pop()
    if c >= 2:
        break
    for t in e[f]:
        if c + 1 < dist[t]:
            dist[t] = c + 1
            d.appendleft([t, c+1])
print('POSSIBLE') if dist[n-1] <= 2 else print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
arr_ = [tuple(map(int, input().split())) for _ in range(m)]
one = set([b for a, b in arr_ if a == 1])
last = set([a for a, b in arr_ if b == n])
print("POSSIBLE" if len(one & last) >= 1 else "IMPOSSIBLE")

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

one = set([b for a, b in arr_ if a == 1])
last = set([a for a, b in arr_ if b == n])
connect = one & last
if len(connect) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

one = set([b for a, b in arr if a == 1])
last = set([a for a, b in arr if b == n])
connect = one & last
if len(connect) >= 1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

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

def bfs(goal, graph, seen, next_v):
    for x in graph[next_v[0][0]]:
        if x == goal:
            return True
        if x in seen:
            continue
        next_v.append((x,next_v[0][1]+1))
        seen.add(x)
    return False


next_v = [(0,0)]
seen = {0}

while True:
    if len(next_v) == 0 or next_v[0][1] == 2:
        ans = "IMPOSSIBLE"
        break
    if bfs(N-1, graph, seen, next_v):
        ans = "POSSIBLE"
        break
    next_v.pop(0)
print(ans)

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

Solution (Python):
import collections as c
n,m=map(int,input().split())
print(['POSSIBLE','IMPOSSIBLE'][not [1 for c in c.Counter([[a,b][a==1] for a,b in [[i,j] for i,j in [list(map(int,input().split())) for _ in range(m)] if i==1 or j==n]]).values() if c>1]])

Solution (Python):

from collections import deque


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

if m == 1:
    print('IMPOSSIBLE')
    exit()

to = [[] for _ in range(n+1)]
for i in range(m):
    to[a[i]].append(b[i])
    to[b[i]].append(a[i])



inf = 200200
dist = [inf for _ in range(n+1)]
q = deque()
q.append(1)
dist[1] = 0 

while q:
    v = q.popleft()
    for u in to[v]:
        if dist[u] == inf:
            dist[u] = dist[v]+1
            q.append(u)

if dist[n] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N,M=list(map(int, input().split()))
S=set()
D=[]
for i in range(M):
    l=list(map(int, input().split()))
    if l[0]==1:
        S.add(l[1])
    else:
        D.append(l)


D.sort()
L=len(D)
for i in range(L):
    if D[i][1]==N and D[i][0] in S:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

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

for i in island[1]:
    if N in island[i]:
        print('POSSIBLE')
        exit(0)
print('IMPOSSIBLE')

Solution (Python):
n, m, *AB = map(int, open(0).read().split())

C, D = set(), set()
for a, b in zip(AB[::2], AB[1::2]):
  if a == 1:
    C.add(b)
  if b == n:
    D.add(a)

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

Solution (Python):
n, m = map(int,input().split())
init_island = set()
last_island = set()
for _ in range(m):
    a,b = map(int,input().split())
    a,b = min(a,b), max(a,b)
    if a == 1:
        init_island.add(b)
    elif b == n:
        last_island.add(a)
    else:
        continue
common = init_island.intersection(last_island)
if len(common) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
n, m = map(int, input().split())
 
g = [[] for _ 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)

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

print('IMPOSSIBLE')

Solution (Python):
import sys
sys.setrecursionlimit(200010)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = list(map(int,input().split()))
    G = [set([]) for k in range(N)]
    for i in range(M):
        A, B = set(map(int,input().split()))
        G[A-1].add(B-1)
        G[B-1].add(A-1)
    for e in G[0]:
        if e in G[N-1]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")
if __name__ == '__main__':
    main()

Solution (Python):
import collections
n, m = map(int, input().split())
visited = [False]*n
ships = [set() for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    ships[a-1].add(b-1)
    ships[b-1].add(a-1)

for i in range(1,n-1):
    if 0 in ships[i] and n-1 in ships[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

ans = {True: "POSSIBLE",
    False: "IMPOSSIBLE"}

print(ans[len(set(edge[0]) & set(edge[-1])) > 0])

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline

    n, m = map(int, input().split())
    first = list()
    second = list()

    for i in range(m):
        ai, bi = map(int, input().split())

        if ai == 1:
            first.append(bi)

        if bi == n:
            second.append(ai)

    ans = set(first) & set(second)

    if len(ans) > 0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

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


def read():
    N, M = map(int, input().strip().split())
    AB = []
    for i in range(M):
        a, b = map(int, input().strip().split())
        AB.append((a, b))
    return N, M, AB


def solve(N, M, AB):
    is_ok = True
    mid_b = set()
    mid_a = set()
    for a, b in AB:
        if a == 1:
            mid_b.add(b)
        elif b == N:
            mid_a.add(a)
    is_ok = len(mid_a.intersection(mid_b)) > 0
    return "POSSIBLE" if is_ok else "IMPOSSIBLE"


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

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


x = set()
for a, b in AB:
    if a == 1:
        x.add(b)
    if b == 1:
        x.add(a)

f = False

for a, b in AB:
    if (a in x and b == N) or (b in x and a == N):
        f = True

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

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

s1 = set()
sn = set()
for a,b in AB:
    if a==1:
        s1.add(b)
    if b==N:
        sn.add(a)

print('POSSIBLE' if s1&sn else 'IMPOSSIBLE')

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

ans=False
for i in A[1]:
    if i==N:
        ans=True
        break
    for j in A[i]:
        if j==N:
            ans=True
            break
print("POSSIBLE" if ans else "IMPOSSIBLE" )

Solution (Python):
N,M = map(int,input().rstrip().split(" "))
G = [[] for i in range(N + 1)]
ans = False
for i in range(M):
    a,b = map(int,input().rstrip().split(" "))
    G[a].append(b)
    G[b].append(a)
for i in G[1]:
    if (N in G[i]):
        ans = True
if ans:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
N, M = map(int, input().split())
from_one = []
to_n = []
for _ in range(M):
  a, b = map(lambda x:int(x)-1, input().split())
  if a == 0:
    from_one += [b]
  elif b == 0:
    from_one += [a]
  elif a == N-1:
    to_n += [b]
  elif b == N-1:
    to_n += [a]

from_one = set(from_one)
to_n = set(to_n)
if len(from_one & to_n) >= 1:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

s1 = [False] * N
sN = [False] * N

for i, s in enumerate(ship):
    if s[0] == 1:
        s1[s[1] - 1] = True

    if s[1] == N:
        sN[s[0] - 1] = True

ans = 'IMPOSSIBLE'
if any([p1 * pN for p1, pN in zip(s1, sN)]):
    ans = 'POSSIBLE'

print(ans)

Solution (Python):
import sys

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

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



for i in l[0]:
  for j in l[i-1]:
    if j==n:
      print("POSSIBLE")
      sys.exit()

print("IMPOSSIBLE")

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

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

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

travellist = sorted(travellist)


To_list = [0]*N
From_list = []
for i in range(M):

    oneroot = travellist[i]
    From = oneroot[0]
    To   = oneroot[1]

    if From == 1:
        To_list[To] = 1

    if To == N:
        From_list.append(From)


for i in From_list:
    if To_list[i] == 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Solution (Python):
N, M = [int(x) for x in input().split(" ")]
next_to_1 = []
next_to_last = []

for i in range(M):
  tmp = input().split(" ")
  if int(tmp[0]) == 1:
    next_to_1.append(int(tmp[1]))
  if int(tmp[1]) == N:
    next_to_last.append(int(tmp[0]))

if len(list(set(next_to_1) & set(next_to_last))) > 0:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

Solution (Python):
from collections import deque
n,m=map(int,input().split())
ab=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
que=deque()
que.append(1)
count=[0]*2+[-1]*(n-1)
while que:
    x=que.pop()
    for j in ab[x]:
        if count[j]==-1:
            count[j]=count[x]+1
            que.appendleft(j)
if count[n]==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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


def read():
    N, M = map(int, input().strip().split())
    AB = []
    for i in range(M):
        a, b = map(int, input().strip().split())
        AB.append((a, b))
    return N, M, AB


def solve(N, M, AB):
    S = [False for i in range(N+1)]
    T = [False for i in range(N+1)]
    for a, b in AB:
        if a > b:
            a, b = b, a
        if a == 1:
            S[b] = True
        elif b == N:
            T[a] = True
    for s, t in zip(S, T):
        if s and t:
            return "POSSIBLE"
    return "IMPOSSIBLE"


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

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

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

Solution (Python):
N, M = map(int, input().split())
to = [[] for _ in range(N)]
ans = 'IMPOSSIBLE'

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    to[a].append(b)
    to[b].append(a)
    
for nxt in to[0]:
    if N - 1 in to[nxt]:
        ans = 'POSSIBLE'
        break
        
print(ans)

Solution (Python):
from collections import deque 


N, M = map(int, input().split())
to = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    to[a].append(b)
    to[b].append(a)
    
que = deque()
que.append(0)
dist = [-1] * N
dist[0] = 0

while que:
    island = que.popleft()
    for nxt in to[island]:
        if dist[nxt] != -1:
            continue
        que.append(nxt)
        dist[nxt] = dist[island] + 1
        
print('POSSIBLE' if dist[N - 1] == 2 else 'IMPOSSIBLE')

Solution (Python):
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
x = set()
y = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        x.add(b)
    if b == n:
        y.add(a)
print(("POSSIBLE", "IMPOSSIBLE")[len(x & y) == 0])

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


dic = {}
isOK = False
for i in range(m):
    a,b = map(int,input().split())
    if a in [1,n]:
        dic.setdefault(b,0)
        dic[b] += 1
        if dic[b]==2:
            isOK = True
            break
    elif b in [1,n]:
        dic.setdefault(a,0)
        dic[a] += 1
        if dic[a]==2:
            isOK = True
            break















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

Solution (Python):
from collections import deque

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)

q=deque([(1,0)])
visit=[0]*(n+1)

while len(q)>0:
    u,cnt=q.popleft()

    visit[u]=1

    if u==n and cnt==2:
        print('POSSIBLE')
        exit(0)
    
    for v in g[u]:
        if visit[v] or cnt==2:
            continue

        q.append((v,cnt+1))

print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
d=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  if a==1 or b==1 or a==n or b==n:
    d[a-1].append(b)
    d[b-1].append(a)
for i in d[n-1]:
  if 1 in d[i-1]:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')

Solution (Python):
n,m=map(int,input().split())
M=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    M[a].append(b)
    M[b].append(a)
yes="POSSIBLE";no="IMPOSSIBLE"

for i in M[0]:
    if n-1 in M[i]:
        print(yes);exit()
print(no)

Solution (Python):
L=list()
R=list()
N,M=map(int,input().split())
for i in range(M):
  a,b=map(int,input().split())
  if a==1:
    L.append(b)
  elif b==1:
    L.append(a)
  if a==N:
    R.append(b)
  elif b==N:
    R.append(a)
L=set(L)
R=set(R)
if len(L&R)==0:
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

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

Solution (Python):
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

def solve():
    n, m = map(int, input().split())
    course = [[] for i in range(n)]
    for i in range(m):
        a, b = map(int, input().split())
        course[a-1].append(b)
        course[b-1].append(a)
    for i in course[0]:
        if n in course[i-1]:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
n, m = list(map(int, input().split()))
s1 = {}
sn = []

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

res = False
for s in sn:
    if s in s1:
        res = True
        break

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

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

goal = [0] * n
start = [0] * n

for a, b in ab:
    if a == 1:
        start[b] = 1
    if b == n:
        goal[a] = 1

flg = False
for i in range(n):
    if start[i] and goal[i]:
        flg = True

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

Solution (Python):
from collections import defaultdict
N, M = [int(x) for x in input().split()]
dict = defaultdict(bool)  
for i in range(M):
    a, b = [int(x) for x in input().split()]
    dict[(a, b)] = True

for j in range(1, N + 1):
    if dict[(1, j)] and dict[(j, N)]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
from collections import deque
n, m = map(int, input().split())
edges = [[]*n for _ in range(n)]

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

d = deque()
d.append(0)
visited = [False]*n
visited[0] = True
from_0 = [0]*n
while d:
    x = d.popleft()
    for child in edges[x]:
        if visited[child]:
            continue
        else:
            visited[child] = True
            d.append(child)
            from_0[child] = from_0[x] + 1

if from_0[n-1] == 2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

Solution (Python):
from collections import deque

INF=10**20

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

def bfs(s):
    seen = [0 for i in range(N+1)]
    d = [0 for i in range(N+1)]
    todo = deque()
    seen[s]=1
    todo.append(s)
    while 1:
      if len(todo)==0:break
      a = todo.popleft()
      if d[a] >= 2:continue
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
    return d

d = bfs(1)
if d[N] != 0 and d[N] <= 2:print('POSSIBLE')
else:print('IMPOSSIBLE')

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

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

if len(set(l1)&set(l2)) >=1:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

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

Solution (Python):
n,m = map(int,input().split())
a = [] 
z = [] 
an = 0
zn = 0
for i in range(m):
    x,y = map(int,input().split())
    if x == 1:
        zn += 1
        z.append(y)
    elif y == n:
        an += 1
        a.append(x)
    else:
        pass
a.sort()
z.sort()
i = 0
j = 0
while i < an and j < zn:
    if a[i] == z[j]:
        print('POSSIBLE')
        exit(0)
    else:
        if a[i] > z[j]:
            j += 1
        else:
            i += 1
print('IMPOSSIBLE')

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

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

for i in ab[1]:
  for j in ab[i]:
    if j == n:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

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

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

if len(adj[0] & adj[N - 1]) > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")