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$ | 无特殊限制 |