CF51F Caterpillar

一个毛毛虫定义为 一个无向联通无环图上 存在一条路径 $p$ 使得任意一个节点距离 $p$ 的距离至多为 $1$ 。 毛毛虫可以包含自环 （ 一条从一个顶点连向自己的边 ），但是不可以包含重边。 这个图片是一个毛毛虫的例子：  现在你有一张无向图 $G$ 。你被允许做一些合并操作。 每次操作将两个顶点合并成一个顶点 。 每次选择任意两个顶点 $a ,b (a≠b)$ , 这些顶点以及它们的边 （ 至少连接着 $a,b$ 中一个点的边 ） 将被删除 ，而后顶点 $w$ 会被加入，以及对于每条边 $(x,a),(x,b)$ 都会有新边 $( x,w)$ 加入 。 如果有一条边 $(a,b)$ 它会被转换成自环 $(w,w)$ 。 得到的图 （ 操作结束后 ） 可能会有重边。我们注意到这个操作减少了 $1$ 个顶点 ，却没有改变边的数量。 合并操作可以简单的描述为 将图中两个顶点合并为图中的一个顶点并继承原来所有的边。 你可以连续地使用合并操作，从而将给定的图转变成一个毛毛虫。 编写一个程序，这个程序将要输出这张图转变成一个毛毛虫的最少操作次数。

无

无