P6560 [SBCOI2020] The Passage of Time

Time passes second by second, melting away together with the snow in this winter. Maybe, if time could stop at this moment, how wonderful that would be. ...... “Is this... my last winter in this town?” “Yeah. You can’t stay in this town for your whole life. The outside world is big, really big...” “Uh... the outside world... I’m suddenly looking forward to it!” “Someday, you will go very far, very far away. Later, don’t forget this town.” “I won’t. At least... this used to be my happiest memory! And you must not forget me either.” “Look, these snowflakes. Legend says: whenever there is a piece of longing in the world, it turns into a snowflake and falls here.” “Then... later you must find my snowflake...”  “Then, how about we create one last memory this winter, together?” “Sure. Let’s play a game...”

This game is played on a directed graph (not necessarily acyclic). Before each round starts, they first choose a start node and a target node on the graph, and place a token on the start node. Then the two players take turns moving the token. Each time, they may move the token to an adjacent node following the direction of the directed edge. If someone moves the token to the target node first, that person wins. Likewise, if someone cannot make a move, that person loses. They alternate moves. Determine whether they have a winning strategy. The answer is an integer `0`, `1`, or `-1`, where `1` means the first player has a winning strategy, `-1` means the second player has a winning strategy, and `0` means neither player has a winning strategy.

The $\text{1}$st line contains three integers $n,m,q$, meaning the graph has $n$ nodes and $m$ edges, and there are $q$ rounds of the game. The next $m$ lines each contain two numbers $u_i,v_i$, meaning there is a directed edge from $u_i$ to $v_i$. The next $q$ lines each contain two numbers $x,y$, meaning the start node and the target node for each round. The testdata guarantees that the start node and the target node are different.

For each round, output only one integer `0`, `1`, or `-1`, where `1` means the first player has a winning strategy, `-1` means the second player has a winning strategy, and `0` means neither player has a winning strategy.

#### Sample Explanation $#1$  To describe the meaning, suppose the two players are A (first player) and B. As shown, A moves first to $2$, B moves to $3$. Next, A may choose to move to $4$ or $6$. If A goes to $4$, then B can move to the target node next, so this is not a good choice. If A goes to $6$, then B can only go to $7$, and A can then move to the target node. Therefore, A has a winning strategy. #### Sample Explanation $#2$  As shown, when the start node is $1$ and the target node is $5$, A and B will move in turns along the cycle $1-2-3-1$. Because if anyone moves to $4$ first, then the next player can move to the target node. Therefore, neither player has a winning strategy. When the start node is $4$ and the target node is $3$, A first moves to $5$. B has no move to make, so B loses. #### Constraints For $10\%$ of the data, the graph is guaranteed to be a chain. For $50\%$ of the data, $1\leq n\leq 10^3$, $1\leq m\leq 2\times10^3$, $1\leq q\leq 10$. For $70\%$ of the data, $1\leq n\leq 10^5$, $1\leq m\leq 2\times10^5$, $1\leq q\leq 10$. For $100\%$ of the data, $1\leq n\leq 10^5$, $1\leq m\leq 5\times10^5$, $1\leq q\leq 500$. Translated by ChatGPT 5