题目描述

Due to the disorganized structure of his mootels (much like motels but with bovine rather than human guests), Farmer John has decided to take up the role of the mootel custodian to restore order to the stalls.

Each mootel has $N$ stalls labeled $1$ through $N$ and $M$ corridors that connect pairs of stalls to each other bidirectionally. The $i$ th stall is painted with color $C_i$ and initially has a single key of color $S_i$ in it. FJ will have to rearrange the keys to appease the cows and restore order to the stalls.

FJ starts out in stall $1$ without holding any keys and is allowed to repeatedly do one of the following moves:

• Pick up a key in the stall he is currently in. FJ can hold multiple keys at a time.
• Place down a key he is holding into the stall he is currently in. A stall may hold multiple keys at a time.
• Enter stall $1$ by moving through a corridor.
• Enter a stall other than stall $1$ by moving through a corridor. He can only do this if he currently holds a key that is the same color as the stall he is entering.

Unfortunately, it seems that the keys are not in their intended locations. To restore order to FJ's mootel, the $i$th stall requires that a single key of color $F_i$ is in it. It is guaranteed that $S$ is a permutation of $F$.

For $T$ different mootels, FJ starts in stall $1$ and needs to place every key in its appropriate location, ending back in stall $1$. For each of the $T$ mootels, please answer if it is possible to do this.

输入格式

The first line contains $T$, the number of mootels (test cases).

Each test case will be preceded by a blank line. Then, the first line of each test case contains two integers $N$ and $M$.

The second line of each test case contains $N$ integers. The $i$-th integer on this line $C_i$ means that stall $i$ has color $C_i$.

The third line of each test case contains $N$ integers. The $i$-th integer on this line $S_i$ means that stall $i$ initially holds a key of color $S_i$.

The fourth line of each test case contains $N$ integers. The $i$-th integer on this line $F_i$ means that stall $i$ needs to have a key of color $F_i$ in it.

The next $M$ lines of each test case follow. The $i$-th of these lines contains two distinct integers $u_i$ and $v_i$. This represents that a corridor exists between stalls $u_i$ and $v_i$. No corridors are repeated.

输出格式

For each mootel, output YES on a new line if there exists a way for FJ to return a key of color $F_i$ to each stall $i$ and end back in stall $1$. Otherwise, output NO on a new line.

题目大意

奶牛旅馆可以被看作一个 $N$ 个节点 $M$ 条边的无向简单图，其中每个房间有一个颜色 $C_i$，以及一个钥匙，颜色为 $S_i$， FJ 最初在 $1$ 号节点，手上一把钥匙都没有。

FJ 可以进行无数次以下操作：

• 捡起当前房间的钥匙。（FJ 可以同时手持多个钥匙）

• 将部分或全部手上的钥匙放在当前房间。 (房间内可以同时放多把钥匙)

• 通过一条边，移到一个相邻的房间，前提是目标房间是房间 $1$, 或者 FJ 拥有至少一个目标房间颜色的钥匙。

已知 $F$ 是 $S$ 的排列， FJ 想要让每个房间里面都恰好有一个 $F_i$ 颜色的钥匙，并且最后回到 $1$ 号点。求是否可能。

有 $T$ 组数据，每组数据由一个空行开始，接着先给定 $3$ 行每行 $N$ 个整数，分别表示 $C$,$S$,$F$，最后给定 $M$ 行，每行两个整数表示一条边。

by Error_Eric.

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

提示

For the first test case of the first sample, here is a possible sequence of moves:

Current stall: 1. Keys held: []. Keys in stalls: [3, 4, 3, 4, 2]
(pick up key of color 3)
Current stall: 1. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(move from stall 1 to 2, allowed since we have a key of color C_2=3)
Current stall: 2. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(pick up key of color 4)
Current stall: 2. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(move from stall 2 to 1 to 4 to 5, allowed since we have keys of colors C_4=4 and C_5=3)
Current stall: 5. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(pick up key of color 2 and place key of color 3)
Current stall: 5. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(move from stall 5 to 4 to 1 to 3, allowed since we have keys of colors C_4=4 and C_3=2)
Current stall: 3. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(pick up key of color 3 and place key of color 4)
Current stall: 3. Keys held: [2, 3]. Keys in stalls: [x, x, 4, 4, 3]
(move from stall 3 to stall 2 and place key of color 3)
Current stall: 2. Keys held: [2]. Keys in stalls: [x, 3, 4, 4, 3]
(move from stall 2 to stall 1 and place key of color 2)
Current stall: 1. Keys held: []. Keys in stalls: [2, 3, 4, 4, 3]

For the second test case of the first sample, there exists no way for FJ to return a key of color $F_i$ to each stall $i$ and end back at stall $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$.

• Test cases 3-6 satisfy $N,M\le 8$.
• Test cases 7-10 satisfy $C_i=F_i$.
• Test cases 11-18 satisfy no additional constraints.