Games on graph#2404
The opponent started with -.
I analyzed his architecture and gave up.
_______________________________________________
From the memoirs of the 20th world champion Fritz Rybkin
Upon arrival, Aaz immediately demanded to organize a meeting of bookmakers, at which he laid out his plan.
- The main task, - began Aaz in his speech to the bookmakers, - is to learn to use the achievements of progress. We plan to launch many new types of competitions, which—quite possibly—will result in the appearance of some games with rules not invented by us. Therefore, it is necessary to quickly determine how useful these rules can be for us.
- Can you explain, at least in general, how this will be done? - came a question from the audience.
- Here is an example of a problem, by solving which, we will be able to understand the whole class of such games. A directed graph for a two-player game and its initial position are given. Recall that, in a graph game, a player can move from the current position to any position connected by an edge from the current one. Players take turns; the player who cannot make a move loses. It is required to check whether it is true that, in any play of the game, the first player always wins.
The input file contains a description of one or more tests. The first line of each test contains the number of vertices and the number of edges (1 \leq V \leq 100000, 1 \leq E \leq 100000), as well as the number of the initial position (1 \leq a \leq V). This is followed by lines—each contains a description of an edge in the form u_i\ v_i (1 \leq u_i, v_i \leq V), meaning there is a directed edge from vertex u_i to vertex v_i. The file ends with three zeros. The total sum of for all tests does not exceed , and the number of tests in the file does not exceed .
Follow the example format as closely as possible—checking is done automatically.
Example 1