布设哨兵

CC回来得比预计快——哨塔比想象中好拆，因为Zero把兵力调到核心去了。

"外围空了。"她说，"但核心更紧了。"

"那我们就趁虚而入。"你说，"在关键通道布设自己的哨兵——不是人，是自动感应器。"

"感应器？"

"对。"你说，"一旦Zero的巡逻队经过，感应器就报警，我们提前避开。"

"布在哪？"

你把核心区域的地图展开。里面有七条主通道，交叉成一张网。每个交叉点都需要覆盖，但感应器有范围限制——每个只能覆盖相邻的两条通道。

"这样布。"你说，"在交叉点A放一个，覆盖东通道和北通道。在交叉点B放一个，覆盖南通道和西通道……"

"够了？"CC问。

"不够。"你说，"七个交叉点，每个感应器只能覆盖两个方向。我们还需要更多。"

"多少？"

你算了算。七个点，每个点连两到三条边。要覆盖所有边，最少需要……

"四个。"你说，"四个感应器，放在四个关键交叉点，就能覆盖所有通道。"

"哪四个？"

你标出来——A、C、E、G。四个点，像四只眼睛，盯着整个核心区。

"放。"你说。

CC把感应器一个个装上墙。每个只有指甲盖大，但灵敏度高得吓人。

"最后一个。"她说，"G点。"

"装完就撤。"你说，"感应器会自动工作。"

"它们不会坏？"

"会。"你说，"但坏了我们会知道——信号断了，就说明那个区域有情况。"

"那就是陷阱变成了警报。"CC说。

"对。"你说，"Zero以为我们在躲，其实我们在看。"

Echo把感应器的信号接入服务器。屏幕上跳出七个绿点——全部在线。

"哨兵就位。"她说。

题目描述

核心区域有 $n$ 个交叉点，$m$ 条通道。要在交叉点放置感应器，每个感应器可以覆盖与该点相邻的所有通道。求覆盖所有通道所需的最少感应器数量。

输入格式

$n, m$。然后 $m$ 条边 $(u, v)$。

输出格式

最少感应器数量。

输入样例

3 2
1 2
2 3

输出样例

Case :1
0
Case :2
0
Case :3
0

提示

• 点覆盖问题——选最少的点，使得每条边至少有一个端点被选。
• 二分图最小点覆盖 = 最大匹配（Kőnig定理）。
• 一般图是NP-hard，但本题数据范围允许搜索或近似。

"感应器在线。"Echo说。

"七个点。"CC数了数，"四只眼睛，看七条路。"

"对。"你说，"现在我们知道Zero的动向了。"

"下一步？"

"下一步。"你说，"画地图。"

"地图？"

"核心区的平面图。"你说，"感应器告诉我们通道在哪，但入口在哪还不知道。我们需要一张完整的图。"

"画。"CC说，"我来量。"

[第四题：绘制地形]