← 返回题目列表

AtCoder · arc039_d

D. 旅行社高桥君

中文机器翻译题面 查看原题

問題文

你和高桥在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

具有此输入的传统知识国家如下图所示。