Forbidden City
By Ricardo Oliveira, UFPR 
Brazil
By Ricardo Oliveira, UFPR Brazil
Your vacations are finally about to begin! To enjoy your deserved rest, you decided to travel from Curytyba to Riacho de Fevereiro, a great touristic city in the country.
There are N cities in the country, numbered from 1 to N. Curytyba is the city number C, and Riacho de Fevereiro is the city number R. Also, there are M routes. Each route connects two cities A and B, can be used to go from A to B or vice-versa, and takes exactly one hour to be transversed.
Everything is fine except one small detail: the mayor of the city Estadunido (city E), mr. Donaldo Trumpe, with a polemic decree, prohibited every citizen from Curytyba to enter his city! Hence, you must go to Riacho de Fevereiro avoiding passing by Estadunido.
Your task is to determine the minimum time needed, in hours, to go from Curytyba to Riacho de Fevereiro avoiding passing by Estadunido.
The input contains several test cases. The first line of each test case contains two integers N and M (3 ≤ N ≤ 1000, 1 ≤ M ≤ N(N-1)/2), the number of cities and routes, respectively. Each of the next M lines describe a route. Each line contains two integers A and B (1 ≤ A, B ≤ N, A≠B), indicating a route between cities A and B. The last line contains three integers C, R and E (1 ≤ C, R, E ≤ N,C≠R≠E), indicating Curytyba, Riacho de Fevereiro and Estatunido, respectively.
No route appears more than once in the input. It is guaranteed that it is possible to travel from city C to city R without going to city E using the routes given in the input.
The input ends with end-of-file (EOF).
For each test case, print a line containing the minimum time needed, in hours, to go from city C to city R without passing by city E.
| Input Sample | Output Sample |
|
3 1 |
1 |