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):
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    repn = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        repn[a - 1].append(b - 1)
        repn[b - 1].append(a - 1)
    visited = [0] * N

    def dfs(u, n):
        if n >= 2:
            visited[u] = 1
            return
        visited[u] = 1
        for v in repn[u]:
            if visited[v] != 0: continue
            dfs(v, n + 1)

    dfs(0, 0)
    if visited[N - 1] == 1:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

Solution (Python):
N,M=map(int,input().split())
c1=[]
c2=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        c1.append(b)
    if b==N:
        c2.append(a)
c1=set(c1)
c2=set(c2)
if c1&c2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
def resolve():
    N, M = [int(i) for i in input().split()]
    aabb = [list(map(int, input().split())) for _ in range(M)]
    to_N, from_1 = set(), set()
    for a, b in aabb:
        if b == N:
            to_N.add(a)
        elif a == 1:
            from_1.add(b)
    if len(to_N & from_1) > 0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


resolve()

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

Solution (Python):
N, M = map(int, input().split())
route_1 = [0] * (N+1)
route_n = [0] * (N+1)

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        route_1[b] = 1
    elif b == N:
        route_n[a] = 1

for i in range(2, N+1):
    if route_1[i] == 1 and route_n[i] == 1:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

Solution (Python):


import sys
sys.setrecursionlimit(10**9)










def solve(n,m,l):
  edges = {i+1:[] for i in range(n)}
  for i in range(m):
    a,b = l[i]
    edges[a].append(b)
    edges[b].append(a)
  return any(1 in v and n in v for k,v in edges.items())



def main():
  N,M = map(int,input().split())
  l = [tuple(map(int,input().split())) for _ in range(M)]
  print("POSSIBLE" if solve(N,M,l) else "IMPOSSIBLE")
  return

if __name__ == '__main__':
  main()

Solution (Python):


import sys
sys.setrecursionlimit(10**9)










def solve(n,m,l):
  edges = {i+1:[] for i in range(n)}
  for i in range(m):
    a,b = l[i]
    edges[a].append(b)
    edges[b].append(a)
  def dfs(start,end,rest):
    if rest == 0:
      return start == end
    else:
      return any(dfs(nextNode,end,rest-1) for nextNode in edges[start])

  return dfs(1,n,2)



def main():
  N,M = map(int,input().split())
  l = [tuple(map(int,input().split())) for _ in range(M)]
  print("POSSIBLE" if solve(N,M,l) else "IMPOSSIBLE")
  return

if __name__ == '__main__':
  main()

Solution (Python):
import collections
N,M = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(M)]
a.sort()
B = collections.Counter(x[0] for x in a)[1]
C = set([])
for i in range(B):
    C.add(a[i][1])
for i in range(M):
    if a[i][0] in C and a[i][1] == N:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

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

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

k = [1]
flag = 0
for _ in range(2):
    if flag == 1:
        break
    for j in k:
        kk = []
        kk += r[j]
        if n in r[j]:
            flag = 1
            break
    k = kk[:]

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

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

G = {i: [] for i in range(1, N + 1)}

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

res = False

for i in range(2, N):
    if 1 in G[i] and N in G[i]:
        res = True
        break


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

Solution (Python):
N, M = map(int, input().split())
a = [0] * M
b = [0] * M
list = []
for i in range(M):
  a[i], b[i] = map(int, input().split())
for i in range(M):
  if a[i] == 1:
    list.append(b[i])
  elif b[i] == N:
    list.append(a[i])
list = sorted(list)
ans = 'IMPOSSIBLE'
for i in range(len(list)-1):
  if list[i] == list[i+1]:
    ans = 'POSSIBLE'
    break
print(ans)

Solution (Python):
N, M = map(int, input().split())
d = {i + 1: [] for i in range(N)}

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

ans = False
one_to_i = d[1]
for i in one_to_i:
    if N in d[i]:
        ans = True
        break

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

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

edges = {i : [] for i in range(1, N+1)}
visited = [False for _ in range(N+1)]

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

def dfs(n, count):
  
  if count == 3:
    return False
  if n == N:
    return True
  visited[n] = True
  
  for edge in edges[n]:
    if visited[edge]:
      continue
    if dfs(edge, count + 1):
      return True
  
  return False

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

