唯一漫步(Unique Walk)

题目描述

本题对应 AtCoder Beginner Contest 286 Problem G：Unique Walk。

给定一个包含 $n$ 个顶点、$m$ 条边的连通无向图，边的编号为 $1 \sim m$，其中第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

给定一个包含 $k$ 条指定边的集合 $S = \{x_1, x_2, \dots, x_k\}$。请你判断图中是否存在一条路径（Walk，允许重复经过顶点和非 $S$ 中的边），使得集合 $S$ 中的每一条边都在该路径上恰好被经过一次（不在 $S$ 中的边可以被经过任意次，包括 $0$ 次）。

输入格式

第一行包含两个正整数 $n, m$。

接下来 $m$ 行，第 $i$ 行包含两个正整数 $u_i, v_i$。

下一行包含一个正整数 $k$（$1 \le k \le m$）。

最后一行包含 $k$ 个递增的正整数 $x_1, x_2, \dots, x_k$，表示集合 $S$ 中的边编号。

输出格式

若存在满足条件的路径，输出一行 Yes，否则输出一行 No。

样例输入 #1

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

样例输出 #1

Yes

样例输入 #2

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

样例输出 #2

Yes

数据范围

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$n - 1 \le m \le 2 \times 10^5$，$1 \le k \le m$，保证原图连通。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接