4304: 「WC2017」棋盘
内存限制：1024 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
小 Z 在一块棋盘上玩游戏。这块棋盘是一个由 $n$ 个顶点和 $m$ 条边组成的无向连通图，图上的顶点编号为 $[1,n]$ 中的正整数。游戏开始时，每个顶点上都放有一个棋子，每个棋子上有一个 $[0,n−1]$ 中的整数，表示棋子的编号。不同棋子的编号互不相同。
每次操作时，小 Z 需要先选择棋盘上的一条边，这条边的一个端点此时放有 $0$ 号棋子。然后，小 Z 将这条边两个端点上的棋子交换。
现在你已经知道棋盘的模样，以及初始状态下每个顶点上的棋子编号。小 Z 想请你回答 $q$ 个询问。每个询问指定了棋盘的目标状态，你需要回答能否通过若干次操作，将棋盘由初始状态变为这个目标状态。
输入
第一行输入三个正整数 $n,m,q$，分别表示图中的顶点数、边数，以及询问的个数。
接下来 $m$ 行，每行两个整数 $u,v\ (1\leq u,v\leq n)$，表示图中有一条连接 $u,v$ 两顶点的无向边。保证 $u\neq v$ ，即图中不存在自环。保证给出的图是连通图，即任意两个顶点都可以经过若干条边而相互到达。
接下来一行有 $n$ 个空格隔开的整数，其中第 $i$ 个整数表示初始状态下 $i$ 号顶点上的棋子的编号，保证编号都为 $[0,n-1]$ 中的整数，且两两不同。
接下来 $q$ 行，每行有 $n$ 个空格隔开的整数，表示一个询问，其中第 $i$ 个整数表示目标状态中第 $i$ 号顶点上的棋子的编号，保证编号都为 $[0,n-1]$ 中的整数，且两两不同。
输出
输出 $q$ 行，每行一个字符串 `Yes` 或者 `No`（不含引号）作为回答。`Yes` 表示从棋子的初始状态可以经过若干次操作而达到询问中所指定的目标状态，`No` 表示不存在这样的操作步骤。注意：`Yes` 和 `No` 的首字母都是大写的。
样例输入 复制
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提示
输入样例2
输出样例2
数据范围：本题共有 20 个测试点。 对于每个测试点，只有当你的输出与标准输出完全相同时，才能得到该测试点的满分。 下表为各个测试点的数据范围和约定。 | 测试点编号 | $n$ | $m$ | 数据特性 | | :-----: | :---------: | :-----------: | :----: | | 1 | $\leq 8$ | $ \leq 15$ | 无 | | 2 | $\leq 8$ | $ \leq 15$ | 无 | | 3 | $\leq 50$ | $ = n-1 $ | 无 | | 4 | $\leq 50$ | $ = n-1 $ | 无 | | 5 | $\leq 50$ | $ =n $ | 特性 1 | | 6 | $\leq 50$ | $ =n $ | 特性 1 | | 7 | $\leq 50$ | $ =n $ | 无 | | 8 | $\leq 50$ | $ =n $ | 无 | | 9 | $\leq 50$ | $ \leq 100$ | 特性 2 | | 10 | $\leq 50$ | $ \leq 100$ | 特性 2 | | 11 | $\leq 50$ | $ \leq 100$ | 特性 3 | | 12 | $\leq 50$ | $ \leq 100$ | 特性 3 | | 13 | $\leq 50$ | $ \leq 100$ | 特性 3 | | 14 | $\leq 50$ | $ \leq 100$ | 无 | | 15 | $\leq 50$ | $ \leq 100$ | 无 | | 16 | $\leq 50$ | $ \leq 100$ | 无 | | 17 | $\leq 50$ | $ \leq 100$ | 无 | | 18 | $\leq 50$ | $ \leq 100$ | 无 | | 19 | $\leq 50$ | $ \leq 100$ | 无 | | 20 | $\leq 50$ | $ \leq 100$ | 无 | $1\le q\le 1000$ 特性 1：所有顶点的度数均为 $2$。 特性 2：这个棋盘可以绘制在一个 $k\times k$ 的矩形网格图上。其中 $k\times k=n$ 且 $2k\times (k−1)=m$。 特性 3：每条边至多属于一个简单环。