You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你居住的小区正在进行快递柜网络的优化改造。小区里有 $n$ 个快递柜点位（用 $1$ 到 $n$ 编号），当前这些点位之间铺设了 $m$ 条步行路径（双向通行）。理想的快递配送网络应该像一棵"树"结构：任意两个快递柜之间有且仅有一条最短步行路径（即没有环路，路径不重复），这样能保证快递员以最高效率配送。

但由于前期施工规划问题，现有的路径可能存在冗余（比如绕路的环路）或缺失（部分快递柜无法直接连通）。你需要通过最少的施工操作，将当前网络改造成理想的树结构。每次操作可以选择：

• 拆除一条现有的步行路径
• 新增一条步行路径连接两个快递柜

请计算最少需要多少次操作，才能让整个快递柜网络成为高效的树结构。

输入格式

第一行：整数 $n$（快递柜点位数量，$1 ≤ n ≤ 10⁶$）和$m$（现有路径数量，$0 ≤ m ≤ 10⁶$）。

接下来 $m$ 行：每行两个整数 $u, v$，表示当前存在一条连接快递柜 $u 和 v$ 的步行路径。

输出格式

输出一行整数，表示最少需要的施工操作次数。

样例

样例输入

5 5
1 2
2 1
5 4
5 4
2 5

样例输出

3

样例解释

在第一组样例中，可以先分别删除$(1,2),(5,4)$，后添加$(2,3)$，花费 $3$ 次操作修好设备，可以证明这 是最小次数

数据分布

$40\%$的数据，$1 \le n,m \le 100$

$100\%$的数据，$1 \le n,m \le 10^6$

时空限制

• 时间限制：$1s$
• 空间限制：$256M$