Testo del problema

Negli Stati Uniti di JOI ci sono $N$ città numerate da $1$ a $N$, e $M$ strade numerate da $1$ a $M$. La strada $i$ ($1 \le i \le M$) collega in entrambe le direzioni la città $U_i$ e la città $V_i$.

Gli Stati Uniti di JOI sono divisi in $K$ stati numerati da $1$ a $K$. La città $j$ ($1 \le j \le N$) appartiene allo stato $S_j$. Inoltre, ogni stato contiene almeno $1$ città.

Il direttore K, Ministro dell'Industria degli Stati Uniti di JOI, ha in programma di effettuare $Q$ scambi commerciali d'ora in avanti. Il $k$-esimo scambio ($1 \le k \le Q$) consiste nel trasportare prodotti tipici dalla città $A_k$ alla città $B_k$ passando attraverso alcune strade e città. Tuttavia, solo lo stato $S_{A_k}$ e lo stato $S_{B_k}$ (o solo lo stato $S_{A_k}$ quando $S_{A_k} = S_{B_k}$) collaborano a questo scambio, e se il percorso passa per una qualsiasi città che non appartiene a questi stati, i prodotti tipici verranno rubati.

Il direttore K vuole verificare se esiste un percorso di trasporto per effettuare lo scambio senza che i prodotti tipici vengano rubati. Data la disposizione delle città e delle strade, e le informazioni sugli stati e sugli scambi, scrivi un programma per determinare per ciascuno scambio se è possibile consegnare in sicurezza i prodotti tipici.

Vincoli

• $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$).
• Per ogni $l$ ($1 \le l \le K$), esiste $j$ ($1 \le j \le N$) tale che $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$).
• Tutti i valori in input sono numeri interi.

Sottoproblemi

1. ($5$ punti) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ punti) Tutte le città appartenenti allo stato $l$ ($1 \le l \le K$) possono comunicare tra loro passando esclusivamente attraverso strade e città appartenenti allo stato $l$.
3. ($42$ punti) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ punti) Nessun vincolo aggiuntivo.

Input

L'input è fornito dallo Standard Input nel seguente formato:

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

Output

Sullo Standard Output, stampa $Q$ righe. Sulla $k$-esima riga ($1 \le k \le Q$), stampa 1 se è possibile consegnare i prodotti tipici nel $k$-esimo scambio, e 0 se è impossibile.

Esempio 1

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

1
0
1

• Il $1$° scambio consiste nel trasportare prodotti tipici dalla città $1$ alla città $2$ passando solo per città appartenenti allo stato $1$ o allo stato $2$. Il trasporto lungo città $1$ → città $2$ soddisfa la condizione, quindi si stampa 1.
• Il $2$° scambio consiste nel trasportare prodotti tipici dalla città $1$ alla città $3$ passando solo per città appartenenti allo stato $1$. Poiché non esiste alcun percorso di trasporto che soddisfi la condizione, si stampa 0.
• Il $3$° scambio consiste nel trasportare prodotti tipici dalla città $1$ alla città $4$ passando solo per città appartenenti allo stato $1$ o allo stato $2$. Il trasporto lungo città $1$ → città $2$ → città $3$ → città $4$ soddisfa la condizione, quindi si stampa 1.

Questo input di esempio soddisfa i vincoli dei Sottoproblemi $1, 3, 4$.

Esempio 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

Questo input di esempio soddisfa i vincoli dei Sottoproblemi $1, 3, 4$.

Esempio 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

Questo input di esempio soddisfa i vincoli di tutti i sottoproblemi.

Esempio 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

Questo input di esempio soddisfa i vincoli dei Sottoproblemi $1, 3, 4$.