由于他的“牛旅馆”（类似于汽车旅馆，但以牛为客人）的结构混乱，农夫约翰决定担任牛旅馆管理员的角色，以恢复牛舍的秩序。

每个牛旅馆有 N 个牛舍，标记为 1 到 N，以及 M 条双向连接牛舍的走廊。第 i 个牛舍被涂上颜色 C_i，并且最初有一个颜色为 S_i 的钥匙。FJ 需要重新安排钥匙以安抚奶牛并恢复牛舍的秩序。

FJ 从牛舍 1 开始，没有持有任何钥匙，并且可以反复执行以下操作之一：

• 拿起他当前所在牛舍的钥匙。FJ 可以同时持有多个钥匙。
• 将他持有的钥匙放入他当前所在的牛舍。一个牛舍可以同时容纳多个钥匙。
• 通过走廊进入牛舍 1。
• 通过走廊进入除牛舍 1 以外的牛舍。只有当他当前持有的钥匙与他要进入的牛舍颜色相同时，他才能这样做。

不幸的是，钥匙似乎不在它们预定的位置。为了恢复 FJ 的牛旅馆的秩序，第 i 个牛舍需要有一个颜色为 F_i 的钥匙。保证 S 是 F 的一个排列。

对于 T 个不同的牛旅馆，FJ 从牛舍 1 开始，需要将每个钥匙放到其适当的位置，最后回到牛舍 1。对于每个 T 个牛旅馆，请回答是否可以做到这一点。

第一行包含 T，表示牛旅馆的数量（测试用例）。

每个测试用例前都有一个空行。然后，每个测试用例的第一行包含两个整数 N 和 M。

每个测试用例的第二行包含 N 个整数。第 i 个整数 C_i 表示牛舍 i 的颜色为 C_i。

每个测试用例的第三行包含 N 个整数。第 i 个整数 S_i 表示牛舍 i 最初持有一个颜色为 S_i 的钥匙。

每个测试用例的第四行包含 N 个整数。第 i 个整数 F_i 表示牛舍 i 需要有一个颜色为 F_i 的钥匙。

每个测试用例接下来的 M 行中，第 i 行包含两个不同的整数 u_i 和 v_i。这表示在牛舍 u_i 和 v_i 之间存在一条走廊。没有重复的走廊。

对于每个牛旅馆，如果存在一种方法可以让 FJ 将颜色为 F_i 的钥匙返回到每个牛舍 i 并最终回到牛舍 1，则在新行中输出 YES。否则，在新行中输出 NO。

对于第一个样例的第一个测试用例，这里是一个可能的移动序列：

当前牛舍：1。持有的钥匙：[]。牛舍中的钥匙：[3, 4, 3, 4, 2]
（拿起颜色为 3 的钥匙）
当前牛舍：1。持有的钥匙：[3]。牛舍中的钥匙：[x, 4, 3, 4, 2]
（从牛舍 1 移动到 2，因为我们有颜色为 C_2=3 的钥匙）
当前牛舍：2。持有的钥匙：[3]。牛舍中的钥匙：[x, 4, 3, 4, 2]
（拿起颜色为 4 的钥匙）
当前牛舍：2。持有的钥匙：[3, 4]。牛舍中的钥匙：[x, x, 3, 4, 2]
（从牛舍 2 移动到 1 到 4 到 5，因为我们有颜色为 C_4=4 和 C_5=3 的钥匙）
当前牛舍：5。持有的钥匙：[3, 4]。牛舍中的钥匙：[x, x, 3, 4, 2]
（拿起颜色为 2 的钥匙并放下颜色为 3 的钥匙）
当前牛舍：5。持有的钥匙：[2, 4]。牛舍中的钥匙：[x, x, 3, 4, 3]
（从牛舍 5 移动到 4 到 1 到 3，因为我们有颜色为 C_4=4 和 C_3=2 的钥匙）
当前牛舍：3。持有的钥匙：[2, 4]。牛舍中的钥匙：[x, x, 3, 4, 3]
（拿起颜色为 3 的钥匙并放下颜色为 4 的钥匙）
当前牛舍：3。持有的钥匙：[2, 3]。牛舍中的钥匙：[x, x, 4, 4, 3]
（从牛舍 3 移动到牛舍 2 并放下颜色为 3 的钥匙）
当前牛舍：2。持有的钥匙：[2]。牛舍中的钥匙：[x, 3, 4, 4, 3]
（从牛舍 2 移动到牛舍 1 并放下颜色为 2 的钥匙）
当前牛舍：1。持有的钥匙：[]。牛舍中的钥匙：[2, 3, 4, 4, 3]

对于第一个样例的第二个测试用例，没有办法让 FJ 将颜色为 F_i 的钥匙返回到每个牛舍 i 并最终回到牛舍 1。

0 \le M \le 10^5, 1 \le C_i, S_i, F_i, u_i, v_i \le N \le 10^5。 1 \le T \le 100, 1 \le \sum N \le 10^5, 1 \le \sum M \le 2\cdot 10^5。

• 测试用例 3-6 满足 N,M\le 8。
• 测试用例 7-10 满足 C_i=F_i。
• 测试用例 11-18 不满足任何附加约束。

USACO