题目描述

高桥王国中有一个名为高桥群岛的群岛，由 $N$ 座岛屿组成。为方便起见，这些岛屿编号为岛 $1$、岛 $2$、……、岛 $N$。

在这些岛屿之间，共有 $M$ 条定期船航线在运营。每条航线可以在两座岛屿之间往返，第 $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

输入

3 2
1 2
2 3

输出

POSSIBLE

样例 2

输入

4 3
1 2
2 3
3 4

输出

IMPOSSIBLE

样例 3

输入

100000 1
1 99999

输出

IMPOSSIBLE

样例 4

输入

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

输出

POSSIBLE

说明/提示

限制条件

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

样例说明2

要去往岛 $4$，需要用 $3$ 条定期航线。

样例说明4

只需按 “岛 $1$ → 岛 $4$ → 岛 $5$” 的顺序移动，即可用 $2$ 条定期航线到达目的地。

由 ChatGPT 5 翻译