[WC2017-A]棋盘

内存限制：1024 MB 时间限制：3000 ms

小 Z 在一块棋盘上玩游戏。这块棋盘是一个由 $n$ 个顶点和 $m$ 条边组成的无向连通图，图上的顶点编号为 $[1,n]$ 中的正整数。游戏开始时，每个顶点上都放有一个棋子，每个棋子上有一个 $[0,n−1]$ 中的整数，表示棋子的编号。不同棋子的编号互不相同。

每次操作时，小 Z 需要先选择棋盘上的一条边，这条边的一个端点此时放有 $0$ 号棋子。然后，小 Z 将这条边两个端点上的棋子交换。

现在你已经知道棋盘的模样，以及初始状态下每个顶点上的棋子编号。小 Z 想请你回答 $q$ 个询问。每个询问指定了棋盘的目标状态，你需要回答能否通过若干次操作，将棋盘由初始状态变为这个目标状态。

第一行输入三个正整数 $n,m,q$，分别表示图中的顶点数、边数，以及询问的个数。

接下来 $m$ 行，每行两个整数 $u,v(1≤u,v≤n)$，表示图中有一条连接 $u,v$ 两顶点的无向边。保证 $u≠v$，即图中不存在自环。保证给出的图是连通图，即任意两个顶点都可以经过若干条边而相互到达。

接下来一行有 $n$ 个空格隔开的整数，其中第 $i$ 个整数表示初始状态下 $i$ 号顶点上的棋子的编号，保证编号都为 $[0,n−1]$ 中的整数，且两两不同。

接下来 $q$ 行，每行有 $n$ 个空格隔开的整数，表示一个询问，其中第 $i$ 个整数表示目标状态中第 $i$ 号顶点上的棋子的编号，保证编号都为 $[0,n−1]$ 中的整数，且两两不同。

输出 $q$ 行，每行一个字符串Yes或者No作为回答。Yes表示从棋子的初始状态可以经过若干次操作而达到询问中所指定的目标状态，No表示不存在这样的操作步骤。注意：Yes和No的首字母都是大写的。

Yes
Yes
No

【样例说明】

屏幕快照 2019-06-25 下午12.18.12.png

对于第一组询问，只要将 0 号点沿着 5−4−3−2−1 的路径移动。对于第二组询问，将 0 号点沿着 5−3−1−2−3 移动。对于第三组询问是无解的。

【数据范围】

对于100%数据满足 $1≤n≤50,1≤m≤100,1≤q≤1000$

对于前10%的数据，$n≤8,m≤15$

另有10%的数据，满足 $m=n−1$

另有20%的数据，满足 $m=n$，且其中10%的满足特殊性质1。

另有10%的数据，满足特殊性质 2

另有15%的数据，满足特殊性质 3。

其中，

特殊性质 1 保证每个点的度数均为 2

特殊性质 2 保证这个棋盘可以绘制在一个 $k × k$ 的矩形网格图上。其中 $k × k = n$ 且 $ 2k × (k−1) = m$

特殊性质 3 保证每条边至多属于一个简单环

C0437 [WC2017-A]棋盘