Taking Over the World (Large)

You and your friend Pinky plan to take over the world. First you have to disable one secret weapon.

The weapon is hidden inside a twisted maze of passages with a single entrance. The passages are given as a graph. Pinky is at the vertex that holds the secret weapon, disabling it. Meanwhile the security team at the entrance is alerted and runs through the graph to reach Pinky in time to stop him. You slow the security team down to give Pinky as much time as possible.

Traversing any edge takes $1$ unit of time. On top of that you can obstruct up to $K$ vertices, and traversing an obstructed vertex takes $1$ additional unit of time. Choose the set of vertices that slows the security team down the most.

Compute how much time the security team needs to get from the entrance to the vertex with the secret weapon. You have to commit every obstruction before the guards start, and the guards know which vertices are obstructed and take an optimal path for that choice.

Obstructing the secret weapon vertex has no effect, because the guards have already caught Pinky once they reach it. Obstructing the entrance, on the other hand, is clearly a good idea, since the guards pass through that vertex as they start.

The first line contains the number of test cases $T$. The first line of each test case contains $N$, $M$ and $K$, and the next $M$ lines each contain a pair of vertices connected by an edge. Vertices are numbered from $0$ (the entrance) to $N-1$ (the secret weapon room). On every line the first vertex number is always smaller than the second one, and no pair of vertices appears twice in the same test case. Edges are bidirectional, so the guards can travel along an edge in either direction.

Limits

• $1 \le T \le 100$
• $2 \le N \le 100$
• $1 \le M \le N \times (N-1) / 2$
• $1 \le K \le N$
• There is always a path from room $0$ to room $N-1$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the time the guards need to get from the entrance to the secret weapon room.