题目描述

$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$ をちょうど $1$ 回ずつ通るようなものが存在するか判定してください。
$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$ 回通るとは、$e_i=x$ となるような $1\leq\ i\leq\ k-1$ がただ $1$ つ存在することをいう。

输入格式

入力は以下の形式で標準入力から与えられる。

$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 を出力せよ。

题目大意

有一张 $n$ 个点 $m$ 条边的无向连通图，已知 $k$ 条边为关键边，需要经过每条关键边恰好一次，非关键边无限制，判断能否满足条件。

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$
• 入力はすべて整数

Sample Explanation 1

頂点 $i$ を $v_i$, 辺 $j$ を $e_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$ をいずれもちょうど $1$ 回ずつ通っているため条件をみたします。

Sample Explanation 2

辺 $1,2,3$ をちょうど $1$ 回ずつ通るような歩道は存在しないため、No を出力します。