题目描述

你的朋友最近刚上完烹饪课，现在他想在学校朋友面前炫耀一下，制作一道精美的甜点。他想出了一道名为“樱桃网”的美味甜点。为了制作这道菜，他已经收集了编号为 $1$ 到 $N$ 的樱桃。他还决定用糖制成的甜丝连接每一对不同的无序樱桃。甜丝根据含糖量分为红色和黑色。每条黑色糖丝含有 $1$ 单位糖，每条红色糖丝含有 $2$ 单位糖。

但事实证明，这道甜点现在太甜了，而他学校的朋友们最近正在节食，通常喜欢含糖量较低的菜肴。他现在非常困惑，向你求助。你能帮他找出应该移除哪些糖丝，使得每对樱桃通过糖丝直接或间接相连，并且甜点的含糖量最小吗？

输入格式

输入的第一行给出测试用例的数量 $T$。

每个测试用例以一行包含两个整数 $N$ 和 $M$ 开始，分别表示樱桃的数量和黑色糖丝的数量。

接下来 $M$ 行，每行描述一对由黑色糖丝连接的樱桃。第 $i$ 行包含编号为 $C_i$ 和 $D_i$ 的樱桃，表示樱桃 $C_i$ 和 $D_i$ 之间由一条黑色糖丝连接。

注意：输入中未出现的任何其他樱桃对，表示它们之间由红色糖丝连接。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是最小可能的含糖量。

2
2 1
1 2
3 1
2 3

Case #1: 1
Case #2: 3

提示

在第一个样例中，有两个樱桃，它们由一条黑色糖丝连接。移除任何一条糖丝都会导致樱桃断开。因此，最小含糖量为 $1$。

在第二个样例中，我们可以保留连接樱桃 $2$ 和樱桃 $3$ 的黑色糖丝，并移除任何红色糖丝，这样得到的最小含糖量为 $3$。

限制条件

$1 \le T \le 100$。

$M \le N \times (N-1)/2$。

对于所有 $i$，$1 \le C_i \le N$。

对于所有 $i$，$1 \le D_i \le N$。

对于所有 $i$，$C_i \neq D_i$。

每个 $\{C_i, D_i\}$ 互不相同。

测试集 1（可见）

$1 \le N \le 100$。

$0 \le M \le 100$。

测试集 2（隐藏）

对于至少 $90\%$ 的测试用例：

$1 \le N \le 1000$。

$0 \le M \le 1000$。

对于所有测试用例：

$1 \le N \le 10^5$。

$0 \le M \le 10^5$。

翻译由 DeepSeek V4 Pro 完成