1676: 相框

题目描述


原题来自:福建集训 2011
P 大的基础电路实验课是一个无聊至极的课。每次实验,T 君总是提前完成,管理员却不让 T 君离开,T 君只能干坐在那儿无所事事。
先说说这个实验课,无非就是把几根导线和某些元器件(电阻、电容、电感等)用焊锡焊接起来。
为了打发时间,T 君每次实验做完后都在焊接一些诡异的东西,这就是他的杰作:

T 君不满足于焊接奇形怪状的作品,强烈的破坏欲驱使他拆掉这个作品,然后将之焊接成规整的形状。这会儿,T 君正要把这个怪物改造成一个环形,当作自己的相框,步骤如下:



T 君约定了两种操作:
烧熔一个焊点:使得连接在焊点上的某些导线相分离或保持相连(可以理解为:把焊点上的导线划分为若干个类,相同类中的导线相连,不同类之间的导线相离)
将两根导线的自由端(即未与任何导线相连的一端)焊接起来。
例如上面的步骤中,先将
A
A 点烧熔,使得导线
1
1 与导线
2,4
2,4 点分离;再将
D
D 点烧熔,使得
4,5
4,5 与
3,7
3,7 相离;再烧熔
E
E,使
7
7 与
6,8
6,8 相离;最后将
1,7
1,7 相连。
T 君想用最少的操作来将原有的作品改造成为相框(要用上所有的导线)。

输入


第一行共有两个整数
n
n 和
m
m——分别表示原有的作品的焊点和导线的数量。焊点的标号为
1 \sim n
1∼n。 接下来的
m
m 行每行共有两个整数——导线两端所连接的两个焊点的标号,若不与任何焊点相连,则将这一端标号为
0
0。
原有的作品可能不是连通的。
某些焊点可能只有一根导线与之相连,在该导线的这一端与其他导线相连之前,这些焊点不允许被烧熔。
某些焊点甚至没有任何导线与之相连,由于 T 君只关心导线,因此这些焊点可以不被考虑。

输出


只包含一个整数——表示 T 君需要将原有的作品改造成相框的最少步数。

样例输入


6 8
1 2
1 3
3 4
1 4
4 6
5 6
4 5
1 5

样例输出


4

提示


数据范围与提示
30\%
30% 的数据中
n \le 10
n≤10;
100\%
100% 的数据中
0 \le n \le 1000,2 \le m \le 50000
0≤n≤1000,2≤m≤50000。

来源/分类


ybttg 图论 欧拉回路

请先 登录 后评论
  • 0 关注
  • 0 收藏,328 浏览
  • 轩爸 提出于 2019-08-02 22:18

相似问题