세계 정복

당신과 친구 Pinky에게는 세계를 정복할 계획이 있다. 하지만 먼저 어떤 비밀 무기를 무력화해야 한다.

그 비밀 무기는 입구가 하나인 복잡하게 뒤틀린 통로의 미로(그래프) 안에 숨겨져 있다. Pinky는 비밀 무기가 있는 정점에서 그것을 무력화할 것이다. 그동안 그래프 입구에 있는 보안팀에 경보가 전달되고, 보안팀은 제시간에 Pinky에게 도달하여 그를 막으려고 그래프를 달릴 것이다. 당신은 Pinky에게 가능한 한 많은 시간을 주기 위해 보안팀의 이동을 늦출 것이다. 그래프의 어느 간선을 통과하는 데에도 한 단위의 시간이 걸리지만, 추가로 최대 K개의 정점을 "방해"할 수 있다. 방해된 정점을 통과하는 데에는 한 단위의 시간이 추가로 걸린다. 보안팀을 가능한 한 많이 늦추는 정점 집합을 골라 방해할 것이다.

보안팀이 그래프 입구에서 출발하여 비밀 무기 정점에 도달하려 한다면, 그곳에 도달하는 데 시간이 얼마나 걸리는가? 보안 요원들이 이동을 시작하기 전에 모든 방해 지점을 확정해야 하며, 보안 요원들은 당신이 어느 정점을 방해했는지 알고 그 정보에 따라 최적의 경로를 선택한다는 점에 유의하라.

비밀 무기 정점을 방해하는 것은 보안 요원들이 이미 Pinky를 붙잡은 뒤에는 그들을 더 늦추지 않으므로 유용하지 않다. 반면 입구를 방해하는 것은 분명 좋은 생각이다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 2 ≤ N ≤ 100. 1 ≤ M ≤ N * (N - 1) / 2. 1 ≤ K ≤ N. 방 0에서 방 N - 1까지 가는 경로는 항상 존재한다.

작은 데이터 세트

시간 제한: 240초. 주어진 K를 사용할 때, 방해되지 않은 최단 경로의 길이와 비교하여 보안 요원들을 2시간 단위보다 더 지연시키는 것은 불가능하다.

큰 데이터 세트

시간 제한: 480초. 추가 제한은 없다.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 N, M, K가 포함된 한 줄로 시작한다. 다음 M개의 줄에는 각각 간선으로 연결된 한 쌍의 정점이 주어진다. 정점에는 0(입구)부터 N - 1(비밀 무기 방)까지 번호가 매겨져 있다. 첫 번째 정점은 항상 두 번째 정점보다 작으며, 같은 테스트 케이스에서 동일한 정점 쌍이 두 번 이상 등장하지 않는다. 간선은 양방향이다. 즉, 보안 요원들은 어느 간선이든 양쪽 방향으로 이동할 수 있다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 보안 요원들이 입구에서 비밀 무기 방까지 이동하는 데 걸리는 시간이다.