A - 高橋王国と青木王国 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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 点が与えられる。

入力例1

3 5
1 2
1 2
1 2
2 3
2 3
3
1 2
2 3
1 3

出力例1

YES NO
NO YES
NO YES

複数本の道路が 2 つの街の間に存在することもあることに注意して下さい。

入力例2

3 5
3 2
3 2
3 2
2 1
2 1
3
1 2
2 3
1 3

出力例2

YES YES
YES YES
NO YES

高橋王国から青木王国への道路のみ撤去されることに気をつけて下さい。

入力例3

8 10
1 2
1 3
1 4
2 3
3 5
4 6
5 8
6 7
6 8
7 8
7
1 2
2 3
2 6
3 6
4 5
5 6
6 7

出力例3

YES NO
YES NO
NO YES
NO YES
YES YES
YES YES
YES NO