#ABC068C. 高桥群岛

高桥群岛

题目描述

\hspace{15pt}高桥群岛有 nn 座岛屿,编号为 1∼n1\sim n,以及 mm 条双向航线。每条航线连接两座不同的岛屿,同一对岛屿之间至多有一条航线。保证岛 11 与岛 nn 之间没有直达航线。

\hspace{15pt}你从岛 11 出发,希望恰好乘坐两条航线到达岛 nn,即经过某座中转岛,再到达目的地。请判断是否存在这样的路线。

输入格式

\hspace{15pt}第一行输入两个整数 $n,m\left(3\leqq n\leqq2\times10^5;\ 1\leqq m\leqq\min\{2\times10^5,n(n-1)/2-1\}\right)$,分别代表岛屿数量与航线数量。

\hspace{15pt}此后 mm 行,第 ii 行输入两个整数 $a_i,b_i\left(1\leqq a_i<b_i\leqq n;\ (a_i,b_i)

\hspace{15pt}eq(1,n)\right)$,代表一条双向航线。不同航线的端点对互不相同。

输出格式

\hspace{15pt}如果可以恰好乘坐两条航线到达目的地,输出 "POSSIBLE"\texttt{"POSSIBLE"};否则输出 "IMPOSSIBLE"\texttt{"IMPOSSIBLE"}。

测试样例

3 2
1 2
2 3
POSSIBLE

样例 1 解释

\hspace{15pt}可以依次经过岛 1,2,31,2,3 到达目的地,恰好使用两条航线。第二个样例中只能沿 1,2,3,41,2,3,4 前进,需要三条航线,因此不符合要求。

4 3
1 2
2 3
3 4
IMPOSSIBLE
100000 1
1 99999
IMPOSSIBLE
5 5
1 3
4 5
2 3
2 4
1 4
POSSIBLE