AT_abc286_g [ABC286G] Unique Walk

题目描述

给定一个有 $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$ 上是否存在一条“步道”，使得对于任意 $x\in S$，边 $x$ 恰好被经过一次。
对于不在 $S$ 中的边，可以经过任意次数（包括 $0$ 次）。

步道的定义如下：
在无向图 $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\leq i\leq k-1$ 中，只有唯一的 $i$ 使得 $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。

输入输出样例 #1

输入 #1

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

输出 #1

Yes

输入输出样例 #2

输入 #2

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

输出 #2

No

说明/提示

限制条件

• $2\leq N\leq 2\times 10^5$
• $N-1\leq M\leq \min\left(\frac{N(N-1)}{2},2\times 10^5\right)$
• $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$
• 输入均为整数

样例解释 1

用 $v_i$ 表示顶点 $i$，$e_j$ 表示边 $j$，则序列 $(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)$ 表示的步道满足条件。
即在 $G$ 上按顶点 $1\to 3\to 4\to 5\to 6\to 4\to 3\to 2$ 的顺序移动。
该步道恰好经过了边 $1,2,4,5$ 各一次，满足条件。

样例解释 2

不存在一条步道恰好经过边 $1,2,3$ 各一次，因此输出 No。

由 ChatGPT 4.1 翻译