Loading...
Loading...
Loading...
Computers are joined by two-way cables. A loop is a route that leaves a computer and comes back to it using distinct cables. Print the number of cables in the shortest loop, or -1 if there is no loop.
Example 1
Input
5 5 0 1 1 2 2 0 2 3 3 4
Output
3
The triangle 0, 1, 2 has 3 cables.
Example 2
Input
4 3 0 1 1 2 2 3
Output
-1
Try the problem first. Open one hint at a time.
Run BFS from every node.
An edge to an already reached node that is not the parent closes a loop of length distance plus distance plus 1.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor