分数: 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.