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

输入 #1

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

输出 #1

YES
NO

输入输出样例 #2

输入 #2

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

输出 #2

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$。

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

题面翻译由 ChatGPT-4o 提供。