bzoj#P3803. Idea Frame

Idea Frame

题目描述

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

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

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

输入格式

第一行两个整数 n,mn,m

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

输出格式

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

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

样例解释

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

数据规模与约定

对于 100%100\% 的数据,0n1030\leq n\leq 10^31m5×1041\leq m\leq 5\times 10^4