Problem E
Escape Plan
BaoBao, one of the most famous monster hunters, wakes up in the middle of Heltion City dominated by monsters. Having troubles remembering what has happened, BaoBao decides to escape from this horrible city as soon as possible. Despite having no weapon, he luckily puts his hand on a map in his right pocket, which contains valuable information that can possibly help him find a way out.
According to the map, Heltion City is composed of
However, it’s not an easy task for BaoBao to escape since
monsters are everywhere in the city! For all
As BaoBao doesn’t know which paths will be blocked, please help him calculate the shortest time he can escape from the city in the worst case.
Input
There are multiple test cases. The first line of the input
contains an integer
The first line contains three integers
The second line contains
The third line contains
For the following
It’s guaranteed that the total sum of
Output
For each case output one line containing one integer. If BaoBao can get to some exit in the worst case, output the shortest possible time cost; Otherwise if BaoBao cannot get to any exit in the worst case, output “-1” (without quotes) instead.
Sample Input 1 | Sample Output 1 |
---|---|
2 3 4 1 3 1 1 1 1 2 1 1 2 2 2 3 1 2 3 2 3 2 2 2 3 2 0 0 1 2 1 1 3 1 |
4 -1 |