题目描述

在 CEOI 社区花园中，我们培育着一批特殊的花，它们的根系紧密交织在一起。如果我们将这些根剪断，只要剪得不过于激进、没有造成无法修复的损伤，它们就会重新生长。

如果两朵花 $a$ 和 $b$ 的根系交织在一起，我们称它们是“相连”的；否则，称它们是“不相连”的。根系按照以下规则生长：设 $a$ 和 $b$ 是两朵不相连的花。如果至少存在另外 $2$ 朵花 $c$ 和 $d$，使得 $a$ 和 $b$ 都分别与 $c$ 和 $d$ 相连，那么 $a$ 与 $b$ 之间会长出根系，从而变为相连。

这些花已经生长了一段时间，所有能够按照上述规则长出的根都已经长成。换言之，如果两朵花 $a$ 和 $b$ 都与某两朵花 $c$ 和 $d$ 相连，那么可以保证 $a$ 与 $b$ 也彼此相连。

现在，我们需要将整座花园连根挖起，并迁往下一届 CEOI 的举办地。为了简化迁移过程，我们希望剪断尽可能多的根。不过，我们也希望这些花最终能够重新生长到当前状态。最多可以剪断多少对相连花朵之间的根，使它们仍能恢复到当前状态？至于恢复需要经过多少轮生长并不重要。

输入格式

输入第一行包含两个以空格分隔的整数 $n$ 和 $m$，分别表示花朵数量以及当前已有的连接数量。接下来有 $m$ 行，每行包含一对整数 $a_i$ 和 $b_i$，表示花朵 $a_i$ 与 $b_i$ 相连。花朵以 $1\ldots n$ 的整数编号。输入保证满足题目描述中的规则。

输出格式

输出一个整数，表示最多可以剪断的连接数量。

9 14
1 2
1 4
1 5
2 4
2 5
3 4
4 5
3 6
4 6
6 7
6 9
7 9
8 9
5 8

2

提示

样例说明

下图表示样例中尚未剪断任何根时的花朵连接情况。可以验证，按照题目所述的生长过程，此时无法形成任何新的连接。

:::align{center} :::

剪断后的样例中少了 $2$ 条连接。花朵 $1$ 与 $2$ 都和花朵 $4$、$5$ 相连，因此花朵 $1$ 与 $2$ 之间的连接可以重新长出。类似地，花朵 $4$ 与 $5$ 都和花朵 $1$、$2$ 相连，因此花朵 $4$ 与 $5$ 之间的连接也可以重新长出。

:::align{center} :::

限制条件

• $1\le n\le 1000$
• $1\le m\le 10^5$

子任务

• 子任务 $1$（$20$ 分）：$n\le 10$ 且 $m\le 20$
• 子任务 $2$（$14$ 分）：$m=\dfrac{n(n-1)}{2}$
• 子任务 $3$（$15$ 分）：保证每朵花至多与另外 $7$ 朵花相连。
• 子任务 $4$（$15$ 分）：$n\le 50$ 且 $m\le 1000$
• 子任务 $5$（$36$ 分）：无额外限制。

翻译由 ChatGPT-5.6 完成