Enunciado del problema

En los Estados Unidos de JOI hay $N$ ciudades numeradas del $1$ al $N$, y $M$ carreteras numeradas del $1$ al $M$. La carretera $i$ ($1 \le i \le M$) conecta bidireccionalmente la ciudad $U_i$ y la ciudad $V_i$.

Los Estados Unidos de JOI constan de $K$ estados numerados del $1$ al $K$. La ciudad $j$ ($1 \le j \le N$) pertenece al estado $S_j$. Además, cada estado contiene al menos $1$ ciudad.

El director K, ministro de Industria de los Estados Unidos de JOI, planea realizar $Q$ intercambios comerciales a partir de ahora. El $k$-ésimo intercambio ($1 \le k \le Q$) consiste en transportar productos especiales desde la ciudad $A_k$ hasta la ciudad $B_k$ pasando por algunas carreteras y ciudades. Sin embargo, solo el estado $S_{A_k}$ y el estado $S_{B_k}$ (o solo el estado $S_{A_k}$ cuando $S_{A_k} = S_{B_k}$) cooperan en este intercambio, y si la ruta pasa por cualquier ciudad que no pertenezca a estos estados, los productos especiales serán robados.

El director K quiere investigar si existe una ruta de transporte para realizar el intercambio sin que roben los productos especiales. Dada la disposición de las ciudades y carreteras, y la información sobre los estados y los intercambios, escribe un programa para determinar en cada intercambio si es posible entregar de forma segura los productos especiales.

Restricciones

• $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$).
• Para todo $l$ ($1 \le l \le K$), existe $j$ ($1 \le j \le N$) tal que $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$).
• Todos los valores de entrada son números enteros.

Subtareas

1. ($5$ puntos) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ puntos) Todas las ciudades que pertenecen al estado $l$ ($1 \le l \le K$) pueden viajar entre sí pasando únicamente por carreteras y ciudades que pertenecen al estado $l$.
3. ($42$ puntos) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ puntos) Sin restricciones adicionales.

Entrada

La entrada se proporciona desde la Entrada Estándar en el siguiente 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

Salida

En la Salida Estándar, imprime $Q$ líneas. En la $k$-ésima línea ($1 \le k \le Q$), imprime 1 si es posible entregar los productos especiales en el $k$-ésimo intercambio, y 0 si es imposible.

Ejemplo 1

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

1
0
1

• El $1$-er intercambio consiste en transportar productos especiales de la ciudad $1$ a la ciudad $2$ pasando únicamente por ciudades que pertenecen al estado $1$ o al estado $2$. Transportar a lo largo de ciudad $1$ → ciudad $2$ cumple la condición, por lo que se imprime 1.
• El $2$-do intercambio consiste en transportar productos especiales de la ciudad $1$ a la ciudad $3$ pasando únicamente por ciudades que pertenecen al estado $1$. Como no existe ninguna ruta de transporte que cumpla la condición, se imprime 0.
• El $3$-er intercambio consiste en transportar productos especiales de la ciudad $1$ a la ciudad $4$ pasando únicamente por ciudades que pertenecen al estado $1$ o al estado $2$. Transportar a lo largo de ciudad $1$ → ciudad $2$ → ciudad $3$ → ciudad $4$ cumple la condición, por lo que se imprime 1.

Esta entrada de ejemplo cumple las restricciones de las Subtareas $1, 3, 4$.

Ejemplo 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

Esta entrada de ejemplo cumple las restricciones de las Subtareas $1, 3, 4$.

Ejemplo 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

Esta entrada de ejemplo cumple las restricciones de todas las subtareas.

Ejemplo 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

Esta entrada de ejemplo cumple las restricciones de las Subtareas $1, 3, 4$.