Problem statement
You are given an undirected, unweighted graph with N vertices and M edges. You must travel from vertex S to vertex T while visiting vertex K at least once. Find the minimum total number of edges needed. You may revisit vertices and edges. If no valid route exists, output -1. Self-loops and repeated edges are allowed.
Input format
First line: N M. Next M lines: U V. Last line: S K T.
Output format
Print the minimum number of edges needed to travel from S to T through K, or -1 if impossible.
Constraints
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
- 1 ≤ U, V, S, K, T ≤ N
Sample input
6 6 1 2 2 3 3 4 4 5 2 5 5 6 1 4 6
Sample output
5
Sample explanation
The route 1 → 2 → 3 → 4 → 5 → 6 visits checkpoint 4 and uses five edges. The two shortest legs have lengths 3 and 2.
Need a hint?
BFS from S and BFS from K. Answer = dist(S,K) + dist(K,T), provided both distances exist. Expected complexity: O(N + M).