题目描述

在 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$ 的限制。