John and David just studied the topic of "Dynamic Connectivity in Graphs". They decided to play a game based on it with an undirected connected graph. There is atmost one edge between any two vertices and there are no self loops. Before the game two vertices a and b are selected. John's current vertex x is a. Both take alternate turns starting from John. The game is then played as follows:

(1) John changes his current vertex from x to any of the neighbour of x. If he can't make this move he loses the game.

(2) David removes exactly one edge from the graph.

(3) If John's current vertex $x = b$, then he wins the game. Repeat the procedure again from (1).

This game is played q times. For each game a and b are given, your task is to find the winner. Assume that both John and David play optimally.

Input Format :

First line contains two integers n - number of vertices in graph and m - number of edges in graph. Next m line contains two integers u and v denoting an edge between u and v. Next line contains integer q - number of games to be played. Next q line contains integer a and b as mentioned above.

Output Format :

For each game print the name of winner.

Input Constraints :

• $1 <= n <= 10^5$

• $1 <= m <= min((n*(n-1))/2, 2 * 10^5)$

• $1 <= u, v <= n$

• $1 <= q <= 10^5$

• $1 <= a, b <= n$

Setter : Tanmay Patel