D - 旅行会社高橋君 Editorial

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

高橋君とあなたはTK国でHS会社という旅行会社を経営しています。 TK国は NN 個の頂点と MM 本の辺からなる連結な単純無向グラフです。各頂点にはそれぞれ 11 から NN の番号が振られています。

HS会社では、顧客ごとに旅行計画を立てて提供するサービスを行っています。 これまでは、旅行計画を温もりのある手作業で作成していました。 ですが突然の旅行ブームがTK国に訪れ、ナウでヤングな若者は皆旅行をするようになりました。もちろん会社は大忙し、とうとうコンピューターに頼ることにしました。

HS会社では、顧客から始点、中継点、終点という 33 つの頂点を与えられるので、始点から中継点を通り終点へと到着するような旅行計画を提供しています。 ただし、顧客が退屈しないように、同じ辺を複数回通るような旅行計画は提供しないようにしています。同じ頂点を複数回通る事に制限はありません。つまり旅行計画は、始点から中継点を通り終点に到着するトレイルです。

あなたはとりあえず、顧客ごとにそのような旅行計画は存在するのかどうかだけを判別するプログラムを書くことにしました。

入力

入力は以下の形式で標準入力から与えられる。

NN MM
X1X_1 Y1Y_1
X2X_2 Y2Y_2
:
XMX_M YMY_M
QQ
A1A_1 B1B_1 C1C_1
A2A_2 B2B_2 C2C_2
:
AQA_Q BQB_Q CQC_Q
  • 11 行目は 22 つの整数 N(3≦N≦100,000)N(3 ≦ N ≦ 100,000)、M(1≦M≦200,000)M(1 ≦ M ≦ 200,000) が空白区切りで与えられ、これはTK国の頂点数と辺数を表す。
  • 22 行目からの MM 行は辺の情報を表す。そのうち ii 行目には 22 つの整数 XiX_i、YiY_i が空白区切りで与えられ、これは ii 番目の辺が 頂点 Xi(1≦Xi≦N)X_i(1 ≦ X_i ≦ N) と頂点 Yi(1≦Yi≦N)Y_i(1 ≦ Y_i ≦ N) を結んでいることを表す。
  • 2+M2+M 行目には、 11 つの整数 Q(1≦Q≦100,000)Q(1 ≦ Q ≦ 100,000) が与えられる。これはプログラムに旅行計画が存在するかを判定させたい顧客が QQ 人いることを表す。
  • 3+M3+M 行目からの QQ 行は顧客の情報を表す。そのうち ii 行目は 33 つの整数 AiA_i、BiB_i、CiC_i が空白区切りで与えられ、これは ii 番目の顧客に与えられた始点、中継点、終点がそれぞれ頂点 Ai(1≦Ai≦N)A_i(1 ≦ A_i ≦ N)、頂点 Bi(1≦Bi≦N)B_i(1 ≦ B_i ≦ N)、頂点 Ci(1≦Ci≦N)C_i(1 ≦ C_i ≦ N) であることを表す。
  • TK国は連結なグラフである。
  • TK国は単純なグラフである、つまり多重辺や自己辺は存在しない。
  • AiA_i、BiB_i、CiC_i は互いに異なる。

出力

QQ 行出力せよ。そのうち ii 行目は ii 番目の顧客の旅行計画が存在するなら OK、存在しないならば NG である。出力は標準出力に行い、末尾に改行を入れること。

入力例1Copy

Copy
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

出力例1Copy

Copy
OK
NG
OK
OK

以下にこの入力でのTK国を図示する。

一例として、

  • 11 番目の顧客には 1−2−31 - 2 - 3
  • 33 番目の顧客には 2−3−5−4−32 - 3 - 5 - 4 - 3
  • 44 番目の顧客には 3−4−53 - 4 - 5

という旅行計画が提供できる。

また、 22 番目の顧客に提供できる旅行計画は存在しない。

入力例2Copy

Copy
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

出力例2Copy

Copy
NG
OK
OK
OK
OK
NG
NG
OK
NG
NG
NG

以下にこの入力でのTK国を図示する。

入力例3Copy

Copy
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

出力例3Copy

Copy
OK
OK
NG
OK
OK
NG
NG
OK
OK
OK

以下にこの入力でのTK国を図示する。

2025-04-05 (Sat)
19:16:51 +00:00