좀비들 사이의 인디아나 존스

인디아나 존스는 우여곡절 끝에 신체와 정신을 지배하는 부적을 찾는 탐험을 마쳤다. 다행히 부적은 손에 넣었지만, 문제는 그가 갇힌 미로가 좀비로 가득하고 좀비를 물리치려던 부적이 작동하지 않는다는 점이다. 결국 인디아나는 오래된 방식, 즉 스미스 앤 웨슨 리볼버로 좀비를 가까이에서 쏘는 방법에 의존해야 한다.

미로에는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 방이 있다. 인디아나는 $1$번 방에 있다. 나머지 각 방에는 처음에 좀비가 정확히 한 마리씩 있다. 방들은 양방향 통로로 연결되어 있다.

매 턴마다 살아 있는 모든 좀비는 자신이 있는 방에서 인디아나가 있는 방($1$번 방)까지의 최단 경로 위 다음 방으로 통로를 따라 한 칸 이동한다. 좀비가 있는 방에서 인디아나의 방으로 갈 수 없다면 그 좀비는 제자리에 머문다. 어떤 방에서 인디아나의 방으로 가는 최단 경로가 여러 개라면, 그 방의 좀비들은 입력에서 가장 먼저 등장한 통로를 택한다.

인디아나의 리볼버에는 총알 $K$발이 들어간다. 어떤 턴에 인디아나가 있는 방에 도착한 좀비가 최대 $K$마리라면 인디아나는 그들을 모두 쏴 죽인다. 그보다 많으면 인디아나는 잡아먹힌다.

인디아나가 무사히 탈출하는지 판정하고, 그렇지 못하다면 몇 번째 턴에 잡아먹히는지 구하여라.

첫 줄에는 테스트 집합의 개수를 나타내는 자연수 $Z$ ($1 \le Z \le 10$)가 주어진다. 이어지는 줄에서 각 테스트 집합이 차례로 주어진다.

각 테스트 집합의 첫 줄에는 공백으로 구분된 세 자연수 $N$, $M$, $K$ ($1 \le N, M, K \le 10^6$)가 주어진다. $N$은 방의 수, $M$은 통로의 수, $K$는 인디아나 리볼버의 장전 용량이다.

이어지는 $M$개의 줄에는 각 줄마다 통로 하나가 서로 다른 두 자연수 $A$, $B$ ($1 \le A, B \le N$)의 쌍으로 주어지며, 이는 방 $A$와 방 $B$를 잇는 양방향 통로가 존재함을 뜻한다. 임의의 두 방은 최대 하나의 통로로만 연결된다.

각 테스트 집합에 대해, 인디아나가 잡아먹히는 턴 번호(좀비는 $1$번 턴에 첫 이동을 한다)를 한 줄에 하나씩 출력한다. 인디아나가 살아남는다면 대신 hurray!를 출력한다.