Solution (Python):
from collections import deque
def BFS(N,M,List):
    Graph = [[] for T in range(N+1)]
    for NodeM in range(0,M):
        Graph[List[NodeM][0]].append(List[NodeM][1])
        Graph[List[NodeM][1]].append(List[NodeM][0])

    Distance = [-1]*(N+1)
    Distance[0] = 0
    Distance[1] = 0
    From = [0]*(N+1)

    Deque = deque()
    Deque.append(1)
    while Deque:
        V = Deque.popleft()
        for NodeV in Graph[V]:
            if Distance[NodeV]==-1:
                Distance[NodeV] = Distance[V]+1
                Deque.append(NodeV)
                From[NodeV] = V

    return Distance[1:],From[1:]
  
N,M = (int(X) for X in input().split())
List = [[] for T in range(0,M)]
for T in range(0,M):
    List[T] = [int(X) for X in input().split()]
Distance,From = BFS(N,M,List)
if Distance[-1]==2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
From = set()
To = set()
for _ in range(M):
  a, b = map(int, input().split())
  if a == 1:
    From.add(b)
  if b == N:
    To.add(a)
if From.isdisjoint(To):
  print("IMPOSSIBLE")
else:
  print("POSSIBLE")

Solution (Python):
import sys
from collections import defaultdict
from heapq import heapify, heappush
n,m=map(int,input().split())
s=[tuple(map(int,input().split())) for _ in range(m)]
def hl():
  ret=[]
  heapify(ret)
  return ret
d=defaultdict(hl)
for x in s:
  heappush(d[x[0]],-x[1])
  heappush(d[x[1]],-x[0])
for e in d[1]:
  if d[-e][0]==-n:
    print('POSSIBLE')
    sys.exit()
