C - Cat Snuke and a Voyage

Contest Duration: 2017-07-29(Sat) 12:00 - 2017-07-29(Sat) 13:40 (local time) (100 minutes) Back to Home

C - Cat Snuke and a Voyage Editorial

Time Limit: 2 sec / Memory Limit: 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 と出力する。

入力例 1Copy

Copy

3 2
1 2
2 3

出力例 1Copy

Copy

POSSIBLE

入力例 2Copy

Copy

出力例 2Copy

Copy

IMPOSSIBLE

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

入力例 3Copy

Copy

100000 1
1 99999

出力例 3Copy

Copy

IMPOSSIBLE

入力例 4Copy

Copy

出力例 4Copy

Copy

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 1Copy

Copy

3 2
1 2
2 3

Sample Output 1Copy

Copy

POSSIBLE

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

IMPOSSIBLE

You have to use three boat services to get to Island $4$ .

Sample Input 3Copy

Copy

100000 1
1 99999

Sample Output 3Copy

Copy

IMPOSSIBLE

Sample Input 4Copy

Copy

Sample Output 4Copy

Copy

POSSIBLE

You can get to Island $5$ by using two boat services: Island $1$ -> Island $4$ -> Island $5$ .