Marisa is again being chased by k Alice’s dolls.
Marisa is now at vertex 1 of an undirected graph of n vertices and m edges. The ith doll is at vertex Ai. Marisa and dolls can move to any adjacent vertex in 1 unit of time.
Marisa can escape these dolls after reaching one of the p special vertices S1,S2,…,Sp. 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.
YES
if such a path exists, NO
otherwise.Input:
6 6 2 1
2 5
6
1 2
1 3
3 4
2 4
4 5
3 6
Output:
YES