somnoros

The cat Somnorilă is a very sleepy cat! While sleeping, he had a dream in which he and a mouse were in a labyrinth. What is special about this labyrinth is that all the paths between the rooms of the labyrinth can only be traversed in one direction, and during a walk through the labyrinth, he cannot pass through the same room twice. Moreover, only the cat knows the map of the labyrinth, as the mouse does not have the courage to move from his current room. Being a delicate cat, Somnorilă wants to know if, from the room he is currently in, he can reach the mouse's room, so he will know if his dream was a nightmare or a pleasant dream when he wakes up!

Formally, you are given a directed acyclic graph (DAG) with $N$ nodes and $M$ edges, and $Q$ questions of the form: can node $Y$ be accessed from node $X$?

Task

You need to answer all $Q$ questions from Somnorilă.

Input data

The first line contains the numbers $N$ and $M$, where $N$ represents the number of nodes in the graph, and $M$ the number of edges. The next $M$ lines contain two numbers $X$ and $Y$, indicating that there is an edge from node $X$ to node $Y$ in the graph. Line $M + 2$ contains the number $Q$, representing the number of questions. The next $Q$ lines each contain numbers $X$ and $Y$, representing a question.

Output data

The output will contain $Q$ lines, each having a number. Each line $i$ contains the answer to question $i$. Print $1$ if node $X_i$ can reach node $Y_i$, or $0$ otherwise.

Constraints and clarifications

• $1 \leq N \leq 50\ 000$
• $1 \leq M \leq 200\ 000$
• $1 \leq Q \leq 100\ 000$
• It is guaranteed that in an edge and in a query, node $X$ will be at a lower level than node $Y$.
• It is guaranteed that for each node on a level $X \ (X > 1)$, there will be at least one edge with a node on level $X - 1$, $(∀) \ X > 1$.
• For $28$ points, $1 \leq N, Q \leq 1\ 000$, the tests are NOT grouped.
• For the remaining $72$ points, the original constraints apply, and the tests are grouped into 4-5 tests per group.

Example

stdin

12 13
1 4
2 5
3 5
4 6
4 7
4 11
5 6
5 8
5 12
6 9
7 9
7 10
11 12
4
1 9
4 8
7 12
3 6

stdout

1
0
0
1

Explanation

• Node $9$ can be accessed from node $1$. (Example path: $1 → 4 → 6 → 9$)
• Node $8$ cannot be accessed from node $4$.
• Node $12$ cannot be accessed from node $7$.
• Node $6$ can be accessed from node $3$. (Example path: $3 → 5 → 6$)