Sum of games
Given a directed graph, consider the following standard game: a token is initially placed on one of the graph's vertices (known as the starting position). Two players take turns moving the token along the edges. The player who cannot make a move loses the game.
In game theory, more complex scenarios are often analyzed, such as the direct sum of two games on graphs. The direct sum of games is defined as follows: initially, a token is placed at the starting position on each graph. During their turn, a player selects any token and moves it along an edge of the corresponding graph. The player who cannot make a move loses.
Your task is to determine the winner with optimal play.
Input
The first line contains the integers N_1 and M_1—representing the number of vertices and edges in the first graph (1 ≤ N_1, M_1 ≤ 10000). The next M_1 lines each contain two integers x and y (1 ≤ x, y ≤ N_1), indicating a directed edge from vertex x to vertex y.
Following this, the second graph is defined in the same format over the next M_2+1 lines.
The input concludes with a list of pairs of starting vertices for which the problem needs to be solved. The first line of this section specifies the integer T (1 ≤ T ≤ 100000)—the number of pairs of starting vertices. The subsequent T lines each specify a pair of vertices v_1 and v_2 (1 ≤ v_1 ≤ N_1, 1 ≤ v_2 ≤ N_2).
Output
For each of the T pairs of starting vertices, output a line with first if the first player wins with optimal play, second if the second player wins, or draw if the game results in a draw.