Sum of games#2411
Given a directed graph, a standard game is played as follows: initially, a token is placed on one of the graph's vertices (referred to as the starting position). Two players take turns moving the token along the edges of the graph. The player who cannot make a move loses the game.
In game theory, more complex games are also considered. For example, the direct sum of two games on graphs. In such a game, a token is placed at a starting position on each graph. On each turn, a player may choose any token and move it along an edge of the corresponding graph. The player who cannot make a move loses.
Your task is to determine who will win with optimal play.
The first line contains the numbers N_1 and M_1—the number of vertices and edges in the first graph (1 \leq N_1, M_1 \leq 10000). The following M_1 lines each contain two numbers and (1 \leq x, y \leq N_1), describing a directed edge from to .
Then, the next M_2+1 lines describe the second graph in the same format.
After that, the input ends with a list of pairs of starting vertices. The first line gives the number (1 \leq T \leq 100000)—the number of pairs of starting vertices. The next lines each contain two numbers v_1 and v_2 (1 \leq v_1 \leq N_1, 1 \leq v_2 \leq N_2).
For each of the pairs of starting vertices, output a single line with first if the first player wins with optimal play, second if the second player wins, or draw if the game is a draw.
Example 1