06717. USACO·保洁清理 未做

由于他的牛旅馆（mootel，与汽车旅馆 motel 十分类似，只是住客从人类换成了牛）结构杂乱无章，Farmer John 决定亲自出任牛旅馆管理员，来恢复牛栏的秩序。

每座牛旅馆有 $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$ 以外的其他牛栏。只有当他当前持有一把与所要进入的牛栏颜色相同的钥匙时，他才能这样做。

不幸的是，钥匙们似乎并不在它们应在的位置上。为了恢复 FJ 的牛旅馆的秩序，第 $i$ 个牛栏中需要恰好有一把颜色为 $F_i$ 的钥匙。保证 $S$ 是 $F$ 的一个排列。

对于 $T$（$1\le T\le 100$）座不同的牛旅馆，FJ 从牛栏 $1$ 出发，需要把每把钥匙都放到合适的位置，并最终回到牛栏 $1$。对于这 $T$ 座牛旅馆，请分别回答这是否可能做到。

第一行包含 $T$，即牛旅馆（测试用例）的数量。

每个测试用例前有一个空行。然后，每个测试用例的第一行包含两个整数 $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$ 之间存在一条走廊。走廊不会重复。

所有牛旅馆的 $N$ 之和不超过 $10^5$，所有牛旅馆的 $M$ 之和不超过 $2\cdot 10^5$。

对于每座牛旅馆，如果存在一种方案，使 FJ 能把颜色为 $F_i$ 的钥匙放回每个牛栏 $i$ 并最终回到牛栏 $1$，则在新的一行输出 YES；否则在新的一行输出 NO。

【样例解释】

【数据规模与约定】

• 测试点 3-6：$N,M\le 8$。
• 测试点 7-10：$C_i=F_i$。
• 测试点 11-18：无额外限制。