Sum of games
Given a directed graph, consider the following standard game: a token is initially placed on one of the graph's vertices (the starting position). Two players alternate turns, moving the token along the edges. The player who cannot make a move loses.
In game theory, more complex games are often analyzed, such as the direct sum of two games on graphs. The direct sum game involves placing a token at the starting position on each graph. On their turn, a player selects any token and moves it along an edge of the respective graph. The player who cannot make a move loses.
Your task is to determine the winner with perfect play.
Input
The first line contains the numbers N_1 and M_1 — the number of vertices and edges in the first graph (1 ≤ N_1, M_1 ≤ 10000). The following M_1 lines each contain two numbers x and y (1 ≤ x, y ≤ N_1), representing an edge from vertex x to vertex y.
The next M_2+1 lines describe the second graph in the same format.
The input concludes with a list of pairs of starting vertices for which the problem needs to be solved. The first line contains the number T (1 ≤ T ≤ 100000) — the number of pairs of starting vertices. The next 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 perfect play, "second" if the second player wins, or "draw" if the game ends in a draw.