AT_arc150_c [ARC150C] Path and Subsequence

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

## 限制条件 - $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 翻译