Problem Description

Xiao Z is playing a game on a chessboard. This chessboard is an undirected connected graph with $n$ vertices and $m$ edges. The vertices are labeled with positive integers in $[1,n]$. At the beginning of the game, each vertex has one piece placed on it. Each piece has an integer in $[0,n-1]$, representing the piece’s label. All piece labels are distinct.

In each operation, Xiao Z must first choose an edge of the graph such that one endpoint of this edge currently has the piece labeled $0$. Then, Xiao Z swaps the pieces on the two endpoints of this edge.

Now you are given the graph (the chessboard) and the initial label of the piece on each vertex. Xiao Z asks you to answer $q$ queries. Each query specifies a target state of the chessboard. You need to determine whether it is possible, using some number of operations, to transform the chessboard from the initial state into the target state.

Input Format

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

The next $m$ lines each contain two integers $u,v(1\leq u,v\leq n)$, indicating an undirected edge connecting vertices $u$ and $v$. It is guaranteed that $u\neq v$, so there are no self-loops. It is guaranteed that the given graph is connected, i.e., any two vertices can reach each other through some edges.

The next line contains $n$ space-separated integers. The $i$-th integer denotes the label of the piece on vertex $i$ in the initial state. It is guaranteed that all labels are integers in $[0,n-1]$ and are pairwise distinct.

The next $q$ lines each contain $n$ space-separated integers describing one query. The $i$-th integer denotes the label of the piece on vertex $i$ in the target state. It is guaranteed that all labels are integers in $[0,n-1]$ and are pairwise distinct.

Output Format

Output $q$ lines. Each line contains a string Yes or No. Yes means the target state in the query can be reached from the initial state using some number of operations, and No means it is impossible. Note that the first letter of both Yes and No is uppercase.

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

Yes
Yes
No

Hint

The samples are shown in the figure:

For the first query, it is enough to move the piece labeled $0$ along the path $5-4-3-2-1$. For the second query, move the piece labeled $0$ along $5-3-1-2-3$. The third query has no solution.

All testdata satisfy: $1 \leq n \leq 50$, $1 \leq m \leq 100$, $1 \leq q \leq 1000$.

• Property 1: The degree of every vertex is $2$.
• Property 2: This chessboard can be drawn on a $k \times k$ rectangular grid graph, where $k \times k=n$ and $2k \times (k-1)=m$.
• Property 3: Each edge belongs to at most one simple cycle.

Translated by ChatGPT 5