问题描述

我们有一个连通的无向图$G$，有$N$个顶点和$M$条边。顶点编号从$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})$的（不一定连续的）子序列。

约束条件

• $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$
• $(U_i,\\ V_i) \neq (U_j,\\ V_j)$ if $i \neq j$.
• $1 \leq A_i,\\ B_i \leq N$
• 输入中的所有值都是整数。
• 给定的图$G$是连通的。

输入

输入以以下格式从标准输入给出：

$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。

示例输入 1

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

示例输出 1

Yes

从顶点$1$到顶点$6$，有两条简单路径：$(1,\\ 2,\\ 4,\\ 6)$和$(1,\\ 3,\\ 5,\\ 6)$。与这些路径对应的$(A_{v_1},\\ A_{v_2},\\ \\dots,\\ A_{v_k})$分别为$(1,\\ 2,\\ 5,\\ 6)$和$(1,\\ 4,\\ 2,\\ 6)$。它们都有$B=(1,\\ 2,\\ 6)$作为子序列，因此答案是Yes。

示例输入 2

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

示例输出 2

No

对于从顶点$1$到顶点$5$的简单路径$(1,\\ 2,\\ 5)$，$(A_{v_1},\\ A_{v_2},\\ \\dots,\\ A_{v_k})$是$(1,\\ 2,\\ 2)$，它没有$B=(1,\\ 3,\\ 2)$作为子序列。

示例输入 3

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

示例输出 3

Yes