题目描述

有一个包含 $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。

样例 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

输出

Yes

样例 2

输入

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

输出

No

样例 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

输出

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$ 是连通的

样例解释 1

从顶点 $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

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

由 ChatGPT 4.1 翻译