由于他的“牛旅馆”（类似于汽车旅馆，但以牛为客人）的结构混乱，农夫约翰决定担任牛旅馆管理员的角色，以恢复牛舍的秩序。
每个牛旅馆有 N 个牛舍，标记为 1 到 N，以及 M 条双向连接牛舍的走廊。第 i 个牛舍被涂上颜色 C_i，并且最初有一个颜色为 S_i 的钥匙。FJ 需要重新安排钥匙以安抚奶牛并恢复牛舍的秩序。
FJ 从牛舍 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。
2 5 5 4 3 2 4 3 3 4 3 4 2 2 3 4 4 3 1 2 2 3 3 1 4 1 4 5 4 3 3 2 4 1 2 3 4 4 4 2 3 4 4 2 4 1 4 3
YES NO
5 2 0 1 2 2 2 2 2 2 1 1 1 2 1 2 1 1 2 2 1 1 1 2 1 1 2 1 2 2 1 1 1 1 2 2 1 1 2 5 4 1 2 3 4 4 2 3 5 4 2 5 3 2 4 2 1 2 1 3 1 4 4 5
YES YES NO 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。
USACO