G - Equal Connected Components

配点 : 200点

頂点に から の番号が、辺に から の番号が付いた 頂点 辺の単純無向グラフが与えられます。
番目の辺は頂点 と頂点 を結びます。
連結成分の数を変えずに元のグラフから最大何本の辺を削除することが出来ますか。

※ 連結成分とは
任意の 頂点間にパスが存在するような部分グラフのうち極大なものことを言います。

• 入力はすべて整数

入力は以下の形式で標準入力から与えられる。

答えを出力してください。

7 6
1 2
2 3
3 1
4 5
2 6
3 6

2

元のグラフの連結成分の数は つです。
例えば、 番目の辺を削除しても連結成分の数はつのままです。
つより多くの辺を削除することは出来ないので を出力します。

100 0

0

元のグラフに辺が存在しないこともあります。

3 3
1 2
1 3
2 3

1