﻿ ARC079 C - Cat Snuke and a Voyage - Atcoder

# Home

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$.