问题描述

高桥君和你在TK国经营一家名为HS公司的旅行社。TK国是一个由N个顶点和M条边组成的连通简单无向图。每个顶点都被标上从1到N的编号。

HS公司为每个客户提供制定旅行计划并提供旅行服务。过去，我们一直使用手工制作温馨的旅行计划。但是突然之间，旅行热潮来袭，年轻人都开始旅行。公司非常忙碌，最终决定依赖计算机来进行工作。

HS公司会根据客户的要求提供旅行计划，包括起点、中间点和终点，确保从起点经过中间点最后到达终点。为了避免客户感到无聊，我们不提供经过同一条边多次的旅行计划。但是，可以经过同一个顶点多次。也就是说，旅行计划是从起点经过中间点最后到达终点的路径。

你需要编写一个程序，判断对于每个客户是否存在这样的旅行计划。

---

输入

输入从标准输入读取，具体格式如下：

$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$

• 第1行包含两个整数，$N(3 \leq N \leq 100,000)$ 和 $M(1 \leq M \leq 200,000)$，表示TK国的顶点数和边数。
• 接下来的M行包含边的信息。其中第i行包含两个整数 $X_i$ 和 $Y_i$，以空格分隔，表示第i条边连接顶点$X_i (1 \leq X_i \leq N)$和顶点$Y_i (1 \leq Y_i \leq N)$。
• 第M+2行包含一个整数 $Q(1 \leq Q \leq 100,000)$，表示需要判断旅行计划是否存在的客户数量。
• 接下来的Q行包含客户的信息。其中第i行包含三个整数 $A_i$, $B_i$, $C_i$，以空格分隔，表示第i个顾客的起点、中间点和终点分别为顶点 $A_i (1 \leq A_i \leq N)$、顶点 $B_i (1 \leq B_i \leq N)$、顶点 $C_i (1 \leq C_i \leq N)$。
• TK国是一个连通图。
• TK国是一个简单图，即不存在重复边或自环。
• $A_i$, $B_i$ 和 $C_i$ 两两不相等。

输出

输出Q行。其中第i行表示第i个顾客的旅行计划是否存在，如果存在则输出OK，否则输出NG。输出结果以换行符结尾。

---

示例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

输出

OK
NG
OK
OK

以下是TK国的示意图：

例如，

• 对于第1个顾客，可以提供旅行计划 $1 - 2 - 3$
• 对于第3个顾客，可以提供旅行计划 $2 - 3 - 5 - 4 - 3$
• 对于第4个顾客，可以提供旅行计划 $3 - 4 - 5$

但是对于第2个顾客，无法提供旅行计划。

---

示例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

输出

NG
OK
OK
OK
OK
NG
NG
OK
NG
NG
NG

以下是TK国的示意图：

---

示例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

输出

OK
OK
NG
OK
OK
NG
NG
OK
OK
OK

以下是TK国的示意图：