P2100 [第三章习题7.5]相框
![](https://cdn.maxuetang.cn/ojimages/uploadFiles/image/20180731/20180731160633_480_htimg.jpg)
T君不满足于焊接奇形怪状的作品,强烈的破坏欲驱使他拆掉这个作品,然后将之焊接成规整的形状。这会儿,T君正要把这个怪物改造成一个环形,当作自己的相框,步骤如下:
T君约定了两种操作:
1. 烧熔一个焊点:使得连接在焊点上的某些导线相分离或保持相连(可以理解为:把焊点上的导线划分为若干个类,相同类中的导线相连,不同类之间的导线相离)
2. 将两根导线的自由端(即未与任何导线相连的一端)焊接起来。
例如上面的步骤中,先将A点烧熔,使得导线1与导线2、4点分离;再将D点烧熔,使得4、5与3、7相离;再烧熔E,使7与6、8相离;最后将1、7相连。
T君想用最少的操作来将原有的作品改造成为相框(要用上所有的导线)。
输入文件的第一行共有两个整数n和m — 分别表示原有的作品的焊点和导线的数量 (0 ≤ n ≤ 1 000, 2 ≤ m ≤ 50 000)。焊点的标号为1~n。 接下来的m行每行共有两个整数 — 导线两端所连接的两个焊点的标号,若不与任何焊点相连,则将这一端标号为0。
原有的作品可能不是连通的。
某些焊点可能只有一根导线与之相连,在该导线的这一端与其他导线相连之前,这些焊点不允许被烧熔。
某些焊点甚至没有任何导线与之相连,由于T君只关心导线,因此这些焊点可以不被考虑。
6 8
1 2
1 3
3 4
1 4
4 6
5 6
4 5
1 5
4
30%的数据中n≤10;
100%的数据中n≤1000。