P14532 [RMI 2018] 颜色 / Colors

翻译来自于 [LibreOJ](https://loj.ac/p/5127)。

**题目译自 [Romanian Master of Informatics 2018](https://rmi.lbi.ro/rmi_2018/) Day2 T1 「[Colors](https://rmi.lbi.ro/rmi_2018/_dwl/public.zip)」** 你有一个包含 $N$ 个节点和 $M$ 条边的连通无向图。初始时，每个节点 $u$ 有一个颜色 $a_u$，用一个介于 $1$ 到 $N$ 的整数表示。你可以反复修改节点的颜色，通过操作 $a_u = \min(a_u, a_v)$，其中 $u$ 和 $v$ 是通过边连接的节点。 给定目标颜色数组 $b_1, \ldots b_N$，你的任务是判断是否能通过上述操作将颜色数组 $a$ 转换为 $b$。

每个输入文件包含多组测试数据，你需要分别回答每组测试数据。 第一行包含一个整数 $T$，表示测试数据的数量。每组测试数据的结构如下： - 第一行包含两个整数 $N$ 和 $M$ 分别表示节点数和边数。 - 接下来一行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$，表示初始颜色。 - 接下来一行包含 $N$ 个整数 $b_1, b_2, \ldots, b_N$，表示目标颜色。 - 接下来的 $M$ 行每行包含两个整数 $u_i, v_i$，表示节点 $u_i$ 和 $v_i$ 之间有一条边。

对于每组测试数据，如果可以通过上述操作将 $a$ 转换为 $b$，输出一行 $1$，否则输出 $0$。

### 样例 1 解释 在第一组测试数据中，图是一个包含 $4$ 个节点和 $4$ 条边的连通图。需要的操作如下： - $a_2 = \min(a_2, a_3) = 2$ - $a_1 = \min(a_1, a_2) = 2$ - $a_2 = \min(a_2, a_4) = 1$ 通过这些操作，初始颜色 $a = [3, 3, 2, 1]$ 可以转换为目标颜色 $b = [2, 1, 2, 1]$，因此输出 $1$。 在第二组测试数据中，无法通过上述操作将初始颜色 $a = [3, 3, 2, 1]$ 转换为目标颜色 $b = [1, 2, 2, 1]$，因此输出 $0$。 ### 数据范围 对于所有输入数据，满足： - 对于所有测试数据，$N \leq 150000$，$M \leq 200000$ - 所有测试数据组的 $N$ 之和 $\leq 300000$，$M$ 之和 $\leq 400000$ - 对于所有 $1 \leq i \leq N$，$1 \leq a_i,b_i \leq N$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :----: | :----: | :-------: | | $1$ | $15$ | 图为星形图（$M = N - 1$，一个节点连接到所有其他节点），所有测试数据的 $N^2$ 之和 $\leq 5000000$ | | $2$ | $7$ | 图为完全图，$N \leq 50$，所有测试数据的 $N \times M$ 之和 $\leq 12000000$ | | $3$ | $8$ | 图为一条链（$M = N - 1$，边形成单路径），所有测试数据的 $N^2$ 之和 $\leq 5000000$ | | $4$ | $15$ | 图为一条链，无进一步限制 | | $5$ | $7$ | 图为树，所有测试数据的 $N^2$ 之和 $\leq 5000000$ | | $6$ | $16$ | 图为树，初始颜色 $a$ 是 $\{1, 2, \ldots, N\}$ 的一个排列 | | $7$ | $10$ | 所有测试数据的 $N \times M$ 之和 $\leq 5000000$ | | $8$ | $22$ | 无附加限制 |