PEG Judge - WC99 - S

Woburn Challenge 1999 - Suicidal

Where in the world are Will and Ethan Hunt?

The IMF has expanded its budget to hire one more person and both Ethan and Will are trying out for the job. But the IMF is fairly cruel and so they are making them play each other in a simple game of internation intrigue-- the loser of the game doesn't get hired (and since the IMF "doesn't exist", we all know what happens to the loser, right?). The game is simple -- it involves a lot of intercontinental flying as a pair.

The airports that the 2 will be using are in Europe and North America. At each destination, Ethan and Will must alternately choose a new intercontinental destination to fly to (ie. if they're in America now, they have to fly to somewhere in Europe and vice versa). Obviously, they can only fly by one of the recognized flight routes originating in the city they're currently in. They can also never take the same flight route twice, nor can they land in the same airport twice. Like we said, they must alternate in choosing the next destination. The game starts when Ethan picks an airport to start at. The game ends when no more airports can be gotten to from where they are without retracing steps or visiting one twice. At that point, the winner of the game is the one who last chose an airport. Upto 26 American cities and upto 26 European cities will be used in this game American cities will be designated with small case letters while European cities with upper-case letters. You will be given the cities between which flights exist. Assuming Ethan picks the airport that they start at, your task is to determine whether Ethan has a winning strategy, Will has a winning strategy or whether neither has a winning strategy (meaning that it totally depends on what each does). Output "Ethan", "Will", "Neither" respectively

Input

Line 1: Number of input sets
Each input set will be of the following format:
A E (A is the # of American cities, E is the # of European cities. Assume that if there are 10 American cities, they are represented by the first 10 lower-case letters of the alphabet and similarly with the European cities)
The next set of lines will contain pairs of cities (American first, then European) indicating that a flight exists between those 2 cities in BOTH directions, ie. They can fly either way. The input set will terminate with -1 -1

Output

For each input set, you will output "Ethan", "Will" or "Neither" depending on who has the winning strategy. Remember that Ethan goes first by picking the starting city. Will goes next by picking where they fly to and so on.