C - Don’t be cycle Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1 から N の番号がついており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。 このグラフから 0 本以上のいくつかの辺を削除してグラフが閉路を持たないようにするとき、削除する辺の本数の最小値を求めてください。

単純無向グラフとは 単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。

閉路とは 単純無向グラフが閉路を持つとは、i \neq j ならば v_i \neq v_j を満たす長さ 3 以上の頂点列 (v_0, v_1, \ldots, v_{n-1}) であって、各 0 \leq i < n に対し v_i と v_{i+1 \bmod n} の間に辺が存在するものがあることをいいます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは単純
  • 入力はすべて整数

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

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

出力例 1

2

頂点 1 と頂点 2 を結ぶ辺・頂点 4 と頂点 5 を結ぶ辺の 2 本を削除するなどの方法でグラフが閉路を持たないようにすることができます。
1 本以下の辺の削除でグラフが閉路を持たないようにすることはできないので、2 を出力します。

入力例 2

4 2
1 2
3 4

出力例 2

0

入力例 3

5 3
1 2
1 3
2 3

出力例 3

1

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

What is a simple undirected graph? A simple undirected graph is a graph without self-loops or multi-edges whose edges have no direction.

What is a cycle? A cycle in a simple undirected graph is a sequence of vertices (v_0, v_1, \ldots, v_{n-1}) of length at least 3 satisfying v_i \neq v_j if i \neq j such that for each 0 \leq i < n, there is an edge between v_i and v_{i+1 \bmod n}.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is simple.
  • All values in the input are integers.

Input

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

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

Sample Output 1

2

One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

0

Sample Input 3

5 3
1 2
1 3
2 3

Sample Output 3

1