세계 정복 (라지)

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

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

간선 하나를 지나는 데 시간 $1$이 걸린다. 여기에 더해 정점을 최대 $K$개까지 막아 둘 수 있고, 막힌 정점을 지나가려면 시간 $1$이 더 든다. 경비대를 가장 많이 늦추는 정점 집합을 고르면 된다.

경비대가 입구에서 출발해 비밀 병기가 있는 정점까지 가는 데 걸리는 시간을 구하라. 막을 정점은 경비대가 출발하기 전에 모두 정해야 하고, 경비대는 어느 정점이 막혔는지 알고 그에 맞는 최적 경로로 움직인다.

비밀 병기가 있는 정점을 막는 것은 의미가 없다. 경비대가 그 정점에 닿는 순간 이미 핑키를 잡았으므로 더 늦출 수 없기 때문이다. 반대로 입구를 막는 것은 분명히 이득이다. 경비대가 출발하면서 그 정점을 지나기 때문이다.

첫 줄에 테스트 케이스의 개수 $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$번 방으로 가는 경로가 항상 존재한다.

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