Minimum Intermediate Nodes in a Graph

You are given an undirected graph with n nodes and m edges. Your task is to determine the minimum number of hops (edges traversed) required to send a message from a source node s to a destination node t. If there is no possible path from s to t, output -1.

Note: The number returned is the count of edges in the shortest path. For example, if s = t, the answer is 0.

The input is provided via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The first line contains two integers n and m — the number of nodes and the number of edges, respectively.

The next m lines each contain two integers u and v representing an undirected edge connecting nodes u and v.

The last line contains two integers s and t — the source and destination nodes.

outputFormat

Output a single integer: the minimum number of edges (hops) from s to t. If t is unreachable from s, print -1.

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

3