Sum of games#3718
Let a directed graph be given. The standard game on a graph is as follows: at first, a token is placed on one of the graph's vertices (the so-called starting position). Two players take turns moving the token along the edges. The player unable to make a move loses.
In game theory, more complicated games are often considered. For example, the direct sum of two games on graphs. The direct sum of games is the following game: initially, there is a token on the starting position of each graph. On a turn, a player chooses any token and moves it along an edge of its 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).
The next M_2 + 1 lines describe the second graph in the same format.
The input file ends with a list of pairs of starting vertices for which you need to solve the problem. The first of these lines contains the number (1 \leq T \leq 100000)—the number of starting vertex pairs. The next lines contain pairs of vertices 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 line first if the first player wins with optimal play, second if the second player wins, or draw if it ends in a draw.
Example 1