AT_arc039_d [ARC039D] 旅行会社高橋君

[problemUrl]: https://atcoder.jp/contests/arc039/tasks/arc039_d 高橋君とあなたは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` である。出力は標準出力に行い、末尾に改行を入れること。

### Sample Explanation 1 以下にこの入力でのTK国を図示する。 !\[\](http://arc039.contest.atcoder.jp/img/arc/039/vn240wsdnl23fn4zd0i/D\_sample1.png) 一例として、 - $ 1 $ 番目の顧客には $ 1\ -\ 2\ -\ 3 $ - $ 3 $ 番目の顧客には $ 2\ -\ 3\ -\ 5\ -\ 4\ -\ 3 $ - $ 4 $ 番目の顧客には $ 3\ -\ 4\ -\ 5 $ という旅行計画が提供できる。 また、 $ 2 $ 番目の顧客に提供できる旅行計画は存在しない。 ### Sample Explanation 2 以下にこの入力でのTK国を図示する。 !\[\](http://arc039.contest.atcoder.jp/img/arc/039/vn240wsdnl23fn4zd0i/D\_sample2.png) ### Sample Explanation 3 以下にこの入力でのTK国を図示する。 !\[\](http://arc039.contest.atcoder.jp/img/arc/039/vn240wsdnl23fn4zd0i/D\_sample3.png)