A city installs emergency sirens at some important intersections. When sirens start, the warning sound travels through roads, taking one minute to cross each road.
Find the minimum time after which every intersection has heard a siren. If some intersection can never hear any siren, print
The twist: starting BFS separately from every siren would repeat a lot of work.
The first line contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression — the number of intersections, roads, and siren locations.
The second line contains KaTeX can only parse string typed expression distinct integers — the intersections where sirens are installed.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, meaning there is a two-way road between intersections KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Print a single integer — the minimum time needed for every intersection to hear a siren, or KaTeX can only parse string typed expression if impossible.
Input
5 4 2
1 5
1 2
2 3
3 4
4 52Intersection KaTeX can only parse string typed expression is farthest from the nearest siren and hears it after KaTeX can only parse string typed expression minutes.
Example 2:
Input
6 3 1
1
1 2
2 3
4 5-1Intersections KaTeX can only parse string typed expression cannot hear a siren from intersection KaTeX can only parse string typed expression.