Little Z is playing a game on a chessboard. The chessboard is an undirected connected graph consisting of $n$ vertices and $m$ edges. The vertices are numbered with integers in $[1, n]$. At the beginning of the game, there is a chess piece on each vertex, and each piece has a number in $[0, n - 1]$ assigned to it. No two pieces have the same number.

In each operation, Little Z chooses an edge on the chessboard. If the chess piece on one endpoint of this edge has the number $0$, Little Z can swap it with the chess piece on the other endpoint.

You are now given the configuration of the chessboard and the initial numbers on each vertex. Little Z asks you to answer $q$ queries. Each query specifies a target configuration, and you need to answer whether it is possible to reach this target configuration from the initial configuration through a sequence of operations.

Input

The input is read from the file chess.in.

The first line contains three integers $n, m, q$, representing the number of vertices, the number of edges, and the number of queries, respectively.

The next $m$ lines each contain two integers $u, v$ ($1 \le u, v \le n$), representing an edge between vertices $u$ and $v$. It is guaranteed that $u \neq v$, and there are no self-loops. The given graph is connected, meaning any two vertices can reach each other through some path.

The next line contains $n$ space-separated integers, where the $i$-th integer represents the number on the chess piece at vertex $i$ in the initial configuration. It is guaranteed that the numbers are in $[0, n - 1]$ and are all distinct.

The next $q$ lines each contain $n$ space-separated integers, representing a query, where the $i$-th integer represents the number on the chess piece at vertex $i$ in the target configuration. It is guaranteed that the numbers are in $[0, n - 1]$ and are all distinct.

Output

The output is written to the file chess.out.

Output $q$ lines, each containing the string "Yes" or "No" (without quotes). "Yes" indicates that the initial configuration can reach the target configuration specified in the query through a sequence of operations, and "No" indicates that such a sequence of operations does not exist. Note that the first letters of "Yes" and "No" are capitalized.

Examples

Input 1

5 6 3
2 1
4 5
3 5
3 4
2 3
1 3
1 2 3 4 0
0 1 2 3 4
2 1 0 4 3
4 3 0 1 2

Output 1

Yes
Yes
No

Note 1

The chessboard is shown below:

For the first query, simply move the piece with number $0$ along the path $5 - 4 - 3 - 2 - 1$. For the second query, move the piece with number $0$ along the path $5 - 3 - 1 - 2 - 3$. The third query is impossible to solve.

Input 2

See the files chess/chess2.in and chess/chess2.ans in the contestant directory.

Constraints

There are 20 test cases in total. You will receive full points for a test case only if your output is identical to the standard output. The table below shows the constraints for each test case.

$1 \le q \le 1000$

Characteristic 1: The degree of all vertices is 2.

Characteristic 2: The chessboard can be drawn on a $k \times k$ grid graph, where $k \times k = n$ and $2k \times (k - 1) = m$.

Characteristic 3: Every edge belongs to at most one simple cycle.