← 返回题目列表

AtCoder · arc079_a

C. 猫的阴核和航行

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

在高桥王国,有一个群岛 N 岛屿,称为高桥群岛。 为了方便起见,我们将它们称为岛屿 1, 岛 2, ..., 岛 N.

有 M 这些岛屿之间的各种定期船只服务。 每项服务都连接两个岛屿。的 i第服务连接岛屿 a_i 和岛 b_i.

猫蛇在岛上 1 现在,想去海岛 N。 然而发现岛上没有船服务 1 前往岛屿 N,所以他想知道是否可以去岛 N 使用两艘船服务。

帮助他。

约束

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

输入

输入由标准输入按以下格式给出:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

输出

如果可以去海岛的话 N 通过使用两艘船服务,打印 POSSIBLE;否则,打印 IMPOSSIBLE.


示例输入 1

3 2
1 2
2 3

示例输出 1

POSSIBLE

示例输入 2

4 3
1 2
2 3
3 4

示例输出 2

IMPOSSIBLE

您必须乘坐三趟船才能到达岛屿 4.


示例输入 3

100000 1
1 99999

示例输出 3

IMPOSSIBLE

示例输入 4

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

示例输出 4

POSSIBLE

你可以到达岛屿 5 使用两条船服务:岛屿 1 -> 岛屿 4 -> 岛屿 5.