somnoros

Motanul Somnorilă este un motan foarte somnoros! Cât timp dormea, el a avut un vis, în care el se afla împreună cu un șoricel într-un labirint. Ce este special la acest labirint este că toate drumurile între camere labirintului pot fi parcurse doar într-un sens, iar într-o plimbare prin labirint el nu are cum să treacă de două ori prin aceeași cameră. Mai mult, doar motanul știe harta labirintului, șoricelul neavând curajul să se mute din camera lui curentă. Fiind un motan delicat, Somnorilă vrea să știe dacă din camera în care se află el momentan poate ajunge în camera șoricelului, ca să știe după ce se trezește dacă visul lui a fost un coșmar sau un vis!

Formal, vi se dă un graf orientat aciclic (DAG) cu $N$ noduri și $M$ muchii, și $Q$ întrebări de forma: poate fi accesat nodul $Y$ din nodul $X$?

Cerință

Trebuie să răspundeți la toate cele $Q$ întrebări ale lui Somnorilă.

Date de intrare

Pe prima linie se vor găsi numerele $N$ și $M$, unde $N$ reprezintă numărul de noduri ale grafului, iar $M$ numărul de muchii. Pe următoarele $M$ rânduri, se vor găsi câte două numere $X$ și $Y$, care semnifică că în graf există muchie de la nodul $X$ la nodul $Y$. Pe linia $M + 2$ se va afla numărul $Q$, care reprezintă numărul de întrebări. Pe următoarele $Q$ rânduri se vor afla numerele $X$ și $Y$, care reprezintă o întrebare.

Date de ieșire

Răspunsul pentru fiecare întrebare va fi afișat pe câte o linie, în forma următoare: pe linia $i$ se va afișa răspunsul la a $i$-a întrebare. Se va afișa $1$, dacă din nodul $X_i$ se poate ajunge în nodul $Y_i$, sau $0$ în caz contrar.

Restricții și precizări

• $1 \leq N \leq 50 \ 000$
• $1 \leq M \leq 200 \ 000$
• $1 \leq Q \leq 100 \ 000$
• Se garantează că într-o muchie și într-un query nodul $X$ se va afla pe un nivel mai mic față de nodul $Y$.
• Se garantează că pentru fiecare nod de pe un nivel $X \ (X > 1)$ va exista cel puțin o muchie cu un nod de pe nivelul $X - 1$, $(∀) \ X > 1$.
• Pentru $28$ de puncte, $1 \leq N, Q \leq 1 \ 000$, testele NU sunt grupate.
• Pentru alte $72$ de puncte se aplică restricțiile originale, iar testele sunt grupate câte $4 - 5$ teste / grupă.

Exemplu

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

Explicație

• Nodul $9$ poate fi accesat din nodul $1$. (Exemplu de drum: $1 → 4 → 6 → 9$)
• Nodul $8$ nu poate fi accesat din nodul $4$.
• Nodul $12$ nu poate fi accesat din nodul $7$.
• Nodul $6$ poate fi accesat din nodul $3$. (Exemplu de drum: $3 → 5 → 6$)