Friendship between two persons is usually mutual, but not always.</p>

If person A trusts person B, we have a directed edge A → B in the friendship graph G.

There may be a case that we have directed edge A → B in G but not directed edge B → A.

A person X wants to deliver a secret message to another person Y, either directly or via a chain of trusted friendships in G.

Can this secret message be successfully delivered?

Answer: 1 for a successful delivery, or 0 otherwise. There will be Q such queries with different X and Y in G.

입력 형식

The first section of the input is for the friendship graph G.</p>

The first line of input contains two integers in one line: V and E (1 ≤ V ≤ 2000; 0 ≤ E ≤ 100000). Then, we have a list of E lines that contains two integers: A and B that implies the existence of directed edge A → B in G.

Vertices are numbered from [0..V-1], i.e. 0 ≤ A, B < V.

The second section of the input is for the queries. The first and the second section of the input is separated by a blank line for clarity.

The query section starts with one line containing an integer Q (1 ≤ Q ≤ 200000).

Afterward, we have a list of Q lines that also contains two integers: X and Y (0 ≤ X, Y < V). Note that it is possible that X = Y.

출력 형식

For each query, simply output one line containing either "1" or "0" (without the quotes) according to the problem description above.</p>

Important Note: There is something interesting with this particular friendship graph G that you can probably use. In at least 99% of the Q queries, if a person X can send a secret message to another person Y, then Y can also send a secret message (that is, a reply) back to X.

예제 입력

7 9
0 1
1 0
1 3
3 1
1 2
2 4
4 5
5 6
6 4

10
0 1
1 0
0 2
3 2
2 0
2 2
2 6
4 5
5 6
6 4

예제 출력

1
1
1
1
0
1
1
1
1
1