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$ 中的边。

输入格式

输入从标准输入按以下格式给出： $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

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

No

提示

$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 输入中的所有数值均为整数。步行 $(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$。
不存在一条恰好一次包含边 $1$、$2$ 和 $3$ 的步行，因此应输出 $No$。

标签: AtCoder|abc286G

来源

AtCoder|abc286G