Problembeskrivning

I JOI:s förenta stater finns det $N$ städer numrerade från $1$ till $N$, och $M$ vägar numrerade från $1$ till $M$. Väg $i$ ($1 \le i \le M$) förbinder stad $U_i$ och stad $V_i$ i båda riktningarna.

JOI:s förenta stater består av $K$ delstater numrerade från $1$ till $K$. Stad $j$ ($1 \le j \le N$) tillhör delstat $S_j$. Dessutom innehåller varje delstat minst $1$ stad.

Direktör K, industriminister i JOI:s förenta stater, planerar att genomföra $Q$ handelsaffärer framöver. Den $k$-te handelsaffären ($1 \le k \le Q$) går ut på att transportera specialprodukter från stad $A_k$ till stad $B_k$ via några vägar och städer. Dock samarbetar endast delstat $S_{A_k}$ och delstat $S_{B_k}$ (eller endast delstat $S_{A_k}$ då $S_{A_k} = S_{B_k}$) i denna handel, och om rutten passerar genom någon stad som inte tillhör dessa delstater kommer specialprodukterna att bli stulna.

Direktör K vill undersöka om det finns en transportrutt för att genomföra handeln utan att specialprodukterna blir stulna. Givet städernas och vägarnas placering samt information om delstaterna och handelsaffärerna, skriv ett program som för varje handelsaffär avgör om det är möjligt att leverera specialprodukterna säkert.

Begränsningar

• $2 \le N \le 400\,000$.
• $1 \le M \le 400\,000$.
• $1 \le K \le N$.
• $1 \le U_i < V_i \le N$ ($1 \le i \le M$).
• $(U_i, V_i) \neq (U_j, V_j)$ ($1 \le i < j \le M$).
• $1 \le S_j \le K$ ($1 \le j \le N$).
• För varje $l$ ($1 \le l \le K$) finns det ett $j$ ($1 \le j \le N$) sådant att $S_j = l$.
• $1 \le Q \le 400\,000$.
• $1 \le A_k \le N$ ($1 \le k \le Q$).
• $1 \le B_k \le N$ ($1 \le k \le Q$).
• $A_k \neq B_k$ ($1 \le k \le Q$).
• Alla indatavärden är heltal.

Deluppgifter

1. ($5$ poäng) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ poäng) Alla städer som tillhör delstat $l$ ($1 \le l \le K$) kan färdas mellan varandra genom att endast passera vägar och städer som tillhör delstat $l$.
3. ($42$ poäng) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ poäng) Inga ytterligare begränsningar.

Indata

Indata ges från standardindata i följande format:

N M K
U_1 V_1
U_2 V_2
:
U_M V_M
S_1 S_2 ... S_N
Q
A_1 B_1
A_2 B_2
:
A_Q B_Q

Utdata

Skriv ut $Q$ rader till standardutdata. På den $k$-te raden ($1 \le k \le Q$), skriv ut 1 om det är möjligt att leverera specialprodukterna i den $k$-te handelsaffären, och 0 om det är omöjligt.

Exempel 1

4 3 2
1 2
2 3
3 4
1 2 1 2
3
1 2
1 3
1 4

1
0
1

• Den $1$:a handelsaffären går ut på att transportera specialprodukter från stad $1$ till stad $2$ genom att endast passera städer som tillhör delstat $1$ eller delstat $2$. Transport längs stad $1$ → stad $2$ uppfyller villkoret, så vi skriver ut 1.
• Den $2$:a handelsaffären går ut på att transportera specialprodukter från stad $1$ till stad $3$ genom att endast passera städer som tillhör delstat $1$. Eftersom det inte finns någon transportrutt som uppfyller villkoret skriver vi ut 0.
• Den $3$:e handelsaffären går ut på att transportera specialprodukter från stad $1$ till stad $4$ genom att endast passera städer som tillhör delstat $1$ eller delstat $2$. Transport längs stad $1$ → stad $2$ → stad $3$ → stad $4$ uppfyller villkoret, så vi skriver ut 1.

Detta indataexempel uppfyller begränsningarna för deluppgifterna $1, 3, 4$.

Exempel 2

4 2 1
1 3
2 4
1 1 1 1
4
1 2
1 3
2 3
2 4

0
1
0
1

Detta indataexempel uppfyller begränsningarna för deluppgifterna $1, 3, 4$.

Exempel 3

6 5 3
1 2
3 4
5 6
1 4
3 5
1 1 2 2 3 3
4
1 4
1 5
3 6
4 3

1
0
1
1

Detta indataexempel uppfyller begränsningarna för alla deluppgifter.

Exempel 4

8 11 3
4 8
1 8
4 6
3 5
2 4
7 8
6 7
3 4
1 4
2 3
3 8
2 3 1 1 2 1 2 1
10
8 2
8 1
2 7
5 3
5 7
4 8
1 8
6 8
6 5
1 8

1
1
0
1
0
1
1
1
1
1

Detta indataexempel uppfyller begränsningarna för deluppgifterna $1, 3, 4$.