D - ハシポン Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

ある連結なグラフについて、取り除くとグラフが非連結になるような辺のことを橋と呼びます。

また、自己辺や多重辺を含まないグラフを単純グラフと呼びます。

ワタナベくんは橋をちょうど1本含む単純グラフをハシポングラフと名づけました。

連結な無向単純グラフが与えられるので、最小で何本の辺を追加したらハシポングラフになるかを求めてください。

ただし、ハシポングラフにすることが不可能な場合は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