Shortest Path in Caves

You are given a network of caves connected by bidirectional tunnels. Each cave is identified by a positive integer. Your task is to determine the minimum number of tunnels that need to be traversed to go from a starting cave to a target cave. If there is no possible route, output -1.

In formal terms, if you model the caves as nodes and tunnels as edges, you need to find the shortest path between two given nodes. The distance is defined as the number of tunnels traversed. Mathematically, if d represents the number of tunnels, then the answer is computed as \( d = \text{number of tunnels traversed} \).

inputFormat

The first line contains two space-separated integers: n and m, where n is the total number of caves and m is the number of tunnels.

The next m lines each contain two integers representing a tunnel between two caves.

The last line contains two integers: start and target, the identifiers of the starting and target caves respectively.

outputFormat

Output a single integer representing the minimum number of tunnels needed to go from the starting cave to the target cave. If no path exists, output -1.

6 5
1 2
2 3
3 4
1 5
5 6
1 4

3