Lamia also wants to find the shortest possible loop route that a patrol car can take that necessarily passes back through a specific checkpoint intersection. Given an undirected graph with N nodes and M edges, and a specific node K, print the length of the SHORTEST cycle that passes through node K, or -1 if no such cycle exists. (Hint: try BFS from each neighbor of K, or think about removing K's edges one at a time and running BFS between its neighbors.)
Input
Line1: N M K. Next M lines: u v.
Output
Shortest cycle length through K, or -1.
Constraints
1 ≤ N ≤ 500, 0 ≤ M ≤ 2000
Sample Input
4 4 1 1 2 2 3 3 4 4 1
Sample Output
4
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.