題目描述

在 JOI 合眾國中，有 $N$ 座城市，編號從 $1$ 到 $N$；還有 $M$ 條道路，編號從 $1$ 到 $M$。道路 $i$（$1 \le i \le M$）雙向連接城市 $U_i$ 與城市 $V_i$。

JOI 合眾國由 $K$ 個州組成，編號從 $1$ 到 $K$。城市 $j$（$1 \le j \le N$）隸屬於州 $S_j$。此外，每個州都至少包含 $1$ 座城市。

JOI 合眾國的產業大臣 K 理事長計畫接下來進行 $Q$ 次貿易。第 $k$ 次（$1 \le k \le Q$）貿易是經過若干條道路和城市，將特產從城市 $A_k$ 運輸到城市 $B_k$。然而，在這次貿易中只有州 $S_{A_k}$ 和州 $S_{B_k}$（當 $S_{A_k} = S_{B_k}$ 時則只有州 $S_{A_k}$）會給予協助；如果路線途經任何不屬於這些州的城市，特產就會被偷走。

K 理事長想要調查是否存在一條運輸路線，能夠在特產不被偷走的情況下完成貿易。給定城市與道路的佈局，以及關於各個州和貿易的資訊，請撰寫程式，判斷對於每次貿易是否能夠安全送達特產。

資料範圍

• $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$）。
• 對於每個 $l$（$1 \le l \le K$），均存在 $j$（$1 \le j \le N$）使得 $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$）。
• 輸入的所有值均為整數。

子任務

1. （$5$ 分）$N \le 1\,000$，$M \le 1\,000$，$Q \le 1\,000$。
2. （$11$ 分）隸屬於州 $l$（$1 \le l \le K$）的所有城市之間，都可以僅經過道路和隸屬於州 $l$ 的城市互相到達。
3. （$42$ 分）$N \le 80\,000$，$M \le 80\,000$，$Q \le 80\,000$。
4. （$42$ 分）無額外限制。

輸入格式

輸入從標準輸入按以下格式給出：

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

輸出格式

向標準輸出印出 $Q$ 行。在第 $k$ 行（$1 \le k \le Q$）中，如果第 $k$ 次貿易能夠送達特產，則輸出 1；如果無法送達，則輸出 0。

範例 1

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

1
0
1

• 第 $1$ 次貿易是僅經過隸屬於州 $1$ 或州 $2$ 的城市，將特產從城市 $1$ 運輸到城市 $2$。沿著 城市 $1$ → 城市 $2$ 運輸滿足條件，因此輸出 1。
• 第 $2$ 次貿易是僅經過隸屬於州 $1$ 的城市，將特產從城市 $1$ 運輸到城市 $3$。由於不存在滿足條件的運輸路線，因此輸出 0。
• 第 $3$ 次貿易是僅經過隸屬於州 $1$ 或州 $2$ 的城市，將特產從城市 $1$ 運輸到城市 $4$。沿著 城市 $1$ → 城市 $2$ → 城市 $3$ → 城市 $4$ 運輸滿足條件，因此輸出 1。

本範例輸入滿足子任務 $1, 3, 4$ 的限制。

範例 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

本範例輸入滿足子任務 $1, 3, 4$ 的限制。

範例 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

本範例輸入滿足所有子任務的限制。

範例 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

本範例輸入滿足子任務 $1, 3, 4$ 的限制。