题目描述

$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\ に対し\ v_i$ と $v_{i+1\ \bmod\ n}$ の間に辺が存在するものがあることをいいます。

输入格式

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

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

输出格式

答えを出力せよ。

题目大意

给定一个简单无向图，要求删除最小的边数（可以不删）使得图中没有环。

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

2

4 2
1 2
3 4

0

5 3
1 2
1 3
2 3

1

提示

制約

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

Sample Explanation 1

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