[ABC068C] Cat Snuke and a Voyage

### 题意 有很多小岛，编号$1$到$n$，某两个岛之间有船可以到达，每次从$1$号小岛出发，要到$n$号岛屿。规定只能做两次船，问是否能到达目标岛屿。 ### 输入 第一行第一个数字是要到达的岛屿$n$，第二行一个数字是$m$，表示有$m$个岛之间有船可以连通，接下来$m$行每行两个数（岛的编号 ），表示某两个岛连通。 ### 输出 如果能到达，输出```POSSIBLE```，否则输出```IMPOSSIBLE``` ``` ### 题意 有很多小岛，编号$1$到$n$，某两个岛之间有船可以到达，每次从$1$号小岛出发，要到$n$号岛屿。规定只能做两次船，问是否能到达目标岛屿。 ### 输入 第一行第一个数字是要到达的岛屿$n$，第二行一个数字是$m$，表示有$m$个岛之间有船可以连通，接下来$m$行每行两个数（岛的编号 ），表示某两个岛连通。 ### 输出 如果能到达，输出```POSSIBLE```，否则输出```IMPOSSIBLE``` ### 数据范围 $3≤N≤200000$ $1≤M≤200000$ $1≤ai<bi≤N$ $(ai,bi)≠(1,N)$ 如果$i≠j$则$(ai,bi)≠(aj,bj).$ ``` ### 数据范围 $3≤N≤200000$ $1≤M≤200000$ $1≤ai<bi≤N$ $(ai,bi)≠(1,N)$ 如果$i≠j$则$(ai,bi)≠(aj,bj).$ ```

[problemUrl]: https://atcoder.jp/contests/abc068/tasks/arc079_a 高橋キングダムには、高橋諸島という、$ N $ 個の島からなる諸島があります。 便宜上、これらの島を島 $ 1 $、島 $ 2 $、 ...、島 $ N $ と呼ぶことにします。 これらの諸島の間では、船の定期便が $ M $ 種類運行されています。 定期便はそれぞれ $ 2 $ つの島の間を行き来しており、$ i $ 種類目の定期便を使うと、 島 $ a_i $ と島 $ b_i $ の間を行き来する事ができます。 すぬけくんは今島 $ 1 $ にいて、島 $ N $ に行きたいと思っています。 しかし、島 $ 1 $ から島 $ N $ への定期便は存在しないことがわかりました。 なので、定期便を $ 2 $ つ使うことで、島 $ N $ に行けるか調べたいと思っています。 これを代わりに調べてあげてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_M $ $ b_M $

定期便を $ 2 $ つ使いたどり着けるならば `POSSIBLE`、たどり着けないならば `IMPOSSIBLE` と出力する。

3 2
1 2
2 3

POSSIBLE

4 3
1 2
2 3
3 4

IMPOSSIBLE

100000 1
1 99999

IMPOSSIBLE

5 5
1 3
4 5
2 3
2 4
1 4

POSSIBLE

### 制約 - $ 3\ ≦\ N\ ≦\ 200,000 $ - $ 1\ ≦\ M\ ≦\ 200,000 $ - $ 1\ ≦\ a_i\ <\ b_i\ ≦\ N $ - $ (a_i,\ b_i)\ \neq\ (1,\ N) $ - $ i\ \neq\ j $ ならば $ (a_i,\ b_i)\ \neq\ (a_j,\ b_j) $ ### Sample Explanation 2 島 $ 4 $ へ行くには、定期便を $ 3 $ つ使う必要があります。 ### Sample Explanation 4 島 $ 1 $、島 $ 4 $、島 $ 5 $ と移動すれば $ 2 $ つの定期便で移動可能です。