Mootel Reordering

Farmer John’s mootels (motels for cows) are in disarray! Each mootel has N stalls, labeled \(1\) through \(N\), and M bidirectional corridors connecting pairs of stalls. Every stall \(i\) is painted in a color \(C_i\) and initially holds a single key of color \(S_i\). Farmer John must rearrange the keys so that every stall \(i\) eventually contains a key of color \(F_i\). It is guaranteed that \(S\) is a permutation of \(F\).

FJ begins in stall \(1\) with no keys in hand, and he may perform the following operations any number of times:

• Pick up any key present in the current stall (FJ may hold multiple keys simultaneously).
• Place any key he is holding into the current stall (each stall can store multiple keys).
• Move through a corridor to stall \(1\) (this move is always allowed).
• Move through a corridor to any stall other than stall \(1\); however, to enter such a stall \(j\) FJ must be holding at least one key whose color matches the painted color \(C_j\) of stall \(j\).

The goal is to rearrange keys so that for each stall \(i\) the final key in it is of color \(F_i\), and FJ must finish his journey back at stall \(1\>.

For each of \(T\) independent mootels, determine if it is possible for FJ to complete the task under these movement rules.

Key Observations

This problem can be viewed as a modified "key and door" puzzle. Consider each stall \(i (\ge 2)\) as a locked room whose door requires a key of color \(C_i\) to enter. Stall \(1\) is always unlocked. Initially, FJ starts in stall \(1\) and collects the key \(S_1\) there. From that point onward, he may travel along corridors to any adjacent stall \(j\) if he holds a key of color \(C_j\). Upon entering stall \(j\), he picks up its key \(S_j\) (adding to his collection) and can then use any key he holds to unlock subsequent stalls. To achieve the final configuration, each stall must be visited at least once so that the required key can be deposited there.

Thus, the rearrangement is possible if and only if every stall is reachable from stall \(1\) under the condition that a non-\(1\) stall \(j\) can be entered if FJ’s set of keys (which accumulates as he visits stalls) contains the color \(C_j\).

Below is the formal input/output description along with sample test cases and complete solutions in Python3, C++, Java, C, and JavaScript.

inputFormat

The input begins with an integer \(T\) indicating the number of test cases. Each test case is described as follows:

1. One line containing two integers: \(N\) (the number of stalls) and \(M\) (the number of corridors).
2. One line with \(N\) integers: \(C_1, C_2, \ldots, C_N\) representing the painted color of each stall.
3. One line with \(N\) integers: \(S_1, S_2, \ldots, S_N\) where \(S_i\) is the initial key color in stall \(i\).
4. One line with \(N\) integers: \(F_1, F_2, \ldots, F_N\) representing the required key color for each stall. It is guaranteed that \(S\) is a permutation of \(F\).
5. Then \(M\) lines follow, each containing two integers \(u\) and \(v\) indicating that there is a bidirectional corridor between stalls \(u\) and \(v\).

outputFormat

For each test case, output a single line containing the string YES if it is possible for FJ to rearrange the keys and finish in stall \(1\), and NO otherwise.

sample

3
3 2
1 2 3
2 3 1
1 2 3
1 2
2 3

YES