Games on graph
The enemy began to e2-e4.
I have reviewed it and gave up architecture
_______________________________________________
From the memoirs of the 20th world champion Fritz Rybkin
Upon arrival, immediately demanded Aahz organize a meeting of the bookmakers, in which he outlined his plan.
- The main task - Aahz began his presentation to the bookies - learn to use to make progress. We plan to launch many new forms of competition that - quite possibly - lead to the fact that there will be some play by the rules, invented not by us. So, you must be able to quickly figure out how these rules may be useful to us.
- Is it possible at least in general to explain how this is done? - Followed by a question from the audience.
- Here is an example of the problem and decided that we will be able to deal with the whole class games. Dan directed graph of a game for two players and the starting position in it. Recall that in the game on a graph the player can walk out of position to any position in which there is an edge from the current one. Players take turns, plays someone who can not make a move. Required to check whether it is true that in any game party always wins the first player.
Input
The input file contains a description of one or more tests. The first line of each test set of vertices V and the number of edges E (1 ≤ V ≤ 100000, 1 ≤ E ≤ 100000), as well as the number of the initial position a (1 ≤ a ≤ V). This is followed by E string - description of edges in the form u_i v_i (1 ≤ u_i, v_i ≤ V), which means that the edge directed from vertex u_i to vertex v_i. File ends with three zeros. The sum of all E for all tests does not exceed 100000, the number of tests in the file does not exceed 1000.
Output
Follow the example format as closely as possible - checking is done automatically.