bzoj#P3803. Idea Frame
Idea Frame
题目描述
有一张 个点 条边的无向图,你可以对其进行下面两种操作:
- 把点 拆为 ,并将 连出的边不重不漏地任意分给 ,且每个新点至少分到一条边,然后把 删掉,其中 是由你指定的数字;
- 把点 合成一个点 ,需要满足 的度数均为 , 分别连向 所连向的点,然后把 删掉。
现在你需要求出最少操作多少次能够使得整张图是一个简单环。
输入格式
第一行两个整数 。
接下来 行,每行两个整数 表示一条 之间的边。
输出格式
一行一个整数表示最小操作次数。
6 8
1 2
1 3
3 4
1 4
4 6
5 6
4 5
1 5
4
样例解释
如图即为一种合法的操作顺序。
数据规模与约定
对于 的数据,,。