C - Cat Snuke and a Voyage 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 300 点

問題文

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

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

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

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

制約

  • 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)

入力

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

N M
a_1 b_1
a_2 b_2
:
a_M b_M

出力

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

入力例 1

3 2
1 2
2 3

出力例 1

POSSIBLE

入力例 2

4 3
1 2
2 3
3 4

出力例 2

IMPOSSIBLE

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

入力例 3

100000 1
1 99999

出力例 3

IMPOSSIBLE

入力例 4

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

出力例 4

POSSIBLE

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

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.