Aufgabenstellung

In den Vereinigten Staaten von JOI gibt es $N$ Städte, die von $1$ bis $N$ nummeriert sind, und $M$ Straßen, die von $1$ bis $M$ nummeriert sind. Straße $i$ ($1 \le i \le M$) verbindet Stadt $U_i$ und Stadt $V_i$ in beide Richtungen.

Die Vereinigten Staaten von JOI bestehen aus $K$ Bundesstaaten, die von $1$ bis $K$ nummeriert sind. Stadt $j$ ($1 \le j \le N$) gehört zum Bundesstaat $S_j$. Außerdem enthält jeder Bundesstaat mindestens $1$ Stadt.

Direktor K, der Industrieminister der Vereinigten Staaten von JOI, plant nun $Q$ Handelsgeschäfte durchzuführen. Das $k$-te Handelsgeschäft ($1 \le k \le Q$) besteht darin, Spezialitäten von Stadt $A_k$ über einige Straßen und Städte nach Stadt $B_k$ zu transportieren. Allerdings kooperieren bei diesem Handel nur der Bundesstaat $S_{A_k}$ und der Bundesstaat $S_{B_k}$ (bzw. nur der Bundesstaat $S_{A_k}$, falls $S_{A_k} = S_{B_k}$), und wenn die Route durch eine Stadt führt, die nicht zu diesen Bundesstaaten gehört, werden die Spezialitäten gestohlen.

Direktor K möchte untersuchen, ob es eine Transportroute gibt, um den Handel durchzuführen, ohne dass die Spezialitäten gestohlen werden. Gegeben die Anordnung der Städte und Straßen sowie Informationen über die Bundesstaaten und Handelsgeschäfte, schreiben Sie ein Programm, das für jedes Handelsgeschäft bestimmt, ob die Spezialitäten sicher geliefert werden können.

Einschränkungen

• $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 jedes $l$ ($1 \le l \le K$) existiert ein $j$ ($1 \le j \le N$), sodass $S_j = l$ gilt.
• $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$).
• Alle Eingabewerte sind ganze Zahlen.

Teilaufgaben

1. ($5$ Punkte) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ Punkte) Alle Städte, die zum Bundesstaat $l$ ($1 \le l \le K$) gehören, können untereinander erreicht werden, indem man ausschließlich Straßen und Städte nutzt, die zum Bundesstaat $l$ gehören.
3. ($42$ Punkte) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ Punkte) Keine weiteren Einschränkungen.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden 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

Ausgabe

Geben Sie auf der Standardausgabe $Q$ Zeilen aus. Geben Sie in der $k$-ten Zeile ($1 \le k \le Q$) 1 aus, wenn es beim $k$-ten Handelsgeschäft möglich ist, die Spezialitäten zu liefern, und 0, wenn es unmöglich ist.

Beispiel 1

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

1
0
1

• Beim $1$. Handelsgeschäft sollen Spezialitäten von Stadt $1$ nach Stadt $2$ transportiert werden, wobei nur Städte durchquert werden dürfen, die zum Bundesstaat $1$ oder zum Bundesstaat $2$ gehören. Der Transport über Stadt $1$ → Stadt $2$ erfüllt die Bedingung, daher wird 1 ausgegeben.
• Beim $2$. Handelsgeschäft sollen Spezialitäten von Stadt $1$ nach Stadt $3$ transportiert werden, wobei nur Städte durchquert werden dürfen, die zum Bundesstaat $1$ gehören. Da keine Transportroute existiert, die die Bedingung erfüllt, wird 0 ausgegeben.
• Beim $3$. Handelsgeschäft sollen Spezialitäten von Stadt $1$ nach Stadt $4$ transportiert werden, wobei nur Städte durchquert werden dürfen, die zum Bundesstaat $1$ oder zum Bundesstaat $2$ gehören. Der Transport über Stadt $1$ → Stadt $2$ → Stadt $3$ → Stadt $4$ erfüllt die Bedingung, daher wird 1 ausgegeben.

Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $1, 3, 4$.

Beispiel 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

Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $1, 3, 4$.

Beispiel 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

Diese Beispieleingabe erfüllt die Einschränkungen aller Teilaufgaben.

Beispiel 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

Diese Beispieleingabe erfüllt die Einschränkungen der Teilaufgaben $1, 3, 4$.