Minimum Cargo Transfers

You are given a network of n warehouses, numbered from 1 to n, connected by m bidirectional roads. Each road connects two distinct warehouses and represents a possible direct cargo transfer.

Your task is to determine the minimum number of cargo transfers needed to move goods from a starting warehouse s to a destination warehouse t. If there is no possible route between s and t, output -1.

The number of transfers is equivalent to the number of edges in the shortest path from s to t. In mathematical terms, if we denote the distance by \(d(s,t)\), then the required number of transfers is \(d(s,t)\), with the convention that if no path exists, \(d(s,t) = -1\).

inputFormat

The input is given via stdin with the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm
 s t

• The first line contains two integers: \(n\) (the number of warehouses) and \(m\) (the number of roads).
• Each of the following \(m\) lines contains two integers \(u\) and \(v\), representing a road connecting warehouses \(u\) and \(v\).
• The last line contains two integers: \(s\) (the starting warehouse) and \(t\) (the destination warehouse).

outputFormat

Output via stdout a single integer which is the minimum number of cargo transfers needed to move goods from warehouse \(s\) to warehouse \(t\). If there is no valid route, output \(-1\).

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

3