「KDOI-02」一个网的路
题目背景
「{*^$&#$~!@ovo}(他们也有路网?有趣。)」
「{&%#@~akoio!@}(该干的活先干完吧,玩物丧志的东西待会再说。)」
「{!%_&#%@yw?}(您语文是不是没学好?)」
蔚蓝的天空下,人们还不知道危险的来临。
题目描述
敌对文明被惹怒了。他们想用一种有趣的方式摧毁地球的路网。地球的路网可以近似为一个含有 $n$ 个节点 $m$ 条无向边的**森林**。他们想用以下 $2$ 种操作:
- 炸毁一个城市 $u$ 向外连接的所有道路。
- 在城市 $u,v$ 间新建一条道路。
来将地球上的路网改成效率最低的形式:一条链。可惜的是,他们的智商都不怎么高。于是,他们抓住了你,要求你给出一种方案,使得他们操作的次数最少。可怜的你在万般无奈之下,决定写一个程序,帮助他们算出结果。
输入输出格式
输入格式
从标准输入中读入数据。
输入的第一行包含 $2$ 个正整数 $n,m$。
接下来 $m$ 行,每行 $2$ 个正整数 $u,v$ ,表示在城市 $u,v$ 间有一条无向道路。
输出格式
输出到标准输出。
输出共一行一个整数,表示外星人的最少操作次数。
输入输出样例
输入样例 #1
3 1
1 2
输出样例 #1
1
输入样例 #2
见附件中的 traffic2.in
输出样例 #2
见附件中的 traffic2.ans
输入样例 #3
见附件中的 traffic3.in
输出样例 #3
见附件中的 traffic3.ans
说明
**【样例解释】**
+ **样例 1 解释:**
初始图:
![](https://cdn.luogu.com.cn/upload/image_hosting/2z6ava49.png)
对城市 $2,3$ 进行操作二。
![](https://cdn.luogu.com.cn/upload/image_hosting/lqhomfm5.png)
此时已经成为了一条链。
***
**【数据范围】**
对于 $100\%$ 的数据,$0\le m<n\le2\times10^6$ 且保证输入合法。
|测试点编号|$n\le$|特殊性质|
|:-:|:-:|:-:|
|$1\sim2$|$10$|A|
|$3\sim6$|$500$|无|
|$7\sim8$|$10^4$|A|
|$9$|$10^4$|B|
|$10\sim12$|$10^4$|无|
|$13\sim15$|$10^6$|无|
|$16\sim20$|$2\times10^6$|无|
+ 特殊性质 A:保证每个连通块都为二叉树。
+ 特殊性质 B:保证每个顶点的度数不超过 $2$。
**【提示】**
本题 I/O 量较大,推荐使用较快的 I/O 方式。