Custodial Cleanup

题目描述

由于他的 mootel（类似于 motel，但住客是奶牛而不是人类）的结构十分混乱，Farmer John 决定担任 mootel 的管理员，以恢复畜栏的秩序。 每个 mootel 有 $N$ 个畜栏，编号为 $1$ 到 $N$（$1 \le N \le 10^5$），以及 $M$ 条走廊（$0 \le M \le 10^5$），每条走廊双向连接一对畜栏。第 $i$ 个畜栏被涂成颜色 $C_i$，并且初始时里面有一把颜色为 $S_i$ 的钥匙。FJ 需要重新摆放这些钥匙来安抚奶牛并恢复畜栏秩序。 FJ 从畜栏 $1$ 出发，起初不持有任何钥匙，并且可以反复执行以下操作之一： 在当前所在畜栏中捡起一把钥匙。FJ 可以同时持有多把钥匙。 把自己持有的一把钥匙放到当前所在畜栏中。一个畜栏可以同时存放多把钥匙。 通过一条走廊移动并进入畜栏 $1$。 通过一条走廊移动并进入畜栏 $1$ 以外的某个畜栏。只有当他当前持有一把与要进入畜栏颜色相同的钥匙时，才允许这样做。 不幸的是，钥匙似乎并不在它们应在的位置。为了恢复 mootel 的秩序，第 $i$ 个畜栏要求其中恰好有一把颜色为 $F_i$ 的钥匙。保证 $S$ 是 $F$ 的一个排列。 对于 $T$ 个不同的 mootels（$1 \le T \le 100$），FJ 都从畜栏 $1$ 出发，需要把每把钥匙放到其正确位置，并最终回到畜栏 $1$。请对每个 mootel 判断是否可能完成这一过程。

输入格式

第一行包含整数 $T$，表示 mootels（测试用例）的数量。 每个测试用例前会有一行空行。然后，每个测试用例的第一行包含两个整数 $N$ 和 $M$。 每个测试用例的第二行包含 $N$ 个整数。该行第 $i$ 个整数 $C_i$ 表示畜栏 $i$ 的颜色为 $C_i$（$1 \le C_i \le N$）。 每个测试用例的第三行包含 $N$ 个整数。该行第 $i$ 个整数 $S_i$ 表示畜栏 $i$ 初始时有一把颜色为 $S_i$ 的钥匙（$1 \le S_i \le N$）。 每个测试用例的第四行包含 $N$ 个整数。该行第 $i$ 个整数 $F_i$ 表示畜栏 $i$ 需要有一把颜色为 $F_i$ 的钥匙（$1 \le F_i \le N$）。 接下来是该测试用例的 $M$ 行。第 $i$ 行包含两个不同的整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le N$），表示畜栏 $u_i$ 与 $v_i$ 之间存在一条走廊。不会有重复的走廊。 所有 mootels 的 $N$ 之和不超过 $10^5$，所有 mootels 的 $M$ 之和不超过 $2\cdot 10^5$。

输出格式

对每个 mootel，如果存在一种方式使得 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$。 SCORING: 测试点 3-6 满足 $N,M\le 8$。 测试点 7-10 满足 $C_i=F_i$。 测试点 11-18 没有额外限制。 题目鸣谢：Eric Yachbes

标签: USACO|2023|Gold

来源

USACO|2023|Gold