logo AlgoBeat OnlineJudge
登录 注册

#103803. [BZOJ 3803] Idea Frame

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一张 个点 条边的无向图,你可以对其进行下面两种操作:

  1. 把点 拆为 ,并将 连出的边不重不漏地任意分给 ,且每个新点至少分到一条边,然后把 删掉,其中 是由你指定的数字;
  2. 把点 合成一个点 ,需要满足 的度数均为 分别连向 所连向的点,然后把 删掉。

现在你需要求出最少操作多少次能够使得整张图是一个简单环。

输入格式

第一行两个整数

接下来 行,每行两个整数 表示一条 之间的边。

输出格式

一行一个整数表示最小操作次数。

样例

样例输入 #1

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

样例输出 #1

4

样例解释

如图即为一种合法的操作顺序。

数据范围与提示

对于 的数据,