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