题目描述

高橋キングダムには、高橋諸島という、$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 と出力する。

题目大意

题意

有很多小岛，编号$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).$

```input1
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$ つの定期便で移動可能です。