There are several airports in one country, and there are flights between some of them. One can fly from any airport to any other, probably with some changes. For any pair of airports there exists only one sequence of flights that connects them.
Two terrorists play a game. They make moves in turn. Each move consists of the following operations. A player mines an airport, chooses a flight and flies away together with his colleague. After the take-off he actuates a radio-controlled fuse. As a result the airport that the terrorists have just left is destroyed, and all the flights to and from this airport are no longer possible. After the aircraft lands the other player makes his move, and so forth. One loses if one cannot make a move.
Given an initial list of flights and the number of an airport where the terrorists are at the start of the game, write a program which would determine who wins if the terrorists play a perfect game (each chooses the best move).