一个间谍从你的陷阱中逃出来了，干掉了你的警卫，并且带走了你毁灭世界的计划。你的糟糕的行动由此受到了威胁。现在你需要在他逃出基地之前抓到他。
　　你的基地由一系列房间和连接它们的双向隧道组成，隧道只在房间处相交。每个房间都配有监控摄像，使你能在任意时刻了解间谍所处的位置。另外，每条隧道里都装有遥控炸药，触发后可以永久毁坏该隧道。间谍在隧道中移动极快，因此你不可能把他困在炸毁的一条隧道中，但你可以炸毁一些隧道，使他无法逃出基地。
　　显然，间谍不可能逃出基地。所以你的目标是在困住他的同时炸毁最少的隧道，因为之后的重建非常昂贵。找到一种策略，使得在最坏情况下需要炸毁的隧道数最小。

　输入包含多组数据。每组数据的第一行包含两个整数R, T，分别表示房间的隧道的数量。接下来T行，每行两个整数a, b(0 <= a, b <= R)，表示隧道两端的房间编号。形如"0 x"或"x 0"的输入表示联通房间x和基地外部的隧道。
　　间谍从1出发，你需要阻止他到达点0（基地外部）。

对第i组输入，输出"Case i: {ans}\n\n"，其中${ans}表示对应的答案。
　　参见样例输出的格式。

数据规模和约定

　　1 <= R <= 50, 1 <= T <= 1000。
　　每个测试点至多包含五组数据。

蓝桥杯