考虑一个包含 $N$ 个节点和 $M$ 条边的连通无向图。初始时，每个节点 $u$ 都有一个颜色 $a[u]$，由 $1$ 到 $N$ 之间的一个整数编码。你可以通过执行操作 $a[u] = \min(a[u], a[v])$ 来重复修改节点的颜色，其中 $u$ 和 $v$ 是由一条边连接的。
给定目标颜色序列 $b[1] \dots b[N]$，请判断是否可以将 $a$ 转换为 $b$。
输入格式
输入文件包含多个测试用例，你需要分别回答每一个测试用例。
第一行包含测试用例的数量。每个测试用例的结构如下：
$N$ $M$ $a[1]$ $a[2]$ $\dots$ $a[N]$ $b[1]$ $b[2]$ $\dots$ $b[N]$ $u_1$ $v_1$ $u_2$ $v_2$ $\dots$ $u_M$ $v_M$
输出格式
对于每个测试用例，如果可以通过上述操作将 $a$ 转换为 $b$，则在单独的一行中输出 $1$，否则输出 $0$。
数据范围
- 对于所有测试用例，$N \le 150,000$ 且 $M \le 200,000$。
- 对于每个输入文件，所有测试用例的 $N$ 之和 $\le 300,000$，所有测试用例的 $M$ 之和 $\le 400,000$。
- 对于所有 $1 \le i \le N$，$1 \le a[i], b[i] \le N$。
子任务
每个子任务将作为一个组进行评分。子任务按顺序如下：
| 子任务 | 分值 | 附加输入限制 |
|---|---|---|
| 1 | 15% | 图是一个星形图（$M = N - 1$ 且有一个节点连接到所有其他节点）。所有测试用例的 $N^2$ 之和 $\le 5,000,000$。 |
| 2 | 7% | 图是完全图。$N \le 50$。所有测试用例的 $N \times M$ 之和 $\le 12,000,000$。 |
| 3 | 8% | 图是一条链（$M = N - 1$ 且边构成一条单路径）。所有测试用例的 $N^2$ 之和 $\le 5,000,000$。 |
| 4 | 15% | 图是一条链，无其他限制。 |
| 5 | 7% | 图是一棵树。所有测试用例的 $N^2$ 之和 $\le 5,000,000$。 |
| 6 | 16% | 图是一棵树，且颜色 $a$ 是 $\{1, 2, \dots, N\}$ 的一个排列。 |
| 7 | 10% | 所有测试用例的 $N \times M$ 之和 $\le 5,000,000$。 |
| 8 | 22% | 无。 |
样例
输入 1
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
1 0
说明 1
对于第一个图，所需的操作为： $a[2] = \min(a[2], a[3]) = 2$ $a[1] = \min(a[1], a[2]) = 2$ $a[2] = \min(a[2], a[4]) = 1$