C. 牛舍的钥匙

    传统题 1000ms 256MiB

牛舍的钥匙

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

由于他的“牛旅馆”(类似于汽车旅馆,但以牛为客人)的结构混乱,农夫约翰决定担任牛旅馆管理员的角色,以恢复牛舍的秩序。

每个牛旅馆有 NN 个牛舍,标记为 11 到 NN,以及 MM 条双向连接牛舍的走廊。第 ii 个牛舍被涂上颜色 CiC_i,并且最初有一个颜色为 SiS_i 的钥匙。FJ 需要重新安排钥匙以安抚奶牛并恢复牛舍的秩序。

FJ 从牛舍 11 开始,没有持有任何钥匙,并且可以反复执行以下操作之一:

  • 拿起他当前所在牛舍的钥匙。FJ 可以同时持有多个钥匙。
  • 将他持有的钥匙放入他当前所在的牛舍。一个牛舍可以同时容纳多个钥匙。
  • 通过走廊进入牛舍 11。
  • 通过走廊进入除牛舍 11 以外的牛舍——只有当他当前持有的钥匙与他要进入的牛舍颜色相同时,他才能这样做。

不幸的是,钥匙似乎不在它们预定的位置。为了恢复 FJ 的牛旅馆的秩序,第 ii 个牛舍需要有一个颜色为 FiF_i 的钥匙。保证 SS 是 FF 的一个排列。

FJ 从牛舍 11 开始,需要将每个钥匙放到其适当的位置,最后回到牛舍 11。请回答是否可以做到这一点。

多组数据。

输入格式

第一行包含 TT,表示测试数据组数。

每组测试数据前都有一个空行。对于每组测试数据:

  • 第一行包含两个整数 NN 和 MM。

  • 第二行包含 NN 个整数。第 ii 个整数 CiC_i 表示牛舍 ii 的颜色为 CiC_i。

  • 第三行包含 NN 个整数。第 ii 个整数 SiS_i 表示牛舍 ii 最初有一个颜色为 SiS_i 的钥匙。

  • 第四行包含 NN 个整数。第 ii 个整数 FiF_i 表示牛舍 ii 需要有一个颜色为 FiF_i 的钥匙。

  • 接下来的 MM 行中,第 ii 行包含两个不同的整数 uiu_i 和 viv_i。这表示在牛舍 uiu_i 和 viv_i 之间存在一条走廊。没有重复的走廊。

输出格式

共 T 行,每组测试数据的答案占一行。对于每组测试数据:

如果存在一种方法可以让 FJ 将颜色为 FiF_i 的钥匙返回到每个牛舍 ii 并最终回到牛舍 11,则在对应行中输出 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 将颜色为 FiF_i 的钥匙放回到每个牛舍 ii 并最终回到牛舍 11。

数据范围

0≤M≤1050 \le M \le 10^5, 1≤Ci,Si,Fi,ui,vi≤N≤1051 \le C_i, S_i, F_i, u_i, v_i \le N \le 10^5。 1≤T≤1001 \le T \le 100, 1≤∑N≤1051 \le \sum N \le 10^5, 1≤∑M≤2⋅1051 \le \sum M \le 2\cdot 10^5。

  • 有 25% 的数据满足 N,M≤8N,M\le 8。
  • 有 25% 的数据满足 Ci=FiC_i=F_i。
  • 有 50% 的数据不满足任何附加约束。

2026-10-29

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-10-29 7:40
结束于
2026-10-29 12:00
持续时间
4.3 小时
主持人
参赛人数
16