Question
The Traveler’s Shortest Route
In a vast kingdom, there are n cities numbered from 0 to n−1, connected by a network of undirected roads. Each road directly connects two cities and takes exactly one minute to travel.
One day, a traveler starts their journey from a source city (src) and wants to reach a destination city (dst) as quickly as possible.
Your task is to help the traveler find the shortest route — the minimum number of roads they must cross to reach their destination.
If the traveler can’t reach the destination city at all, return -1.
Input
First line contains two integers n and m representing number of cities and number of roads.
Next m lines will contain two space separated integers u and v representing undirected roads between them.
Next line will contains two integers src and dst representing the source city and the destination city.
Next m lines will contain two space separated integers u and v representing undirected roads between them.
Next line will contains two integers src and dst representing the source city and the destination city.
Output
Return the shortest distance to reach the destination node starting from the source node. If it's impossible return -1.
Example
Input :
5 4
0 2
0 3
0 1
2 4
2 1
Output:
2
Explanation:
There are 5 cities and 4 roads.
The traveler starts at city 2 and wants to reach city 1.
From 2, the traveler can go to 0 and 4 (Level 1).
From 0, they can reach 1 and 3 (Level 2).
The destination 1 is reached in 2 steps.
Hence, the shortest distance from city 2 to 1 is 2.
5 4
0 2
0 3
0 1
2 4
2 1
Output:
2
Explanation:
There are 5 cities and 4 roads.
The traveler starts at city 2 and wants to reach city 1.
From 2, the traveler can go to 0 and 4 (Level 1).
From 0, they can reach 1 and 3 (Level 2).
The destination 1 is reached in 2 steps.
Hence, the shortest distance from city 2 to 1 is 2.