题目描述

题目译自 Romanian Master of Informatics 2018 Day2 T1 「Colors」

你面对一个包含 $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$。

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

1
0

在第一组测试数据中，图是一个包含 $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$

详细子任务附加限制及分值如下表所示。