The product of graphs#1750
Given a directed acyclic graph. A standard game on the graph is as follows: initially, a token is placed on one of the vertices of the graph (called the starting position). Two players take turns moving the token along the edges. The player who cannot make a move loses.
In game theory, more complex games are often considered. For example, the direct product of two games on graphs. The direct product game is defined as follows: initially, each graph has a token placed on its own starting position. On each turn, a player moves both tokens along the edges (each token is moved within its respective graph). A player who cannot make a move loses — that is, the player who cannot move in at least one of the games loses.
Your task is to determine who wins under optimal play.
The first line contains integers N_1 and M_1 — the number of vertices and edges in the first graph (1 \leq N_1, M_1 \leq 100000). Each of the next M_1 lines contains two integers and (1 \leq x, y \leq N_1).
The next M_2 + 1 lines describe the second graph in the same format.
The input ends with a list of starting vertex pairs. The first of these lines contains (1 \leq T \leq 100000) — the number of starting vertex pairs. Each of the next lines contains a pair 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 under optimal play, and "second" otherwise.
Example 1