Finding Midpoint Caves

Luke has discovered a network of caves connected by bidirectional passages. He needs your help to determine the number of caves on the shortest path from a specified starting cave s to a target cave t. In this problem, the network is represented as an undirected graph with n caves (vertices) and m passages (edges). Your task is to determine the number of caves encountered along the shortest path, including both the starting and target caves.

Note: It is guaranteed that a path exists between s and t.

The shortest path length is defined as the minimum number of vertices that need to be visited from s to t. Formally, if the shortest path is represented as a sequence of vertices \(v_1, v_2, \dots, v_k\) with \(v_1 = s\) and \(v_k = t\), you should output \(k\).

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains two space-separated integers \(n\) and \(m\), where \(n\) is the number of caves and \(m\) is the number of passages.
• The next \(m\) lines each contain two space-separated integers \(a\) and \(b\), denoting there is a bidirectional passage between cave \(a\) and cave \(b\).
• The last line contains two space-separated integers \(s\) and \(t\), the starting cave and the target cave.

Constraints:

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 10^5\)
• \(1 \leq a, b, s, t \leq n\)

outputFormat

Output a single integer representing the number of caves on the shortest path from cave \(s\) to cave \(t\) (including both \(s\) and \(t\)). The output should be written to standard output (stdout).

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

4