print('IMPOSSIBLE')

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(*[iter(AB)] * 2):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    dist = [-1] * N
    dist[0] = 0
    queue = deque([0])
    while queue:
        v = queue.popleft()
        for nv in G[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                queue.append(nv)

    if dist[N - 1] in (1, 2):
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

    return


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
n,m=map(int,input().split())
ab=defaultdict(lambda: [])
for i in range(m):
  a,b=map(int,input().split())
  ab[a].append(b)
for aa in ab[1]:
  for bb in ab[aa]:
    if bb == n:
      print("POSSIBLE")
      exit()
print("IMPOSSIBLE")

Solution (Python):
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
t = [[] for _ in range(n + 1)]
for i in ab:
    t[i[1]].append(i[0])
flag = False
for j in t[n]:
    if 1 in t[j]:
        flag = True
        break
print("POSSIBLE") if flag else print("IMPOSSIBLE")

Solution (Python):
n, m = input().split()
a, b = set(), set()
for _ in range(int(m)):
    r = set(input().split())
    if "1" in r:
        a |= r
    if n in r:
        b |= r
print("POSSIBLE" * len(a & b) or "IMPOSSIBLE")

Solution (Python):

n, m = input().split()
a = set()
b = set()
for _ in range(int(m)):
    r = set(input().split())
    if "1" in r:
        a |= r
    if n in r:
        b |= r
print("POSSIBLE" if len(a & b) > 0 else "IMPOSSIBLE")

Solution (Python):

from collections import deque

n, m = map(int, input().split())
graph = [deque([]) for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in graph[1]:
    if n in graph[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

Solution (Python):
n, m = map(int, input().split())
l1 = []
ln = []
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        l1.append(b)
    elif b == 1:
        l1.append(a)
    elif a == n:
        ln.append(b)
    elif b == n:
        ln.append(a)
l1.sort()
ln.sort()
ans = False
for i in l1:
    low = 0
    high = len(ln) - 1
    while low <= high:
        mid = (low + high)//2
        if ln[mid] == i:
            ans = True
            break
        elif ln[mid] > i:
            high = mid - 1
        else:
            low = mid + 1
    if ans:
        break
if ans:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import numpy as np
n,m = map(int,input().split())
A1 = np.zeros(n,dtype=bool)
Ai = np.zeros(n,dtype=bool)
for i in range(m):
    a,b = map(int,input().split())
    if a == 1:
        A1[b-1] = True
    if b == n:
        Ai[a-1] = True
if np.any(Ai[A1]):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
d = {}
c = "IMPOSSIBLE"

for i in range(1,n):
    if i == 1:
        d[i] = []
    else:
        d[i] = 0

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        d[a].append(b)
    elif d[a] < b:
        d[a] = b

for k in d[1]:
    if d[k] == n:
        c = "POSSIBLE"

print(c)

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

lst1 = []
lstN = []

for i in range(M):
    if AB[i][0] == 1:
        lst1.append(AB[i][1])
    if AB[i][1] == N:
        lstN.append(AB[i][0])

if list(set(lst1) & set(lstN)) == []:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")

Solution (Python):
from sys import exit

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

cnt = [0] * n
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1 or a == n:
        cnt[b-1] += 1
    elif b == 1 or b == n:
        cnt[a-1] += 1

for c in cnt:
    if c == 2:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Solution (Python):
import sys
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
start = a[0][0]
goal = n
tmp,ans = [],[]
for i in range(m):
	if a[i][1] == goal:
		tmp.append(a[i][0])

for j in range(m):
		if a[j][0] == start:
			ans.append(a[j][1])
if len(set(tmp)&set(ans)) > 0:
	print('POSSIBLE')
	sys.exit()
print('IMPOSSIBLE')

Solution (Python):
from queue import Queue
n, m = map(int, input().split())
adj = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)
def bfs():
    queue = Queue()
    queue.put(1)
    distance = [10**6]*(n+1)
    distance[1] = 0
    while not queue.empty():
        u = queue.get()
        if u == n and distance[u] == 2:
            print ("POSSIBLE")
            return
        for a in adj[u]:
            if distance[u] + 1 <= 2 and distance[a] > distance[u] + 1:
                distance[a] = distance[u] + 1
                queue.put(a)
    print ("IMPOSSIBLE")
    return
bfs()

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

x=[]
y=[]

for i in lst:
  if i[0]==1:
    x+=[i[1]]
    
for i in lst:
  if i[1]==n:
    y+=[i[0]]
    
ans='POSSIBLE'

if len(list(set(x)))+len(list(set(y)))==len(list(set(x+y))):
  ans='IMPOSSIBLE'
    
print(ans)

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

d=[]
for i in range(m):
    if a[i][0]==1:
        d.append(a[i][1])
    else:
        break
e=[]
for i in range(m):
    if a[i][1]==n:
        e.append(a[i][0])
if len(set(e) & set(d))!=0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
import sys
N, M = list(map(int, input().split()))
S = set()
B = [False] * (N + 1)
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1:
        S.add(b)
    elif b == N:
        B[a] = True
for s in S:
    if B[s]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Solution (Python):
N,M=map(int,input().split())
E=[[False,False] for _ in range(N+1)]

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

    if a==1:
        E[b][0]=True

    if b==N:
        E[a][1]=True

F=False
for n in range(1,N+1):
    F|=(E[n][0]&E[n][1])

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

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

d = dict()
for a, b in p:
    if a not in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)
    if b not in d.keys():
        d[b] = []

node = deque()
node.append((1, 0))
visit = set()
while node:
    (s, count) = node.popleft()
    if s in visit:
        continue
    if s == n:
        if count == 2:
            print('POSSIBLE')
            exit()
        else:
            break
    for i in d[s]:
        node.append((i, count+1))
    visit.add(s)
print('IMPOSSIBLE')

Solution (Python):
N,M = map(int,input().split())
x = set()
y = set()
 
for m in range(M):
    a,b = map(int,input().split())
    if a==1:
        x.add(b)
    if b==N:
        y.add(a)

if x&y:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

s = set()
g = set()

for _ in range(M):
    A, B = map(int, input().split())
    if A == 1:
        s.add(B)
    if B == N:
        g.add(A)

if s & g:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

for m in range(M):
  a,b = map(int,input().split())
  if a==1:
    x.add(b)
  if b==N:
    y.add(a)

if x&y:
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

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

for a, b in ab:
    if check[a-1] == 1 and b == N:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
x = [0]*n
y = [0]*n
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a == 0:
        x[b] = 1
    if b == n-1:
        y[a] = 1

f = 0
for i in range(n):
    if x[i]*y[i] > 0:
        f = 1

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
query = [[] for _ in range(N)]
for _ in range(M):
    a, b = mapint()
    query[a-1].append(b-1)
    query[b-1].append(a-1)

checked = [0]*N
ans = False
def dfs(now, cnt):
    global ans
    if cnt==2:
        if now==N-1:
            ans = True
        return
    checked[now] = 1
    for nx in query[now]:
        if not checked[nx]:
            dfs(nx, cnt+1)

dfs(0, 0)
if ans:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

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

for i in range(1,N-1):
  if 0 in R[i] and N-1 in R[i]:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Solution (Python):
import heapq
INFTY = 10**6
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
dist = [INFTY for _ in range(N+1)]
dist[1] = 0
hist = [0 for _ in range(N+1)]
hist[1] = 1
heap = [(0,1)]
while heap:
    d,x = heapq.heappop(heap)
    if dist[x]<d:continue
    hist[x] = 1
    for y in G[x]:
        if hist[y]==0:
            if dist[y]>d+1:
                dist[y] = d+1
                heapq.heappush(heap,(d+1,y))
if dist[N]==2:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

Solution (Python):
from sys import stdin
n,m=map(int,input().split())
l = [list(map(int, stdin.readline().split())) for _ in range(m)]
s,e=[],[]
for i in l:
    if i[0]==1:
        s.append(i[1])
    if i[1]==n:
        e.append(i[0])
result = list(set(s) & set(e))
print('POSSIBLE' if result else 'IMPOSSIBLE')

Solution (Python):
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    edges = [[int(item) for item in input().split()] for _ in range(M)]
    
    togo = [[] for _ in range(N+1)]
    for f, t in edges:
        togo[f] += [t]
    
    is_found = False

    que = collections.deque()
    for goto in togo[1]:
        que.append(goto)

    is_found = False
    while que:
        node = que.popleft()
        for next_node in togo[node]:
            if next_node == N:
                is_found = True
            
            
    print('POSSIBLE') if is_found else print('IMPOSSIBLE')

if __name__ == "__main__":
    resolve()

Solution (Python):
N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
L_1 = set([l[1] for l in L if l[0]==1])
L_2 = set([l[0] for l in L if l[1]==N])
print("POSSIBLE" if L_1&L_2 else "IMPOSSIBLE")

Solution (Python):
n, m = [int(x) for x in input().split()]
f_set = set()
t_set = set()
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    if a == 1:
        f_set.add(b)
    elif b == n:
        t_set.add(a)
print("POSSIBLE" if len(f_set & t_set) >= 1 else "IMPOSSIBLE")

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

ship={}
for n in range(N):
    n=n+1
    ship[n]=[]

for m in range(M):
    a,b=list(map(int,input().split()))
    if a == 1:
        ship[a].append(b)
    else :
        if b == N:
            ship[a].append(b)

ans='IMPOSSIBLE'
for i in ship[1]:
    if len(ship[i]) != 0:
        ans='POSSIBLE'
        break
print(ans)

Solution (Python):






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





start = [sorted(ship)[1] for ship in ab if 1 in ship]
goal = [sorted(ship)[0] for ship in ab if N in ship]
if set(start) & set(goal):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):

