8399: ABC286 —— G - Unique Walk
[Creator : ]
Description
You are given a simple connected undirected graph G with N vertices and M edges.
The vertices of G are numbered vertex 1, vertex 2, ……, and vertex N, and its edges are numbered edge 1, edge 2, ……, and edge M. Edge i connects vertex $U_i$ and vertex $V_i$.
You are also given a subset of the edges: $S={x_1,x_2,…,x_K}$.
Determine if there is a walk on G that contains edge x exactly once for all x∈S.
The walk may contain an edge not in S any number of times (possibly zero).
What is a walk?
A walk on an undirected graph G is a sequence consisting of k vertices (k is a positive integer) and (k−1) edges occurring alternately, $v_1,e_1,v_2,…,v_{k−1},e_{k−1},v_k$, such that edge $e_i$ connects vertex $v_i$ and vertex $v_{i+1}$. The sequence may contain the same edge or vertex multiple times. A walk is said to contain an edge x exactly once if and only if there is exactly one 1≤i≤k−1 such that $e_i=x$.
The vertices of G are numbered vertex 1, vertex 2, ……, and vertex N, and its edges are numbered edge 1, edge 2, ……, and edge M. Edge i connects vertex $U_i$ and vertex $V_i$.
You are also given a subset of the edges: $S={x_1,x_2,…,x_K}$.
Determine if there is a walk on G that contains edge x exactly once for all x∈S.
The walk may contain an edge not in S any number of times (possibly zero).
What is a walk?
A walk on an undirected graph G is a sequence consisting of k vertices (k is a positive integer) and (k−1) edges occurring alternately, $v_1,e_1,v_2,…,v_{k−1},e_{k−1},v_k$, such that edge $e_i$ connects vertex $v_i$ and vertex $v_{i+1}$. The sequence may contain the same edge or vertex multiple times. A walk is said to contain an edge x exactly once if and only if there is exactly one 1≤i≤k−1 such that $e_i=x$.
Input
The input is given from Standard Input in the following format:
$N\ M$
$U_1\ V_1$
$U_2\ V_2$
$⋮$
$U_M\ V_M$
$K$
$x_1\ x_2\ …\ x_K$
$N\ M$
$U_1\ V_1$
$U_2\ V_2$
$⋮$
$U_M\ V_M$
$K$
$x_1\ x_2\ …\ x_K$
Output
Print Yes if there is a walk satisfying the condition in the Problem Statement; print No otherwise.
Constraints
$2≤N≤2×10^5$
$N−1≤M≤min(\frac{N(N−1)}{2},2×10^5)$
$1≤U_i<V_i≤N$
If $i\neq j$, then $(U_i,V_i)\neq (U_j,V_j)$.
G is connected.
$1≤K≤M$
$1≤x_1<x_2<⋯<x_K≤M$
All values in the input are integers.
$N−1≤M≤min(\frac{N(N−1)}{2},2×10^5)$
$1≤U_i<V_i≤N$
If $i\neq j$, then $(U_i,V_i)\neq (U_j,V_j)$.
G is connected.
$1≤K≤M$
$1≤x_1<x_2<⋯<x_K≤M$
All values in the input are integers.
Sample 1 Input
6 6
1 3
2 3
3 4
4 5
4 6
5 6
4
1 2 4 5
Sample 1 Output
Yes
The walk $(v_1,e_1,v_3,e_3,v_4,e_4,v_5,e_6,v_6,e_5,v_4,e_3,v_3,e_2,v_2)$ satisfies the condition, where $v_i$ denotes vertex $i$ and $e_i$ denotes edge $i$.
In other words, the walk travels the vertices on G in this order: 1→3→4→5→6→4→3→2.
This walk satisfies the condition because it contains edges 1, 2, 4, and 5 exactly once each.
In other words, the walk travels the vertices on G in this order: 1→3→4→5→6→4→3→2.
This walk satisfies the condition because it contains edges 1, 2, 4, and 5 exactly once each.
Sample 2 Input
6 5
1 2
1 3
1 4
1 5
1 6
3
1 2 3
Sample 2 Output
No
There is no walk that contains edges 1, 2, and 3 exactly once each, so No should be printed.