Chess Piece Swap Game

Little Z is playing a game on a chessboard that is represented by a connected, undirected graph with \(n\) vertices and \(m\) edges. The vertices are labeled \(1,2,\dots,n\). Initially, every vertex has exactly one chess piece, and the pieces are numbered uniquely from \(0\) to \(n-1\).

In each move, Little Z must choose an edge such that one of its endpoints currently holds the piece numbered \(0\). Then, he swaps the pieces on the two endpoints of that edge.

You are given the structure of the graph together with the initial configuration of pieces. There are \(q\) queries; in each query a target configuration is specified. Your task is to determine for each query whether it is possible to transform the initial configuration into the given target configuration by applying a sequence of allowed operations.

Important Note: When the graph is non-bipartite, it can be shown that any configuration is reachable. However, if the graph is bipartite then an invariant holds. In particular, if we define the sign of a permutation \(P\) of \(n\) elements as

[ \text{sign}(P)=(-1)^{n-c(P)} ]

where \(c(P)\) is the number of cycles in \(P\), then for a bipartite graph, the quantity

[ \text{sign}(P)\times (-1)^{\text{color}(s)} ]

remains invariant under every move (here \(\text{color}(s)\) is defined by a valid bipartite 2-coloring of the graph and \(s\) is the vertex containing the piece \(0\)). Thus, in the bipartite case, the initial configuration \(P_{init}\) can reach the target configuration \(P_{target}\) if and only if

[ \text{sign}(P_{init})\times (-1)^{\text{color}(s_{init})} = \text{sign}(P_{target})\times (-1)^{\text{color}(s_{target})} ]

where \(s_{init}\) and \(s_{target}\) are the vertices that initially and finally contain the piece \(0\), respectively.

inputFormat

The first line contains two integers \(n\) and \(m\) -- the number of vertices and edges of the graph.

The next \(m\) lines each contain two integers \(u\) and \(v\) indicating an undirected edge between vertices \(u\) and \(v\).

The following line contains \(n\) integers representing the initial configuration. The \(i\)-th integer is the number on the piece at vertex \(i\). The pieces are a permutation of \(\{0,1,\dots,n-1\}\).

The next line contains a single integer \(q\), the number of queries.

Each of the following \(q\) lines contains \(n\) integers representing a target configuration (the \(i\)-th integer is the piece number at vertex \(i\)).

outputFormat

For each query, output a single line containing YES if it is possible to transform the initial configuration into the target configuration using a sequence of allowed operations; otherwise, output NO.

sample

3 3
1 2
2 3
3 1
0 1 2
2
0 1 2
1 2 0

YES
YES

</p>