P16735 [GKS 2019 #E] Cherries Mesh

你的朋友最近刚上完烹饪课，现在他想在学校朋友面前炫耀一下，制作一道精美的甜点。他想出了一道名为“樱桃网”的美味甜点。为了制作这道菜，他已经收集了编号为 $1$ 到 $N$ 的樱桃。他还决定用糖制成的甜丝连接每一对不同的无序樱桃。甜丝根据含糖量分为红色和黑色。每条黑色糖丝含有 $1$ 单位糖，每条红色糖丝含有 $2$ 单位糖。 但事实证明，这道甜点现在太甜了，而他学校的朋友们最近正在节食，通常喜欢含糖量较低的菜肴。他现在非常困惑，向你求助。你能帮他找出应该移除哪些糖丝，使得每对樱桃通过糖丝直接或间接相连，并且甜点的含糖量最小吗？

输入的第一行给出测试用例的数量 $T$。 每个测试用例以一行包含两个整数 $N$ 和 $M$ 开始，分别表示樱桃的数量和黑色糖丝的数量。 接下来 $M$ 行，每行描述一对由黑色糖丝连接的樱桃。第 $i$ 行包含编号为 $C_i$ 和 $D_i$ 的樱桃，表示樱桃 $C_i$ 和 $D_i$ 之间由一条黑色糖丝连接。 注意：输入中未出现的任何其他樱桃对，表示它们之间由红色糖丝连接。

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

在第一个样例中，有两个樱桃，它们由一条黑色糖丝连接。移除任何一条糖丝都会导致樱桃断开。因此，最小含糖量为 $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 完成