問題文
你和高桥在TK国家经营一家名为HS公司的旅行社。 TK 国家是 N 顶点和 M 由书边组成的连通简单无向图。每个顶点都有一个 它的编号为 1 它们的编号最大为 N 。
HS公司为每位客户提供旅行规划服务。 以前,旅行计划是通过手动方式、以温暖的方式创建的。 然而,突如其来的旅游热潮席卷了TK国,Now的年轻人纷纷开始旅游。当然,公司很忙,最后决定依靠电脑。
在 HS 公司中,客户指的是起点、中继点和终点。 3 由于给定了两个顶点,我们提供了一个从起点,经过中间点,到终点的旅行计划。 但是,我们尽量不提供多次经过同一区域的行程,以避免无聊。多次经过同一顶点没有限制。换句话说,旅行计划就是一条从起点出发,经过中间点,到达终点的路线。
您决定编写一个程序来简单地确定每个客户是否存在此类旅行计划。
入力
输入是按以下格式从标准输入给出的。
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 行是 2 整数 N(3 ≦ N ≦ 100,000)、M(1 ≦ M ≦ 200,000) 作为空格分隔符给出,它表示 TK 国家的顶点和边的数量。 来自行
- 2 从线 M 线表示边缘信息。这几天之一 i 行中, 2 整数 X_i、Y_i 以空格分隔,即 i 第一条边是顶点 X_i(1 ≦ X_i ≦ N) 和顶点 Y_i(1 ≦ Y_i ≦ N) 已连接。 给出了
- 2+M 行中, 1 整数 Q(1 ≦ Q ≦ 100,000) 。这是因为客户希望程序确定旅行计划是否存在 Q 表示有人。
- 3+M 从线 Q 行代表客户信息。这几天之一 提供给第 i 行是 3 整数 A_i、B_i、C_i 以空格分隔,即 i 个客户的起点、中继点和终点是顶点。 A_i(1 ≦ A_i ≦ N)、頂点 B_i(1 ≦ B_i ≦ N)、頂点 C_i(1 ≦ C_i ≦ 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
出力例1
OK NG OK OK
具有此输入的传统知识国家如下图所示。

例如, 对于第
- 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
出力例2
NG OK OK OK OK NG NG OK NG NG NG
具有此输入的传统知识国家如下图所示。

入力例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
出力例3
OK OK NG OK OK NG NG OK OK OK
具有此输入的传统知识国家如下图所示。
