Description

你和你的朋友 Pinky 有一个征服世界的计划。但首先，你们需要关闭一个秘密武器。

这个武器被藏在一个错综复杂的迷宫（一个图）中，只有一个入口。Pinky 将会在有秘密武器的房间（顶点）里关闭它。与此同时，安全小队会在图的入口处被警报唤醒，并试图穿过图去阻止 Pinky。你要尽可能拖慢安全小队的速度，为 Pinky 争取时间。通过任意一条边都需要 1 个时间单位，但你还可以“阻碍”最多 $K$ 个顶点。每经过一个被阻碍的顶点，需要额外花费 1 个时间单位。你需要选择一组顶点进行阻碍，使得安全小队到达秘密武器房间所需的时间尽可能长。

安全小队会从图的入口出发，目标是到达秘密武器房间。你需要在安全小队开始行动前就决定所有要阻碍的顶点，且安全小队会知道你阻碍了哪些顶点，并会选择最优路径。

阻碍秘密武器房间没有意义，因为当安全小队到达那里时，Pinky 已经被抓住，无法再拖延时间。另一方面，阻碍入口显然是一个好主意。

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为 $N, M, K$。接下来的 $M$ 行，每行包含一对顶点，表示一条边。顶点编号从 $0$（入口）到 $N-1$（秘密武器房间）。每对顶点中，第一个编号总是小于第二个编号，并且同一组测试数据中不会有重复的边。所有边都是双向的——安全小队可以沿任意方向通过。

Output Format

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是安全小队从入口到秘密武器房间所需的时间。

5
3 2 1
0 1
1 2
3 2 2
0 1
1 2
3 2 3
0 1
1 2
4 4 2
0 1
0 2
1 3
2 3
7 11 3
0 1
0 2
0 3
1 4
1 5
2 4
2 5
3 4
3 5
4 6
5 6

Case #1: 3
Case #2: 4
Case #3: 4
Case #4: 3
Case #5: 5

Hint

数据范围

• $1 \leq T \leq 100$。
• $2 \leq N \leq 100$。
• $1 \leq M \leq N \times (N - 1) / 2$。
• $1 \leq K \leq N$。
• 保证从房间 0 到房间 $N-1$ 总是存在一条路径。

小数据集（7 分）

• 时间限制：5 秒。
• 使用给定的 $K$，安全小队最多只能被延迟 2 个时间单位（相较于最短未阻碍路径）。

大数据集（29 分）

• 时间限制：10 秒。
• 无额外限制。

由 ChatGPT 4.1 翻译