#ABC068C. 高桥群岛
高桥群岛
题目描述
高桥群岛有 座岛屿,编号为 ,以及 条双向航线。每条航线连接两座不同的岛屿,同一对岛屿之间至多有一条航线。保证岛 与岛 之间没有直达航线。
你从岛 出发,希望恰好乘坐两条航线到达岛 ,即经过某座中转岛,再到达目的地。请判断是否存在这样的路线。
输入格式
第一行输入两个整数 $n,m\left(3\leqq n\leqq2\times10^5;\ 1\leqq m\leqq\min\{2\times10^5,n(n-1)/2-1\}\right)$,分别代表岛屿数量与航线数量。
此后 行,第 行输入两个整数 $a_i,b_i\left(1\leqq a_i<b_i\leqq n;\ (a_i,b_i)
eq(1,n)\right)$,代表一条双向航线。不同航线的端点对互不相同。
输出格式
如果可以恰好乘坐两条航线到达目的地,输出 ;否则输出 。
测试样例
3 2
1 2
2 3
POSSIBLE
样例 1 解释
可以依次经过岛 到达目的地,恰好使用两条航线。第二个样例中只能沿 前进,需要三条航线,因此不符合要求。
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