← 返回题目列表

AtCoder · tenka1_2015_qualA_d

D. 哈西彭

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

問題文

对于某个连通图,若去掉某条边后图变为非连通,则称该边为桥。

不包含自环或重边的图称为简单图。

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