配点 : $300$ 点

問題文

高橋キングダムには、高橋諸島という、$N$ 個の島からなる諸島があります。 便宜上、これらの島を島 $1$、島 $2$、 ...、島 $N$ と呼ぶことにします。

これらの諸島の間では、船の定期便が $M$ 種類運行されています。 定期便はそれぞれ $2$ つの島の間を行き来しており、$i$ 種類目の定期便を使うと、 島 $a_i$ と島 $b_i$ の間を行き来する事ができます。

すぬけくんは今島 $1$ にいて、島 $N$ に行きたいと思っています。 しかし、島 $1$ から島 $N$ への定期便は存在しないことがわかりました。 なので、定期便を $2$ つ使うことで、島 $N$ に行けるか調べたいと思っています。

これを代わりに調べてあげてください。

制約

• $3 \leq N \leq 200,000$
• $1 \leq M \leq 200,000$
• $1 \leq a_i < b_i \leq N$
• $(a_i, b_i) \neq (1, N)$
• $i \neq j$ ならば $(a_i, b_i) \neq (a_j, b_j)$

入力

入力は以下の形式で標準入力から与えられる。

$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

島 $4$ へ行くには、定期便を $3$ つ使う必要があります。

100000 1
1 99999

IMPOSSIBLE

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

POSSIBLE

島 $1$、島 $4$、島 $5$ と移動すれば $2$ つの定期便で移動可能です。