题目 1947:
蓝桥杯算法提高VIP-Tunnels
时间限制: 3s
内存限制: 192MB 提交: 4 解决: 0
题目描述
一个间谍从你的陷阱中逃出来了，干掉了你的警卫，并且带走了你毁灭世界的计划。你的糟糕的行动由此受到了威胁。现在你需要在他逃出基地之前抓到他。
你的基地由一系列房间和连接它们的双向隧道组成，隧道只在房间处相交。每个房间都配有监控摄像，使你能在任意时刻了解间谍所处的位置。另外，每条隧道里都装有遥控炸药，触发后可以永久毁坏该隧道。间谍在隧道中移动极快，因此你不可能把他困在炸毁的一条隧道中，但你可以炸毁一些隧道，使他无法逃出基地。
显然，间谍不可能逃出基地。所以你的目标是在困住他的同时炸毁最少的隧道，因为之后的重建非常昂贵。找到一种策略，使得在最坏情况下需要炸毁的隧道数最小。
输入格式
输入包含多组数据。每组数据的第一行包含两个整数R, T，分别表示房间的隧道的数量。接下来T行，每行两个整数a, b(0 <= a, b <= R)，表示隧道两端的房间编号。形如"0 x"或"x 0"的输入表示联通房间x和基地外部的隧道。
间谍从1出发，你需要阻止他到达点0（基地外部）。
输出格式
对第i组输入，输出"Case $i: ${ans}\n\n"，其中${ans}表示对应的答案。
参见样例输出的格式。
样例输入
4 6
1 2
1 3
2 4
3 4
4 0
4 0
4 6
1 2
1 3
1 4
2 0
3 0
4 0
0 0