import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd





def solve():
    n, m = [int(x) for x in input().split()]
    g = defaultdict(set)
    for _ in range(m):
        a, b = [int(x) for x in input().split()]
        g[a].add(b)
        g[b].add(a)
    
    for i in range(2, n):
        if 1 in g[i] and n in g[i]:
            print("POSSIBLE")
            return
    print("IMPOSSIBLE")



t = 1

for case in range(1,t+1):
    ans = solve()


"""

abc

"""

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

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

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

Solution (Python):
from collections import deque


def main():
    n, m = map(int, input().split())
    shuttles = [[] for _ in range(n+1)]
    for i in range(m):
        s, e = map(int, input().split())
        shuttles[s].append(e)
    d = deque(shuttles[1])
    ans = 'IMPOSSIBLE'
    while d:
        j = d.popleft()
        if n in shuttles[j]:
            ans = 'POSSIBLE'
            break
    print(ans)


if __name__ == "__main__":
    main()

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

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

p = set()
q = set()
for _ in range(int(m)):
    a, b = input().split()
    if a == "1":
        p.add(b)
    elif b == n:
        q.add(a)
else:
    if p & q:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

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

lands=[False for _ in range(N-1)]
goal_land=[]

for _ in range(M):
    a,b = map(int,input().split())
    if a == 1 or b == 1:
        if a == 1:
            lands[b-1] = True
        else:
            lands[a-1] = True
    elif a == N or b == N:
        if a == N:
            goal_land.append(b-1)
        else:
            goal_land.append(a-1)




