配点 : $600$ 点

問題文

$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$ 回でも良い)通っていてもかまいません。

制約

• $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
• $i\neq j$ ならば $(U_i,V_i)\neq (U_j,V_j)$
• $G$ は連結
• $1 \leq K \leq M$
• $1 \leq x_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 を出力せよ。

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

Yes

頂点 $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$ 回ずつ通っているため条件をみたします。

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

No

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