P9189 [USACO23OPEN] Custodial Cleanup G

由于他的“牛旅馆”（类似于汽车旅馆，但以牛为客人）的结构混乱，农夫约翰决定担任牛旅馆管理员的角色，以恢复牛舍的秩序。 每个牛旅馆有 $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 不满足任何附加约束。 题面翻译由 ChatGPT-4o 提供。