An office has n computers numbered 0 .. n-1. The list cables holds pairs [a, b] (with a != b): a network cable plugged directly between computers a and b. Two computers can talk if a chain of cables joins them.
In one move you unplug any existing cable and plug it back in between any two computers of your choice. Return the minimum number of moves needed so that every computer can talk to every other one, or -1 if that is impossible no matter how the cables are rearranged. Two cables may join the same pair of computers.
Examples
Input: n = 4, cables = [[0, 1], [0, 2], [1, 2]]
Output: 1
Explanation: one of the three cables in the triangle is redundant; move it to reach computer 3.
Input: n = 5, cables = [[0, 1], [1, 2]]
Output: -1
Explanation: connecting 5 computers needs at least 4 cables.
Input: n = 6, cables = [[0, 1], [0, 1], [2, 3], [2, 3], [4, 5]]
Output: 2
Constraints
1 <= n <= 10**4,0 <= len(cables) <= 2 * 10**4,0 <= a, b < n- Target: O((n + C) * alpha(n)) time.
Goals
- Relate the number of moves to the number of connected components
- Rule out impossible cases by counting cables before doing any work