分数: 600 点
问题陈述
给你一个简单的连通无向图 G 与 N 顶点和 M 边缘。
的顶点 G 是编号的顶点 1,顶点 2, \ldots和顶点 N,其边被编号为edge 1,边缘 2, \ldots,和边缘 M。
边缘 i 连接顶点 U_i 和顶点 V_i.
您还获得了边的子集: S=\{x_1,x_2,\ldots,x_K\}.
判断是否有步行 G 包含边 x 一劳永逸 x \in S.
行走可能包含不在其中的边 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\leq i\leq k-1 这样 e_i=x.约束
- 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
- If 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 否则。
示例输入 1
6 6 1 3 2 3 3 4 4 5 4 6 5 6 4 1 2 4 5
示例输出 1
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 每个恰好一次。
示例输入 2
6 5 1 2 1 3 1 4 1 5 1 6 3 1 2 3
示例输出 2
No
没有包含边的行走 1, 2,和 3 每个正好一次,所以 No 。