AT_codefestival_2015_ex_a 高橋王国と青木王国

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-exhibition/tasks/codefestival_2015_ex_a AtCoder 王国には $ N $ 個の街があります。$ N $ 個の街には $ 1 $ から $ N $ までの番号がついており、街 $ 1 $ に高橋君が、街 $ N $ に青木君が住んでいます。 街の間は $ M $ 本の道路で結ばれています。各道路は一方通行ですが、複数本の道路が 2 つの街の間に存在することもあります。特に、順向きと逆向きの道路が 1 本ずつ存在することにより双方向に移動可能な場合もあります。 AtCoder 王国は高橋王国と青木王国の 2 つの国に分断されるという噂が流れています。分断は以下を満たすように行われるそうです。 - $ N $ 個の街のうちの一部が高橋王国に、残りが青木王国になります。 - 高橋王国には街 $ 1 $ が、青木王国には街 $ N $ が必ず含まれます。 - 高橋王国から青木王国への道路は全て撤去されます。すなわち、始点が高橋王国に、終点が青木王国に所属するような道路が全て撤去されます。 - 撤去する道路の本数が最小になるように分割を行います。 これらを満たす分割の方法は、必ずしも一意ではありません。従って、国民の多くは、国がどのように分断されるかについて心配しています。 そこで、あなたの仕事は、国民からの質問に回答するプログラムを作成することです。2 つの街が質問として与えられるので、それぞれの質問について、「それらが同じ国に所属することになる可能性はあるか」と「それらは違う国に所属することになる可能性はあるか」を回答するプログラムを作成して下さい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ : $ a_M $ $ b_M $ $ Q $ $ c_1 $ $ d_1 $ $ c_2 $ $ d_2 $ : $ c_Q $ $ d_Q $ - $ 1 $ 行目には、街の個数 $ N $ ($ 1\ ≦\ N\ ≦\ 5,000 $) と道の本数 $ M $ ($ 1\ ≦\ M\ ≦\ 50,000 $) が与えられる。 - $ 2 $ 行目からの $ M $ 行のうち $ i $ 行目には、$ i $ 番目の道を表す整数 $ a_i,b_i $ ($ 1≦a_i,\ b_i≦N $, $ a_i\ ≠\ b_i $) が空白区切りで与えられる。これは、道 $ i $ が街 $ a_i $ を出発し街 $ b_i $ へ到達するものであることを表す。 - $ M+1 $ 行目には、国民からの質問の個数を表す整数 $ Q $ ($ 1≦Q≦100,000 $) が与えられる。 - $ M+2 $ 行目からの $ Q $ 行のうち、$ j $ 行目には、$ j $ 番目の質問を表す整数 $ c_j,\ d_j $ ($ 1\ ≦\ c_j,\ d_j\ ≦\ N $, $ c_j\ ≠\ d_j $) が与えられる。これは、$ j $ 番目の質問が街 $ c_j $ と街 $ d_j $ に関するものであることを表す。

$ Q $ 個の質問について、回答を $ 1 $ 行ずつ出力せよ。 質問 $ j $ への回答は 2 つの語からなり、空白で区切って出力すること。 - 1 つめの語は、街 $ c_j $ と街 $ d_j $ が同じ国に所属することになる可能性はあるかを表す。同じ国に所属する可能性がある場合 YES、無い場合 NO と出力せよ。 - 2 つめの語は、街 $ c_j $ と街 $ d_j $ が違う国に所属することになる可能性はあるかを表す。違う国に所属する可能性がある場合 YES、無い場合 NO と出力せよ。 出力の末尾には改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 100,\ M\ ≦\ 1,000,\ Q\ ≦\ 100 $ を満たすデータセットに正解した場合は、20 点が与えられる。 - 追加の制約のないデータセットに正解した場合は、上記とは別に 80 点が与えられる。 ### Sample Explanation 1 複数本の道路が 2 つの街の間に存在することもあることに注意して下さい。 ### Sample Explanation 2 高橋王国から青木王国への道路のみ撤去されることに気をつけて下さい。