The police caught the thief

In a country, a thief stole the king's jewels, the king was very angry, asked the police to seize he as soon as possible,the thief was afraid of stealing king's jewels, to prevent the police from seizing , he decided to randomly walk in the nearby cities or stay put a day, the police found the thief at “t” City and himself at “s” city, and received information (police can always know where is the thief ). he decided to quickly caughting the thief.The police want to know about how long to seize the thief in the worst situation. This country can be seen as a undirected graph, there are N cities, M edges .As we know the police are very smart and quick; a day he will go to a closer city to the thief, if there are several cities, he will choose the smallest label city, if the thief is not in that city he will continue to go to the next one closer city to the thief . If they have several cities, they will select the smallest label city too, in other word ,a day police can move two steps. Suppose the police move first, please tell the police how many days to seize the thief in worst situation.

Multi test cases;  
The first line consist of the two integers N, M (1 ≤ N, M ≤ 1000), separated by spaces; The second line consist of two integers is s, t, respectively, the initial city where the police and thieve The third line to the M +1 line input two integers a and b ,there is one edge between city a and b.,
Processing to the end of the file;

print a line contains a integer respect the days in worst situation;

4 3 
1 4 
1 2 
2 3 
3 4 
9 9 
9 3 
1 2 
2 3 
3 4 
4 5 
3 6 
4 6 
4 7 
7 8 
8 9 

2
3

2010 ACM-ICPC Multi-University Training Contest（17）——Host by ZSTU