output_description: If it is possible to go to Island N by using two boat services, print
  `POSSIBLE`; otherwise, print `IMPOSSIBLE`.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      a_1 b_1
      a_2 b_2
      :
      a_M b_M
attempt: #55 C - Cat Snuke and a Voyage
  import collections from deque
  N,M = map(int,input().split())
  G = [[] for _ in range(N)]
  for _ in range(M):
      a, b = map(int, input().split())
      a -= 1; b -= 1
      G[a].append(b)
      G[b].append(a)
  
  # BFS のためのデータ構造
  dist = [-1]*N
  que = deque([])
  
  # 初期条件 (島 1 を初期ノードとする)
  dist[0] = 0
  que.append(0)
  
  while (len(que) != 0):
      v = que.popleft()# キューから先頭頂点を取り出す
      for next_v in G[v]:
          if (dist[next_v] != -1):# next_v が探索済みならスルー
              continue
          #新たな頂点 next_v について情報を更新してキューに追加
          dist[next_v] = dist[v] + 1
          que.append(next_v)
  if dist[N-1] == 2:
      print('POSSIBLE')
  else:
      print('INPOSSIBLE')
problem_description: 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.
samples: [{"input": "3 2\n    1 2\n    2 3", "output": "POSSIBLE\n    \n\n* * *"}, {"input": "4 3\n    1 2\n    2 3\n    3 4", "output": "IMPOSSIBLE\n    \n\nYou have to use three boat services to get to Island 4.\n\n* * *"}, {"input": "100000 1\n    1 99999", "output": "IMPOSSIBLE\n    \n\n* * *"}, {"input": "5 5\n    1 3\n    4 5\n    2 3\n    2 4\n    1 4", "output": "POSSIBLE\n    \n\nYou can get to Island 5 by using two boat services: Island 1 -> Island 4 ->\nIsland 5."}]