题目描述

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$。此外，每个州至少包含一个城市。

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 理事长希望调查是否存在一条运输路径，使得特产品在交易过程中不被窃取。当给出城市与道路的布局、州的归属信息以及各次交易的信息时，请编写程序，判断每次交易是否可能安全完成。

输入格式

输入通过标准输入以如下格式给出：

$N$ $M$ $K$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

$S_1$ $S_2$ $\cdots$ $S_N$

$Q$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_Q$ $B_Q$

输出格式

在标准输出中，输出 $Q$ 行。第 $k$ 行（$1 \le k \le Q$）应输出：若第 $k$ 次交易中特产品可以安全送达，则输出 $1$；否则输出 $0$。

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

1
0
1

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

0
1
0
1

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

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 解释

• 第 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 \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) \ne (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 \ne 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$），属于该州的所有城市仅可通过属于该州的道路和城市相互连通。
3. （42 分）$N \le 80\,000$，$M \le 80\,000$，$Q \le 80\,000$。
4. （42 分）无额外约束。

由于没有明确的 Subtask2 的测试点，通过子任务 1、3、4 后会为分数自动增加 11 分。

翻译由 Qwen3-235B 完成