Escape from... dolls 2 - MarisaOJ: Marisa Online Judge

Marisa is again being chased by

k

$k$ Alice's dolls. Marisa is now at vertex

1

$1$ of an undirected graph of

n

$n$ vertices and

m

$m$ edges. The

i^{t h}

$i^{th}$ doll is at vertex

A_{i}

$A_i$ . Marisa and dolls can move to any adjacent vertex in

1

$1$ unit of time. Marisa can escape these dolls after reaching one of the

p

$p$ special vertices

S_{1}, S_{2}, . . ., S_{p}

$S_1,S_2,...,S_p$ . She does not want to encounter any doll on her path (encountering the dolls at the special vertices still counts). Determine if there exists a path that **in any case**, Marisa won't meet any doll. ### Input - The first line contains 4 integers

n, m, k, p

$n, m, k, p$ . - The second line contains

k

$k$ integers

A_{i}

$A_i$ . - The third line contains

p

$p$ integers

S_{i}

$S_i$ . - The next

m

$m$ lines, each line contains 2 integers

u, v

$u, v$ , there is an edge between

u

$u$ and

v

$v$ . ### Output - Print

Y E S

$YES$ if such a path exists,

N O

$NO$ otherwise. ### Constraints -

1 \leq p, k \leq n \leq 10^{5}

$1 \le p,k \le n \le 10^5$ . -

1 \leq m \leq 10^{5}

$1 \le m \le 10^5$ . -

1 \leq u, v, A_{i} \leq n

$1 \le u, v, A_i \le n$ . ### Example Input:

6621256121334244536

$6 6 2 1 2 5 6 1 2 1 3 3 4 2 4 4 5 3 6$

Output:

Y E S

$YES$

Multisource BFS / Dijkstra
	Rough ocean
	Restaurant
	Escape from... dolls 2
	Power plant
	Iceberg

Topic

Graph

Shortest path

Rating

1400

Solution (0)

Solution