当前没有测试数据。

G - 独特的步行路径

得分：$600$ 分

问题描述

给定一个简单的连通无向图 $G$，它有 $N$ 个顶点和 $M$ 条边。
图 $G$ 的顶点从 $1$ 到 $N$ 编号，边从 $1$ 到 $M$ 编号。 第 $i$ 条边连接着顶点 $U_i$ 和顶点 $V_i$。
还给出了边的一个子集：$S=\{x_1,x_2,\ldots,x_K\}$。

确定是否存在一条在 $G$ 上的步行路径，使得对于所有 $x \in S$，路径上包含边 $x$ 恰好一次。
路径上可以包含不属于 $S$ 的边任意次数（也可以没有）。

约束

• $2 \leq N \leq 2\times 10^5$
• $N-1 \leq M \leq \min(\frac{N(N-1)}{2},2\times 10^5)$
• $1 \leq U_i<V_i\leq N$
• 如果 $i\neq j$，那么 $(U_i,V_i)\neq (U_j,V_j)$。
• $G$ 是连通的。
• $1 \leq K \leq M$
• $1 \leq x_1<x_2<\cdots<x_K \leq M$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出：

$N$ $M$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_M$ $V_M$

$K$

$x_1$ $x_2$ $\ldots$ $x_K$

输出

如果存在满足问题描述中条件的步行路径，则输出 Yes；否则输出 No。

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

Yes

步行路径 $(v_1,e_1,v_3,e_3,v_4,e_4,v_5,e_6,v_6,e_5,v_4,e_3,v_3,e_2,v_2)$ 满足条件，其中 $v_i$ 表示顶点 $i$、$e_i$ 表示边 $i$。
换句话说，该路径按照 $1\to 3\to 4\to 5\to 6\to 4\to 3\to 2$ 的顺序在图 $G$ 上遍历了顶点。
该路径满足条件，因为它恰好包含了边 $1$、$2$、$4$ 和 $5$ 各一次。

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

No

不存在一条包含边 $1$、$2$ 和 $3$ 的步行路径，所以应该输出 No。