Indiana Jones Among the Zombies

Indiana Jones has finished his search for the Amulet of Body and Mind Control with mixed fortune. The good news is that he found the amulet. The bad news is that the labyrinth he is trapped in is full of zombies, and the amulet he planned to use against them does not work. Indiana has to fall back on the old way of fighting the undead: shooting them at close range with a Smith and Wesson revolver.

The labyrinth has $N$ chambers numbered from $1$ to $N$. Indiana is in chamber $1$. Each of the other chambers initially holds exactly one zombie. Chambers are connected by two-way corridors.

Every turn, each surviving zombie moves one step along a corridor to the next chamber on a shortest path from its current chamber to Indiana's chamber (chamber $1$). If no path leads from a zombie's chamber to Indiana's chamber, that zombie stays where it is. If a chamber has several shortest paths toward Indiana's chamber, the zombies there take the corridor that appears first in the input.

Indiana's revolver holds $K$ bullets. If at most $K$ zombies arrive in Indiana's chamber during a turn, he shoots them all. Otherwise he is eaten.

Determine whether Indiana escapes unharmed, and if not, find the turn in which he is eaten.

The first line contains one natural number $Z$ ($1 \le Z \le 10$), the number of test sets. The test sets follow.

The first line of each test set contains three space-separated natural numbers $N$, $M$, and $K$ ($1 \le N, M, K \le 10^6$): $N$ is the number of chambers, $M$ the number of corridors, and $K$ the capacity of Indiana's revolver.

Each of the next $M$ lines describes one corridor as a pair of distinct natural numbers $A$ and $B$ ($1 \le A, B \le N$), meaning a two-way corridor connects chambers $A$ and $B$. Every pair of chambers is joined by at most one corridor.

For each test set, print on its own line the turn in which Indiana is eaten (the zombies make their first move on turn $1$), or the word hurray! if Indiana survives.