路径与子序列

时间限制：2s
空间限制：1024MB

题目描述

有一个含 $N$ 个顶点、$M$ 条边的连通无向图 $G$，顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。另给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 与长度为 $K$ 的整数序列 $B=(B_1,B_2,\ldots,B_K)$。

判断下列条件是否成立：对于图中从顶点 $1$ 到顶点 $N$ 的任意一条简单路径 $v=(v_1,v_2,\ldots,v_t)$，其中 $v_1=1,v_t=N$，序列 $B$ 都是 $(A_{v_1},A_{v_2},\ldots,A_{v_t})$ 的子序列。子序列中的元素不要求连续。

输入格式

第一行三个整数 $N,M,K$。

接下来 $M$ 行，第 $i$ 行两个整数 $U_i,V_i$，表示一条无向边。

下一行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

最后一行 $K$ 个整数 $B_1,B_2,\ldots,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

样例输入 2

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

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

样例输出 3

Yes

数据范围

• $2\le N\le10^5$；
• $1\le K\le N$；
• $N-1\le M\le2\times10^5$；
• $1\le U_i<V_i\le N$，且没有重边；
• $1\le A_i,B_i\le N$；
• 图 $G$ 连通。