Question
The Messenger’s Journey
In the Kingdom of Nodes, there are n cities, numbered from 0 to n−1, connected by a network of two-way roads. Each road takes exactly 1 minute to travel.
One day, the King sends a messenger from a source city called src to deliver an urgent message to another destination city called dst.
The messenger must take the shortest possible route, traveling from city to city along the roads.
Your task is to help the messenger by computing how many minutes it will take to reach the destination. If the destination cannot be reached, print -1.
Input
First line: Two integers n and m — the number of cities and the number of roads.
Next m lines: Each line contains two integers u and v — representing an undirected road between cities u and v.
Next line: Two integers src and dst — the source city and the destination city.
Next m lines: Each line contains two integers u and v — representing an undirected road between cities u and v.
Next line: Two integers src and dst — the source city and the destination city.
Output
Print the shortest distance to reach the destination city starting from the source city. If it's impossible print -1.
Example
Input :
5 4
0 2
0 3
0 1
2 4
2 1
Output:
2
Explanation:
Source is city 2, Destination is city 1.
Traversal starts from source city 2.
Level 1 from city 2: Cities 0 and 4
Level 2 from city 0: Cities 1 and 3
We reached city 3 at level 2. So, the shortest distance to reach from source city 2 to the destination city 1 is 2
5 4
0 2
0 3
0 1
2 4
2 1
Output:
2
Explanation:
Source is city 2, Destination is city 1.
Traversal starts from source city 2.
Level 1 from city 2: Cities 0 and 4
Level 2 from city 0: Cities 1 and 3
We reached city 3 at level 2. So, the shortest distance to reach from source city 2 to the destination city 1 is 2