for i in goal_land:
    if lands[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

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

p = set()
q = set()

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        p.add(b)
    elif b == n:
        q.add(a)
else:
    print("POSSIBLE" if p & q else "IMPOSSIBLE")

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

p = set()
q = set()

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        p.add(b)
    elif b == n:
        q.add(a)
else:
    if p & q:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

Solution (Python):
def main():
    from collections import defaultdict
    n,m = map(int,input().split())
    G = defaultdict(set)
    for _ in range(m):
        a,b = map(int,input().split())
        G[a].add(b)
        G[b].add(a)

    flg = 0
    for i in G[1]:
        if n in G[i]:
            flg = 1
    if flg == 1:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

main()

Solution (Python):
N, M = map(int, input().split())
teiki_1 = []
teiki_N = []
for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == 1:
        teiki_1.append(a if a != 1 else b)
    if a == N or b == N:
        teiki_N.append(a if a != N else b)
if len(set(teiki_1) & set(teiki_N)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Solution (Python):
n,m = map(int,input().split())
g = [set() for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].add(b)
    g[b].add(a)
for i in g[0]:
    if i in g[n-1]: print('POSSIBLE');exit()
print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
left = []
right = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
left = set(left)
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
N, M = map(int, input().split())
left = []
right = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
left = set(left)
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

Solution (Python):
n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
w = [0]*(n+1)
for i,j in a:
    if (i==1):
        w[j] = 1
for i,j in a:
    if (j==n):
        if (w[i]==1):
            print("POSSIBLE")
            exit()
print("IMPOSSIBLE")

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

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

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

d = {}
for i in range(200002):
	d[i]={}

n,m = readInts()
ab = [readInts() for i in range(m)]
for i in ab:
	d[i[0]][i[1]]=1

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

print("IMPOSSIBLE")

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

import bisect
def isin(arr,x):
	
	return arr[min(bisect.bisect_left(arr,x),len(arr)-1)]==x

n,m = readInts()
ab = [readInts() for i in range(m)]
go1 = []
for i in range(m):
	if ab[i][0]==1:
		go1.append(ab[i][1])
go1.sort()
for i in range(m):
	if isin(go1,ab[i][0]) and ab[i][1]==n:
		print("POSSIBLE")
		exit()

print("IMPOSSIBLE")

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

serv1 = set()
servN = set()
for _ in range(M):
    a, b = map(int, input().split())
    if a != 1 and b != N:
        continue

    if a == 1:
        serv1.add(b)
    elif b == N:
        servN.add(a)

print("POSSIBLE" if len(serv1.intersection(servN)) > 0 else "IMPOSSIBLE")

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

dist = [float('inf')] * n
def dfs(s, p, depth):
    if depth>2: return
    dist[s] = min(dist[s], depth)
    for to in g[s]:
        if to==p: continue
        if dist[to] < dist[s]+1: continue
        dfs(to, s, depth+1)

dfs(0, -1, 0)

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

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

for i in c[1]:
  if n in c[i]:
    print('POSSIBLE')
    exit()

print('IMPOSSIBLE')

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

data1 = [0] * (n+1)
data2 = [0] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        data1[b+1] = 1
    if b == n:
        data2[a+1] = 1


for i in range(n+1):
    if data1[i] == 1 and data2[i] == 1:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

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

for i in ab[0]:
  if ab[i].count(n-1) >= 1:
    print("POSSIBLE")
    exit()
print("IMPOSSIBLE")

Solution (Python):
n,m = map(int,input().split())
a_lst = []
for i in range(m):
  a_lst.append( list(map(int,input().split())) )
 
ans = "IMPOSSIBLE"
 
start_lst = []
goal_lst = []
for a in a_lst:
  if a[0] == 1:
    start_lst.append(a[1])
  if a[1] == n:
    goal_lst.append(a[0])
goal_lst = set(goal_lst)
for s in start_lst:
  if s in goal_lst:
    ans = "POSSIBLE"
    
print(ans)

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

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

ans = "POSSIBLE" if (start_set & goal_set) else "IMPOSSIBLE"
print(ans)

Solution (Python):
n,m=map(int,input().split())
list1=[]
listn=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        list1.append(b)
    elif b==1:
        list1.append(a)
    elif a==n:
        listn.append(b)
    elif b==n:
        listn.append(a)
list1=set(list1)
listn=set(listn)
ans=0
if len(listn)!=0:
    for i in range(len(list1)):
        num=list1.pop()
        if num in listn:
            ans=1
            break
if ans==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Solution (Python):
import sys
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, M = mi()
    l = [[] for i in range(N)]
    for i in range(M):
        a, b = mi()
        l[a-1].append(b-1)
        l[b-1].append(a-1)

    for v in l[0]:
        if N-1 in l[v]:
            print('POSSIBLE')
            return
    print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
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)
for g in G[0]:
    if N - 1 in G[g]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Solution (Python):
import sys
from collections import deque
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)
d = [0] * N
d[0] = 1
Q = deque()
Q.append(0)
while Q:
    q = Q.popleft()
    if d[q] == 3:
        print('IMPOSSIBLE')
        sys.exit()
    for g in G[q]:
        if g == N - 1:
            print('POSSIBLE')
            sys.exit()
        if d[g] == 0:
            d[g] = d[q] + 1
            Q.append(g)
print('IMPOSSIBLE')

Solution (Python):
n, m = map(int, input().split())
lst = [[] for i in range(n + 1)]
for i in range(m):
  tpl = tuple(map(int, input().split()))
  lst[tpl[0]].append(tpl[1])
for i in lst[1]:
  if n in lst[i]:
    print('POSSIBLE')
    exit()
print('IMPOSSIBLE')