Marisa is being chased by k Alice’s dolls. What Marisa has done to Alice, I will leave that to your imagination…
Marisa is now at vertex 1 of an connected, 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. The dolls always move optimally to chase Marisa.
Marisa can escape these dolls after reaching vertex n. If she encounters x dolls at a vertex (even at vertex n), she must fight them and they will stop chasing her. This action costs her x energy, but does not take time.
What is the minimum amount of energy she must spend to escape?
Input:
6 6 2
2 4
1 2
1 3
3 4
2 4
4 5
3 6
Output:
1