C - Path and Subsequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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}) の（連続とは限らない）部分列になる。

制約

  • 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 は連結

入力

入力は以下の形式で標準入力から与えられます。

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) の 2 通りであり、これらに対する (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

Score : 500 points

Problem Statement

We have a connected undirected graph G with N vertices and M edges. The vertices are numbered 1 to N. The i-th edge connects vertices U_i and V_i.

Additionally, we are given an integer sequence of length N, A=(A_1,\ A_2, \dots,\ A_N), and an integer sequence of length K, B=(B_1,\ B_2,\ \dots,\ B_K).

Determine whether G, A, and B satisfy the following condition.

  • For every simple path from vertex 1 to N in G, v=(v_1,\ v_2, \dots,\ v_k)\ (v_1=1,\ v_k=N), B is a (not necessarily contiguous) subsequence of (A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k}).

Constraints

  • 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
  • All values in the input are integers.
  • The given graph G is connected.

Input

The input is given from Standard Input in the following format:

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

Output

If the condition is satisfied, print Yes; otherwise, print No.

Sample Input 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

Sample Output 1

Yes

There are two simple paths from vertex 1 to vertex 6: (1,\ 2,\ 4,\ 6) and (1,\ 3,\ 5,\ 6). The (A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k}) corresponding to these paths are (1,\ 2,\ 5,\ 6) and (1,\ 4,\ 2,\ 6). Both of them have B=(1,\ 2,\ 6) as a subsequence, so the answer is Yes.

Sample Input 2

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

Sample Output 2

No

For a simple path (1,\ 2,\ 5) from vertex 1 to vertex 5, the (A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k}) is (1,\ 2,\ 2), which does not have B=(1,\ 3,\ 2) as a subsequence.

Sample Input 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

Sample Output 3

Yes