问题描述

AtCoder王国有$N$个城市。每个城市从1到$N$编号，高桥君住在第1个城市，青木君住在第N个城市。

这些城市之间由$M$条道路连接。每条道路都是单向的，但两个城市之间可能存在多条道路。特别地，如果一条道路的正方向和反方向各有一条道路，那么可以双向移动。

有传言说，AtCoder国被分割成高桥王国和青木王国。据说分割是根据以下条件进行的：

• $N$个城市中的一部分属于高桥王国，其余城市属于青木王国。
• 高桥王国必须包含城市1，青木王国必须包含城市N。
• 从高桥王国到青木王国的道路将全部撤销。也就是说，所有道路的起点都属于高桥王国，终点都属于青木王国。
• 分割的目标是删除最少数量的道路。

满足上述条件的分割方法并不唯一。因此，许多人担心国家将如何被分割。

因此，您的任务是创建一个程序来回答公民的问题。每个问题都会给出两个城市作为问题，对于每个问题，请编写一个程序来回答它们是否有可能属于同一个国家以及是否有可能属于不同的国家。

输入

输入通过标准输入给出，具体格式如下。

$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 \leq N \leq 5,000$)和道路数量$M$ ($1 \leq M \leq 50,000$)。
• 第2到第$M+1$行中，第$i$行包含表示第$i$条道路的两个整数$a_i,b_i$ ($1 \leq a_i, b_i \leq N$, $a_i \neq b_i$)。表示道路$i$从城市$a_i$到达城市$b_i$。
• 第$M+2$行包含整数$Q$ ($1 \leq Q \leq 100,000$)，表示公民提出的问题数量。
• 第$M+3$行到第$M+2+Q$行中，第$j$行包含表示第$j$个问题的两个整数$c_j, d_j$ ($1 \leq c_j, d_j \leq N$, $c_j \neq d_j$)。表示第$j$个问题涉及城市$c_j$和城市$d_j$。

输出

对于每个问题，输出一行答案。对于第$j$个问题，回答由两个词组成，用空格分隔。

• 第一个词表示城市$c_j$和城市$d_j$可能属于同一个国家。如果可能属于同一个国家，则输出YES；否则，输出NO。
• 第二个词表示城市$c_j$和城市$d_j$可能属于不同的国家。如果可能属于不同的国家，则输出YES；否则，输出NO。

输出末尾要有换行符。

部分得分

本问题设有部分得分。

• 如果能够正确解答满足$N \leq 100, M \leq 1,000, Q \leq 100$的数据集，则可获得20分。
• 如果能够正确解答附加约束条件下的数据集，则除了上述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

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