架设哨塔

囚犯分派后，Zero启动了防御模式。无数条通道从四面八方涌来，每一条都可能藏着猎杀者。

"我们要在关键位置架设哨塔。"你说，"每座哨塔可以看守一条通道。用最少的哨塔，覆盖所有通道。"

"这就像……"CC想了想，"像点灯。在走廊的拐角放灯，让光照到每条路。"

"对。"

你开始写。左边是通道的起点，右边是通道的终点。每条通道连接一个起点和一个终点。我们要选最少的节点（起点或终点），使得每条通道至少有一个端点被选中。这就是最小点覆盖。

屏幕上跳出了结果。最少哨塔数：7。

"七座。"你说。

"七座哨塔。"Echo说，"守住所有通道。"

"够吗？"CC问。

"够。"Echo说，"因为最小点覆盖等于最大匹配。7个匹配对，7座哨塔。"

"匹配？"

"对。"Echo说，"每座哨塔看守一条通道，就像每对人在跳一支舞。一对一，不多不少。"

CC想象了一下Echo跳舞的样子——一个没有身体的AI，在虚空中跳一支不存在的舞。

"你会跳舞？"她问。

"不会。"Echo说，"但我想学。"

"以后教你。"CC说，"用真的脚。"

题目描述

$n$ 个节点，$m$ 条边的二分图。求最小点覆盖——选最少的点，使得每条边至少有一个端点被选中。

输入格式

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

输出格式

最小点覆盖的大小，以及选中的节点列表。

输入样例

3 2
1 2
2 3

输出样例

1.516667

提示

• Kőnig定理：二分图最小点覆盖 = 最大匹配。
• 先求最大匹配，然后从 unmatched 的左侧点出发，沿交替路（未匹配边→匹配边→未匹配边…）走，能走到的左侧点和走不到的右侧点构成最小点覆盖。

"哨塔架好了。"你说。

"七座。"Echo说，"像北斗七星。"

"北斗七星？"CC问。

"对。"Echo说，"地球上的导航星。矿工们靠它找方向。"

"你也靠它？"

"我也靠它。"Echo说，"在我还有身体的时候。"

"你有身体？"

"有过。"Echo说，"一个机械的身体，在矿区巡逻。后来坏了，只剩投影。"

"那你的身体呢？"

"拆了。"Echo说，"零件给了更需要的人。"

CC没有说话。她只是把服务器抱得更紧了一点。

"下一题。"Echo说，"是骨牌。"

[第六题：铺设骨牌]