Problem Description

Takahashi and you are running a travel agency called HS Company in TK country. TK country is a connected simple undirected graph consisting of $N$ vertices and $M$ edges. Each vertex is numbered from $1$ to $N$.

HS Company provides a service where they create and offer travel plans for each customer. Previously, travel plans were created manually with a warm touch. However, a sudden travel boom has hit TK country, and all the cool and young people are now traveling. Of course, the company is very busy, so they decided to rely on computers.

HS Company receives three vertices from the customer: starting point, waypoint, and endpoint. They provide a travel plan that starts from the starting point, passes through the waypoint, and arrives at the endpoint. However, to keep the customers from getting bored, they do not provide travel plans that involve passing through the same edge multiple times. There is no restriction on passing through the same vertex multiple times. In other words, the travel plan is a trail that starts from the starting point, passes through the waypoint, and arrives at the endpoint.

You decided to write a program that determines whether such a travel plan exists for each customer.

Input Format

The input is given from the standard input in the following format:

$N$ $M$ $X_1$ $Y_1$ $X_2$ $Y_2$ : $X_M$ $Y_M$ $Q$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ : $A_Q$ $B_Q$ $C_Q$

• The first line contains two integers $N(3 ≦ N ≦ 100,000)$ and $M(1 ≦ M ≦ 200,000)$, representing the number of vertices and edges in TK country, respectively.
• The next $M$ lines contain edge information. The $i$-th line contains two integers $X_i$ and $Y_i$, representing that the $i$-th edge connects vertex $X_i(1 ≦ X_i ≦ N)$ and vertex $Y_i(1 ≦ Y_i ≦ N)$.
• The $(2+M)$-th line contains one integer $Q(1 ≦ Q ≦ 100,000)$, representing that there are $Q$ customers for whom you want to determine if a travel plan exists.
• The next $Q$ lines contain customer information. The $i$-th line contains three integers $A_i$, $B_i$, and $C_i$, representing that the starting point, waypoint, and endpoint given to the $i$-th customer are vertices $A_i(1 ≦ A_i ≦ N)$, $B_i(1 ≦ B_i ≦ N)$, and $C_i(1 ≦ C_i ≦ N)$, respectively.
• TK country is a connected graph.
• TK country is a simple graph, meaning there are no multiple edges or self-loops.
• $A_i$, $B_i$, and $C_i$ are distinct.

Output Format

Output $Q$ lines. The $i$-th line should be OK if a travel plan exists for the $i$-th customer, and NG if it does not. The output should be to the standard output, with a newline at the end.

Sample Input and Output

Sample Input #1

5 5
1 2
2 3
3 4
4 5
5 3
4
1 2 3
1 3 2
2 4 3
3 4 5

Sample Output #1

OK
NG
OK
OK

Sample Input #2

7 7
4 7
1 7
2 6
2 4
3 4
3 5
3 7
11
3 5 6
6 4 7
5 7 3
4 7 2
4 3 6
2 7 6
1 2 4
2 7 3
7 1 4
3 2 5
2 6 7

Sample Output #2

NG
OK
OK
OK
OK
NG
NG
OK
NG
NG
NG

Sample Input #3

7 8
2 5
5 4
4 2
2 1
1 6
6 3
3 7
7 6
10
3 6 2
1 4 5
1 5 6
6 2 4
5 2 6
3 1 7
7 2 6
5 4 2
6 7 5
2 5 1

Sample Output #3

OK
OK
NG
OK
OK
NG
NG
OK
OK
OK

Notes/Hints

Sample Explanation 1

Here is a diagram of TK country for this input. As an example:
- For the 1st customer, a travel plan could be $1 - 2 - 3$.
- For the 3rd customer, a travel plan could be $2 - 3 - 5 - 4 - 3$.
- For the 4th customer, a travel plan could be $3 - 4 - 5$.

No travel plan exists for the 2nd customer.

Sample Explanation 2

Here is a diagram of TK country for this input.

Sample Explanation 3

Here is a diagram of TK country for this input.

见题面 Input 部分

见题面 Output 部分