Avoid Cities :
Difficulty Level : Easy
Submissions : 9000
Asked In :
Marks :10
: 68 | : 19
There are $$$N$$$ cities with $$$M$$$ bi-directional roads between them. You want to travel from a given source city to target city. But there are some cities that you cannot visit because they are cursed.
Find the smallest number of roads that you should take to complete your travel and output it. If it is not possible to do so output $$$-1$$$.
$$$1 \leq N \leq 10^5$$$ $$$0 \leq M \leq 2 \times 10^5$$$
The first line contains two integers $$$N$$$ and $$$M$$$ denoting the number of cities and the number of roads respectively.
The second line contains two integers: source and target.
The third line contains $$$N$$$ integers which are either $$$0$$$ or $$$1$$$ denoting whether each city is cursed or not. ($$$1$$$ means that the city is cursed.)
Finally, there are $$$M$$$ lines containing $$$2$$$ integers each $$$u$$$ and $$$v$$$ denoting that there is a road between city $$$u$$$ and city $$$v$$$.
Output the smallest number of roads that you should take to complete your travel and output it. If it is not possible to do so output $$$-1$$$.
5 5 0 2 0 1 0 0 0 0 1 1 2 0 3 3 4 4 2
3
