Description

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.

Input Format

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.

Output Format

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.

7 7 1
1 2
2 3
3 4
4 5
3 6
7 5
6 7
1 5

1

5 5 2
1 2
2 3
3 1
3 4
4 5
1 5
4 3

0
1

Hint

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