cho.sh

Taking Over The World (Small)

Block up to K rooms to make the fastest route from the entrance to the weapon room, counting one extra step per blocked room, as long as possible.

Medium7Shortest pathGraphBrute forceNo attempts yetTime limit5sMemory limit512 MB

Problem

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

The weapon sits inside a twisted maze of passages with a single entrance. The maze is a graph: rooms are vertices and passages are edges. Pinky is in the room with the secret weapon, disabling it. Meanwhile the security team at the entrance is alerted and runs through the maze to stop him. Your job is to slow the team down and buy Pinky as much time as possible.

The team spends one unit of time on each passage it walks. On top of that you may obstruct up to KK rooms, and walking through an obstructed room costs one extra unit of time. So the time a route takes is the number of passages on it plus the number of obstructed rooms on it. The room with the secret weapon is the one exception. The guards catch Pinky the moment they reach that room, so obstructing it adds nothing. The entrance is different: every route starts there, so obstructing the entrance always costs the guards one more unit.

You must commit to the whole set of obstructed rooms before the guards start. The guards know exactly which rooms you obstructed and pick a route that reaches the weapon as early as possible given that knowledge. You pick the rooms that make their arrival as late as possible. Report how long the guards need to get from the entrance to the room with the secret weapon.

Input

The first line contains the number of test cases TT. TT test cases follow. Each one starts with a line containing NN, MM, and KK. The next MM lines each contain a pair of rooms joined by one passage. Rooms are numbered from 0 (the entrance) to N−1N-1 (the room with the secret weapon). On every line the first number is smaller than the second, and no pair of rooms appears twice in the same test case. Passages are bidirectional, so the guards can walk along one in either direction.

Limits

  • 1≤T≤1001 \le T \le 100
  • 2≤N≤1002 \le N \le 100
  • 1≤M≤N×(N−1)/21 \le M \le N \times (N - 1) / 2
  • 1≤K≤N1 \le K \le N
  • There is always a route from room 0 to room N−1N-1.
  • With the given KK it is never possible to delay the guards by more than 2 units of time compared with the shortest route when nothing is obstructed.

Output

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 room with the secret weapon.