AT_joi2022_yo2_e.交易計画 (Trade Plan)

题目简述

有一张 $N$ 点 $M$ 边的无向图。节点的编号从 $1$ 到 $N$，第 $i$ 条边连接点 $U_i$ 和点 $V_i$（$1\le i\le M$）。

现在每个点都被染上了 $K$ 种颜色中的一种。颜色的编号从 $1$ 到 $K$，节点 $j$ 的颜色是 $S_j$（$1\le j\le N$）。保证对于任一整数 $x\in [1,K]$，都有至少一个整数 $j\in [1,N]$ 满足 $S_j=x$。

有 $Q$ 次询问，第 $k$ 次询问给出两个整数 $A_k,B_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}$）。如果有请输出 1，否则请输出 0。

输入以以下格式从标准输入给出。

$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$）：

• 若存在符合条件的路径，输出 1；
• 否则，输出 0。

样例解释

样例 #1,#2,#4 满足子任务 $1,3,4$ 的限制。

样例 #3 满足全部子任务的限制。

数据规模与约定

对于 $100\%$ 的测试点，保证：

• $2\le N\le 400000$，$1\le M\le 400000$，$1\le K\le N$；
• $1\le U_i\lt V_i\le N$（$1\le i\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 400000$；
• $1\le A_k,B_k\le N$，$A_k\neq B_k$（$1\le k\le Q$）；
• 输入数据均为整数。

本题采取捆绑测试。 各子任务分值及特殊限制如下：

子任务编号	分值	特殊限制
$1$	$5$	$N,M,Q\le 1000$
$2$	$11$	对于任意满足 $1\le l\le K$ 的整数 $l$，所有满足 $S_j=l$ 的城市可以仅通过同一颜色的点直接到达
$3$	$42$	$N,M,Q\le 80000$
$4$	$42$	无特殊限制