D - 旅行会社高橋君 Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

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

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

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

以下にこの入力での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

出力例2

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

出力例3

OK
OK
NG
OK
OK
NG
NG
OK
OK
OK

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