問題文
对于某个连通图,若去掉某条边后图变为非连通,则称该边为桥。
不包含自环或重边的图称为简单图。
Watanabe同学将恰好包含一条桥的简单图命名为“桥牌图”。
给定一个连通的无向简单图,请求出最少需要增加多少条边,才能使其成为桥牌图。
但是,如果不可能将其变为哈希棋图的话IMPOSSIBLE请输出。
入力
输入是按以下格式从标准输入给出的。
V E a_1 b_1 a_2 b_2 : a_E b_E
- 1 行中给出图的顶点数 V ( 1 \leq V \leq 100,000 ) 和边的数目 E ( 0 \leq E \leq 150,000 ) 用空格分隔。 在
- 继续 E 行有 i 第条边所连接的顶点编号 a_i 和 按字典顺序比较 b_i ( 0 \leq{} a_i, b_i \leq{} V-1 ) 用空格分隔。 在
- 保证给定的图是连通的无向简单图。
出力
最少需要添加的边数,或者IMPOSSIBLE该值应乘以1行输出。在输出末尾插入换行符。
配点
针对此问题设置了部分分数。
- V \leq 20 的测试用例都得到正确回答,35 点。 如果您正确回答了所有满足
- V \leq 2000 的测试用例都得到正确回答,30 点。 如果您正确回答了所有满足
- 如果所有测试用例都回答正确,除上述之外, 55 点。 如果您正确回答了所有满足
入力例1
4 4 0 1 1 2 2 3 3 1
出力例1
0
给定的图已经是哈希棋图。
入力例2
5 5 0 1 1 2 2 3 3 1 3 4
出力例2
1
例如,添加连接顶点1和顶点4的边即可将其变为哈希棋图。
入力例3
3 2 0 1 1 2
出力例3
IMPOSSIBLE
哈希棋图必须是简单图。
入力例4
1 0
出力例4
IMPOSSIBLE