Énoncé du problème

Aux États-Unis de JOI, il y a $N$ villes numérotées de $1$ à $N$, et $M$ routes numérotées de $1$ à $M$. La route $i$ ($1 \le i \le M$) relie la ville $U_i$ et la ville $V_i$ dans les deux sens.

Les États-Unis de JOI sont divisés en $K$ États numérotés de $1$ à $K$. La ville $j$ ($1 \le j \le N$) appartient à l'État $S_j$. De plus, chaque État contient au moins $1$ ville.

Le directeur K, ministre de l'Industrie des États-Unis de JOI, prévoit d'effectuer $Q$ échanges commerciaux. Le $k$-ième échange ($1 \le k \le Q$) consiste à transporter des produits régionaux de la ville $A_k$ à la ville $B_k$ en empruntant certaines routes et villes. Cependant, seuls l'État $S_{A_k}$ et l'État $S_{B_k}$ (ou uniquement l'État $S_{A_k}$ lorsque $S_{A_k} = S_{B_k}$) coopèrent à cet échange, et si l'itinéraire passe par une ville n'appartenant pas à ces États, les produits régionaux seront volés.

Le directeur K souhaite savoir s'il existe un itinéraire de transport permettant de réaliser l'échange sans que les produits régionaux ne soient volés. Étant donné la disposition des villes et des routes, ainsi que les informations sur les États et les échanges, écrivez un programme pour déterminer, pour chaque échange, s'il est possible de livrer les produits régionaux en toute sécurité.

Contraintes

• $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$).
• Pour tout $l$ ($1 \le l \le K$), il existe $j$ ($1 \le j \le N$) tel 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$).
• Toutes les valeurs d'entrée sont des entiers.

Sous-tâches

1. ($5$ points) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ points) Toutes les villes appartenant à l'État $l$ ($1 \le l \le K$) peuvent communiquer entre elles en ne passant que par des routes et des villes appartenant à l'État $l$.
3. ($42$ points) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ points) Aucune contrainte supplémentaire.

Entrée

L'entrée est donnée depuis l'entrée standard dans le format suivant :

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

Sortie

Sur la sortie standard, affichez $Q$ lignes. Sur la $k$-ième ligne ($1 \le k \le Q$), affichez 1 s'il est possible de livrer les produits régionaux lors du $k$-ième échange, et 0 si c'est impossible.

Exemple 1

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

1
0
1

• Le $1$-er échange consiste à transporter des produits régionaux de la ville $1$ à la ville $2$ en ne passant que par des villes appartenant à l'État $1$ ou à l'État $2$. Le transport via ville $1$ → ville $2$ respecte la condition, on affiche donc 1.
• Le $2$-e échange consiste à transporter des produits régionaux de la ville $1$ à la ville $3$ en ne passant que par des villes appartenant à l'État $1$. Comme aucun itinéraire de transport respectant la condition n'existe, on affiche 0.
• Le $3$-e échange consiste à transporter des produits régionaux de la ville $1$ à la ville $4$ en ne passant que par des villes appartenant à l'État $1$ ou à l'État $2$. Le transport via ville $1$ → ville $2$ → ville $3$ → ville $4$ respecte la condition, on affiche donc 1.

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1, 3, 4$.

Exemple 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

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1, 3, 4$.

Exemple 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

Cet exemple d'entrée satisfait les contraintes de toutes les sous-tâches.

Exemple 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

Cet exemple d'entrée satisfait les contraintes des sous-tâches $1, 3, 4$.