AT_arc039_d.[ARC039D] 旅行会社高橋君

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

HS 公司为每位客户制定旅行计划并提供服务。此前，旅行计划都是手工精心制作的。然而，TK 国突然迎来了旅游热潮，所有时尚的年轻人都开始旅行。公司变得异常繁忙，最终不得不依赖计算机。

在 HS 公司，客户会指定起点、中转点和终点这三个顶点，公司需要提供一条从起点出发，经过中转点，最终到达终点的旅行计划。为了避免客户感到无聊，旅行计划不能重复经过同一条边，但可以多次经过同一个顶点。也就是说，旅行计划是一条从起点经过中转点到终点的“迹”（trail）。

你现在的任务是，编写一个程序，仅判断对于每位客户，是否存在这样的旅行计划。

输入以如下格式从标准输入读入。

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

• 第 $1$ 行包含两个整数 $N\ (3 \leq N \leq 100,000)$、$M\ (1 \leq M \leq 200,000)$，表示 TK 国的顶点数和边数。
• 接下来的 $M$ 行，每行包含两个整数 $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$ 行，每行包含三个整数 $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$ 位客户，如果存在满足条件的旅行计划，则输出 OK，否则输出 NG。输出需写到标准输出，每行末尾需换行。

样例解释 1

下图展示了该输入下的 TK 国。

例如，

• 对于第 $1$ 位客户，可以提供 $1-2-3$ 这样的旅行计划；
• 对于第 $3$ 位客户，可以提供 $2-3-5-4-3$ 这样的旅行计划；
• 对于第 $4$ 位客户，可以提供 $3-4-5$ 这样的旅行计划。
  而对于第 $2$ 位客户，无法提供满足条件的旅行计划。

样例解释 2

下图展示了该输入下的 TK 国。

样例解释 3

下图展示了该输入下的 TK 国。

由 ChatGPT 4.1 翻译