Problem Description

In the AtCoder Kingdom, there are $ N $ towns. The $ N $ towns are numbered from $ 1 $ to $ N $, and Takahashi lives in town $ 1 $, while Aoki lives in town $ N $.

The towns are connected by $ M $ one-way roads. Multiple roads can exist between two towns, and bidirectional movement is possible if there is one road in each direction between the towns.

There is a rumor that the AtCoder Kingdom will be divided into two countries: the Takahashi Kingdom and the Aoki Kingdom. The division will be done as follows:

• Some of the $ N $ towns will belong to the Takahashi Kingdom, and the rest will belong to the Aoki Kingdom.
• Town $ 1 $ must be in the Takahashi Kingdom, and town $ N $ must be in the Aoki Kingdom.
• All roads from the Takahashi Kingdom to the Aoki Kingdom will be removed. That is, all roads with a starting point in the Takahashi Kingdom and an ending point in the Aoki Kingdom will be removed.
• The division will be done such that the number of roads to be removed is minimized.

These conditions do not necessarily result in a unique division. Therefore, many citizens are concerned about how the country will be divided.

Your task is to create a program that answers questions from the citizens. Each question will provide two towns, and for each question, you need to determine whether there is a possibility that they belong to the same kingdom or different kingdoms.

Input Format

The input is given from the standard input in the following format:

$ 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 $

• The first line contains the number of towns $ N $ ($1\ ≦\ N\ ≦\ 5,000$) and the number of roads $ M $ ($1\ ≦\ M\ ≦\ 50,000$).
• The next $ M $ lines contain two integers $ a_i, b_i $ ($1≦a_i,\ b_i≦N$, $a_i\ ≠\ b_i$) separated by a space, representing road $ i $ starting from town $ a_i $ and ending at town $ b_i $.
• The $ M+1 $ line contains the number of questions $ Q $ ($ 1≦Q≦100,000 $).
• The next $ Q $ lines contain two integers $ c_j, d_j $ ($1\ ≦\ c_j,\ d_j\ ≦\ N$, $c_j\ ≠\ d_j$), representing the $ j $th question about towns $ c_j $ and $ d_j $.

Output Format

For each of the $ Q $ questions, output one line with two words separated by a space.

• The first word indicates whether there is a possibility that towns $ c_j $ and $ d_j $ belong to the same kingdom. Output YES if there is a possibility, otherwise NO.
• The second word indicates whether there is a possibility that towns $ c_j $ and $ d_j $ belong to different kingdoms. Output YES if there is a possibility, otherwise NO.

End each output with a newline.

Sample Input and Output

Sample Input #1

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

Sample Output #1

YES NO
NO YES
NO YES

Sample Input #2

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

Sample Output #2

YES YES
YES YES
NO YES

Sample Input #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

Sample Output #3

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

Notes/Hints

Partial Points

This problem has partial scoring:

• If you solve the dataset where $N\ ≦\ 100,\ M\ ≦\ 1,000,\ Q\ ≦\ 100$, you will get 20 points.
• If you solve the dataset without additional constraints, you will get an additional 80 points.

Sample Explanation 1

Note that multiple roads can exist between two towns.

Sample Explanation 2

Be aware that only roads from the Takahashi Kingdom to the Aoki Kingdom are removed.

见题面 Input 部分

见题面 Output 部分