唯一游走

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的简单连通无向图 $G$。

$G$ 的顶点编号为顶点 $1$,顶点 $2$,$\ldots$,顶点 $N$;边编号为边 $1$,边 $2$,$\ldots$,边 $M$。边 $i$ 连接顶点 $U_i$ 和顶点 $V_i$。

给定边的子集:$S=\{x_1,x_2,\ldots,x_K\}$。

判断 $G$ 上是否存在一条游走(walk),使得对于所有 $x \in S$,该游走恰好经过边 $x$ 一次。

该游走可以任意次(可能为 $0$ 次)经过不在 $S$ 中的边。

什么是游走?

无向图 $G$ 上的游走是由 $k$ 个顶点($k$ 是正整数)和 $(k-1)$ 条边交替出现的序列 $v_1,e_1,v_2,\ldots,v_{k-1},e_{k-1},v_k$,满足边 $e_i$ 连接顶点 $v_i$ 和顶点 $v_{i+1}$。序列中可以多次出现同一条边或同一个顶点。

一条游走恰好经过边 $x$ 一次,当且仅当恰好存在一个 $1 \le i \le k-1$ 使得 $e_i=x$。

输入格式

输入按以下格式从标准输入给出:

$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$。

换句话说,该游走按以下顺序经过 $G$ 上的顶点:$1\to 3\to 4\to 5\to 6\to 4\to 3\to 2$。

这条游走恰好经过边 $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。

数据范围

• $2 \le N \le 2\times 10^5$
• $N-1 \le M \le \min(\frac{N(N-1)}{2},2\times 10^5)$
• $1 \le U_i \lt V_i \le N$
• 若 $i\neq j$,则 $(U_i,V_i)\neq (U_j,V_j)$。
• $G$ 是连通的。
• $1 \le K \le M$
• $1 \le x_1 \lt x_2 \lt \cdots \lt x_K \le M$
• 输入中的所有值均为整数。