[40%]
One day, a zombie virus outbreak in your city.
To survive, you need to migrate to another safe city.
However, you can only traverse one city to another via roads,
otherwise safety can not be guaranteed.
Also, to minimize the risk during your trip, you wish
to minimize the distanse of your path.
Now, given a map with N cities with M roads.
Find the minimum possible distance between you and your destination.
Assume Roads are bidirection (that is, if there is a road between city A and B.
You can go either from A to B or from B to A.) and all with distance 1.
Hint: BFS
There will be several test cases. Input will terminate with an EOF.
Each test case contains several lines.
First line contains four integer S, E, N, M. Denoting your starting city number,
your destination city number, total number of cities and total number of roads.
For the next M lines, each lines contains two integer A, B. Which means there
is a road between city number A and city number B.
Cities are numbered from 1 to N.
Assume there will be no duplicate roads.
2<=N<=1000, S!=E
0<=M<=N^2
For each test case, output a line with the minimum possible distance between you and your destination.
If it is impossible to get to your desitination city, output -1.