題目描述

喺 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$ 嘅限制。