Fewest connections between two cities
A travel app for a regional airline wants to show passengers the route with the fewest flights. The airline flies direct routes between cities numbered 1 to n, and every route works in both directions. Ticket prices and flight lengths do not matter here, only how many flights a trip needs.
Task: the first line holds n and m (2 ≤ n ≤ 100, 0 ≤ m ≤ 300). Each of the next m lines holds two different cities a b joined by a direct route. The last line holds the start city s and the destination city t (different). Print the minimum number of flights needed to travel from s to t, or -1 if the trip is impossible.
Sample test
Input
6 6 1 2 2 3 3 6 1 4 4 5 5 6 1 6
Expected output
3
Your answer is also checked against 4 hidden tests.
Need a hint?
Explore the network in rings: first everything one flight away, then two flights away, and so on.
Log in or create a free account to run your code, submit and earn points.
Run your code to see the output here. Ctrl + Enter also runs it.