C - Make it Forest Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

頂点に 1 から N の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。i 番目の辺は頂点 u_i と頂点 v_i を結ぶ辺です。
グラフを森にするためには辺を最低何本削除する必要がありますか？

森とは 単純無向グラフ F が森であるとは、F が閉路を含まないことを言います。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5\right)
  • 1 \leq u_i \lt v_i \leq N
  • 入力で与えられるグラフは単純
  • 入力される値は全て整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

4 4
1 2
1 3
2 4
3 4

出力例 1

1

例えば 1 番目の辺を削除すると、グラフは森になります。

入力例 2

5 0

出力例 2

0

入力例 3

10 10
7 9
4 6
6 10
2 5
5 6
5 9
6 8
4 8
1 5
1 4

出力例 3

2

Score : 350 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges, where the vertices are labeled 1 to N. The i-th edge connects vertices u_i and v_i.
What is the minimum number of edges that need to be deleted from this graph so that the graph becomes a forest?

What is a forest? A simple undirected graph F is called a forest if and only if F does not contain any cycle.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5\right)
  • 1 \leq u_i < v_i \leq N
  • The given graph is simple.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the answer.

Sample Input 1

4 4
1 2
1 3
2 4
3 4

Sample Output 1

1

For example, if you delete the first edge, the graph becomes a forest.

Sample Input 2

5 0

Sample Output 2

0

Sample Input 3

10 10
7 9
4 6
6 10
2 5
5 6
5 9
6 8
4 8
1 5
1 4

Sample Output 3

2