세계 정복 (작은 입력)

당신과 친구 핑키는 세계 정복을 계획하고 있다. 그러려면 먼저 비밀 병기 하나를 무력화해야 한다.

비밀 병기는 입구가 하나뿐인 복잡한 통로 미로 안에 있다. 미로는 그래프이고, 방이 정점, 통로가 간선이다. 핑키는 비밀 병기가 있는 방에서 병기를 무력화하고 있다. 그동안 입구의 경비대가 경보를 받고 핑키를 막으러 미로를 달려온다. 당신은 경비대를 최대한 늦춰서 핑키에게 시간을 벌어 준다.

경비대가 통로 하나를 지나는 데 시간 1이 걸린다. 여기에 더해 당신은 방을 최대 $K$개까지 막을 수 있고, 막힌 방을 지나는 데는 시간 1이 더 걸린다. 즉 경비대가 어떤 경로로 이동할 때 걸리는 시간은 그 경로의 통로 수에 경로 위에 있는 막힌 방의 수를 더한 값이다. 비밀 병기가 있는 방만 예외다. 경비대가 그 방에 닿는 순간 핑키를 잡으므로, 그 방을 막아도 시간은 늘어나지 않는다. 반면 입구는 경비대가 반드시 지나는 방이라서, 막아 두면 시간이 그만큼 늘어난다.

막을 방은 경비대가 출발하기 전에 모두 정해야 한다. 경비대는 어느 방이 막혔는지 전부 알고, 그 정보에 맞춰 가장 빨리 도착하는 경로를 고른다. 당신은 경비대의 도착 시간이 가장 늦어지도록 막을 방을 고른다. 경비대가 입구에서 비밀 병기가 있는 방까지 가는 데 걸리는 시간을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 $N$, $M$, $K$가 주어진다. 다음 $M$개의 줄에는 통로 하나로 이어진 두 방의 번호가 주어진다. 방 번호는 0번(입구)부터 $N-1$번(비밀 병기가 있는 방)까지다. 각 줄에서 앞의 번호가 뒤의 번호보다 작고, 같은 방 쌍은 한 테스트 케이스 안에서 두 번 나오지 않는다. 통로는 양방향이라서 경비대는 어느 쪽으로든 지날 수 있다.

제한

• $1 \le T \le 100$
• $2 \le N \le 100$
• $1 \le M \le N \times (N - 1) / 2$
• $1 \le K \le N$
• 0번 방에서 $N-1$번 방으로 가는 경로가 항상 존재한다.
• 주어진 $K$로는 아무 방도 막지 않았을 때의 최단 시간보다 2를 넘게 늦출 수 없다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 경비대가 입구에서 비밀 병기가 있는 방까지 가는 데 걸리는 시간이다.