#957. 牛舍的钥匙
牛舍的钥匙
题目描述
由于他的“牛旅馆”(类似于汽车旅馆,但以牛为客人)的结构混乱,农夫约翰决定担任牛旅馆管理员的角色,以恢复牛舍的秩序。
每个牛旅馆有 个牛舍,标记为 到 ,以及 条双向连接牛舍的走廊。第 个牛舍被涂上颜色 ,并且最初有一个颜色为 的钥匙。FJ 需要重新安排钥匙以安抚奶牛并恢复牛舍的秩序。
FJ 从牛舍 开始,没有持有任何钥匙,并且可以反复执行以下操作之一:
- 拿起他当前所在牛舍的钥匙。FJ 可以同时持有多个钥匙。
- 将他持有的钥匙放入他当前所在的牛舍。一个牛舍可以同时容纳多个钥匙。
- 通过走廊进入牛舍 。
- 通过走廊进入除牛舍 以外的牛舍——只有当他当前持有的钥匙与他要进入的牛舍颜色相同时,他才能这样做。
不幸的是,钥匙似乎不在它们预定的位置。为了恢复 FJ 的牛旅馆的秩序,第 个牛舍需要有一个颜色为 的钥匙。保证 是 的一个排列。
FJ 从牛舍 开始,需要将每个钥匙放到其适当的位置,最后回到牛舍 。请回答是否可以做到这一点。
多组数据。
输入格式
第一行包含 ,表示测试数据组数。
每组测试数据前都有一个空行。对于每组测试数据:
-
第一行包含两个整数 和 。
-
第二行包含 个整数。第 个整数 表示牛舍 的颜色为 。
-
第三行包含 个整数。第 个整数 表示牛舍 最初有一个颜色为 的钥匙。
-
第四行包含 个整数。第 个整数 表示牛舍 需要有一个颜色为 的钥匙。
-
接下来的 行中,第 行包含两个不同的整数 和 。这表示在牛舍 和 之间存在一条走廊。没有重复的走廊。
输出格式
共 T 行,每组测试数据的答案占一行。对于每组测试数据:
如果存在一种方法可以让 FJ 将颜色为 的钥匙返回到每个牛舍 并最终回到牛舍 ,则在对应行中输出 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
解释
对于第一组测试数据,这里是一个可能的移动序列:
当前牛舍: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 将颜色为 的钥匙放回到每个牛舍 并最终回到牛舍 。
数据范围
, 。 , , 。
- 有 25% 的数据满足 。
- 有 25% 的数据满足 。
- 有 50% 的数据不满足任何附加约束。
相关
在下列比赛中: