分数: 500 点
问题陈述
我们有一个连通的无向图 G 与 N 顶点和 M 边缘。顶点已编号 1 to 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 满足以下条件。
- 对于从顶点开始的每个简单路径 1 to N in G, 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,\ 2,\ 5) 从顶点 1 到顶点 5, (A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k}) is (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