题目描述

$N$ 頂点 $M$ 辺の連結無向グラフ $G$ があります。頂点には $1$ から $N$ の番号がついています。$i$ 番目の辺は頂点 $U_i,\ V_i$ を結びます。

また、長さ $N$ の整数列 $A=(A_1,\ A_2,\ \dots,\ A_N)$ 、および長さ $K$ の整数列 $B=(B_1,\ B_2,\ \dots,\ B_K)$ が与えられます。

$G,\ A,\ B$ が以下の条件を満たすか判定してください。

• $G$ における頂点 $1$ から $N$ への任意の単純パス $v=(v_1,\ v_2,\ \dots,\ v_k)\ (v_1=1,\ v_k=N)$ に対し、$B$ は $(A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k})$ の（連続とは限らない）部分列になる。

输入格式

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

$N$ $M$ $K$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_K$

输出格式

条件を満たす場合 Yes と、満たさない場合 No と出力してください。

题目大意

给定一个数组 $B$ 和一张点带点权的图，询问是否「所有从 $1$ 到 $n$ 的路径上依次经过的点的点权形成的序列」都含有 $B$ 作为子序列。

第一行输入 $n,m,k$，表示点数、边数、$B$ 数组的长度，接着 $m$ 行每行两个数 $u,v$ 表示图的一条边，下一行 $n$ 数表示点权数组，最后一行 $k$ 数表示 $B$ 数组。

若给出条件正确，输出 Yes；否则，输出 No。

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

Yes

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

No

10 20 3
5 6
5 10
5 7
3 5
3 7
2 6
3 8
4 5
5 8
7 10
1 6
1 9
4 6
1 2
1 4
6 7
4 8
2 5
3 10
6 9
2 5 8 5 1 5 1 1 5 10
2 5 1

Yes

提示

制約

• $2\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ K\ \leq\ N$
• $N-1\ \leq\ M\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ U_i\ <\ V_i\ \leq\ N$
• $i\ \neq\ j$ ならば $(U_i,\ V_i)\ \neq\ (U_j,\ V_j)$
• $1\ \leq\ A_i,\ B_i\ \leq\ N$
• 入力される値はすべて整数
• 与えられるグラフ $G$ は連結

Sample Explanation 1

頂点 $1$ から頂点 $6$ への単純パスは $(1,\ 2,\ 4,\ 6),\ (1,\ 3,\ 5,\ 6)$ の $2$ 通りであり、これらに対する $(A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k})$ はそれぞれ $(1,\ 2,\ 5,\ 6),\ (1,\ 4,\ 2,\ 6)$ です。 これらはいずれも $B=(1,\ 2,\ 6)$ を部分列に持つので答えは Yes です。

Sample Explanation 2

頂点 $1$ から頂点 $5$ への単純パスである $(1,\ 2,\ 5)$ に対する $(A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k})$ は $(1,\ 2,\ 2)$ であり、これは $B=(1,\ 3,\ 2)$ を部分列に持ちません。