G - Equal Connected Components

2 secs 1024 MB
kusirakusira's icon kusirakusira

配点 : 200点

問題文

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

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

制約

  • 1N2×105 1≦N≦2×10^5
  • 0Mmin(2×105,N(N1)/2) 0≦M≦ \mathrm{min} (2×10^5, N(N-1)/2)
  • 1ui,viN1≦u_i, v_i≦N
  • uiviu_i ≠ v_i
  • ij{ui,vi}{uj,vj}i≠j ⇒\{u_i, v_i\} ≠ \{u_j, v_j\}
  • 入力はすべて整数

入力

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

NN MM
u1u_1 v1v_1
u2u_2 v2v_2
\vdots
uMu_M vMv_M

出力

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


入出力例1

入力
7 6
1 2
2 3
3 1
4 5
2 6
3 6
出力
2

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


入出力例2

入力
100 0
出力
0

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


入出力例3

入力
3 3
1 2
1 3
2 3
出力
1

Submit


Go (1.21)