WC '99 Suicidal P1 - World

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
Woburn Challenge 1999 - Suicidal

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 international 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 two 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 (i.e. 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. Up to 26 American cities and up to 26 European cities will be used in this game. American cities will be designated with lowercase letters while European cities with uppercase 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 Specification

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 lowercase 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, i.e. They can fly either way. The input set will terminate with -1 -1.

Output Specification

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.

Sample Input

1
3 3
a A
a B
b B
b C
c C
c A
-1 -1

Sample Output

Will

Comments

There are no comments at the moment.