← 返回题目列表

AtCoder · abc286_g

G. 独特的步行

中文机器翻译题面 查看原题

分数: 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 。