Description

To recreate the comet of that day, Nana and Lily need to use specific number pairs to transform one sequence into another.

Nana has a sequence $a$ of length $n$. Lily can choose an index $i(1\le i<n)$ each time, and then operate $a_i\leftarrow x,a_{i+1}\leftarrow y$.

The chosen $1\le x,y\le k$ must satisfy $f(a_i,a_{i+1})=f(x,y)=1$. Lily finally needs to transform $a$ into another sequence $b$ of length $n$.

Here, Nana will give an undirected graph $G$ with $k$ vertices and $m$ edges. It is not guaranteed that there are no multiple edges or self-loops. Then $f(x,y)=1$ if and only if there is an edge between $x$ and $y$ in the graph. Note that if there is a self-loop at $x$ (an edge from $x$ to $x$), then $f(x,x)=1$; otherwise, $f(x,x)=0$.

Lily is not very concerned about the construction of the solution, so she wants you to answer for multiple test cases whether $a$ can be transformed into another sequence $b$ of length $n$.

Input Format

Each data point starts with three integers $m, k, T$.

The first $m$ lines, the $i$-th line has two integers $x_i, y_i$ indicating the $i$-th edge connects $(x_i,y_i)$.

Then, there are $T$ test cases.

Each test case input has three lines:

• The first line is an integer $n$.
• The second line is a sequence $a$ of length $n$, where the $i$-th number is $a_i$.
• The third line is a sequence $b$ of length $n$, where the $i$-th number is $b_i$.

Output Format

For each test case, output one line with a string. If it is possible to transform $a$ into $b$, output YES; otherwise, output NO.

1 2 2
1 2
6
1 1 2 1 2 2
2 1 1 2 2 1
2
2 2
1 2

YES
NO

Hint

Sample Explanation

For the first sample, we can operate as follows:

1. Choose $i=2$, the sequence becomes $[1,2,1,1,2,2]$.
2. Choose $i=1$, the sequence becomes $[2,1,1,1,2,2]$.
3. Choose $i=4$, the sequence becomes $[2,1,1,2,1,2]$.
4. Choose $i=5$, the sequence becomes $[2,1,1,2,2,1]$.

For the second sample, clearly you cannot perform the first operation. So it is impossible.

Data Range

This problem uses subtask bundling. You must pass all test points in a subtask to get the corresponding score.

For all data, $1\le T\le 10^4$, $2\le n\le 10^5$, $\sum n\le 10^6$, $1\le m\le 3\times 10^5$, $1\le k\le 2\times 10^5$.

It is guaranteed that $1\le a_i,b_i,x_i,y_i\le k$. The graph is not guaranteed to be without multiple edges or self-loops.