995. Cables You Can Move
An office has n computers and m cables. Each cable joins two different
computers. A pair may be cabled more than once, and a cable may join two computers that were
already reachable from one another.
You may unplug one end of any existing cable and plug it into any computer you like. That counts as ONE move. No new cable may be bought.
Print the fewest moves that make every computer reachable from every other, or -1 if it
cannot be done at all.
4 computers, cables (1 2)(1 3)(2 3)(3 4) -> 0 already connected
6 computers, cables (1 2)(1 3)(2 3)(4 5)(4 6) -> 1 one spare cable, one gap
6 computers, cables (1 2)(3 4)(5 6) -> -1 three pieces, no spare cable
4 computers, cables (1 2)(1 2)(1 2) -> 2 two spares, but only three
computers are cabled at all
Careful with the last one: three cables all join the same pair, so computers 3 and 4 are untouched, the office is in three pieces, and two moves are needed. Two spare cables exist, so it is possible.
## What most people try first
Count the pieces and subtract one. That is problem 396, and it is the right answer only when
there are enough cables to spare. With m fixed there may not be: the third example needs
two moves and has nothing to move.
## Count the pieces AND the spares in the same sweep
``` pieces = n spare = 0 for each cable (u, v): if find(u) != find(v): merge, pieces = pieces - 1 else: spare = spare + 1
need = pieces - 1 answer = need if spare >= need else -1 ```
## Why the spare count does not depend on the order
The sweep calls a cable spare when its two ends were already together. That looks like it
could depend on which cable is read first, and it does not: whatever the order, the cables
that DO merge are exactly a spanning forest, and a forest over n computers in pieces
components has exactly n - pieces edges. So spare always ends at m - (n - pieces),
which is fixed by the graph alone.
## Why pieces - 1 moves are both enough and necessary
Necessary: one move changes one endpoint of one cable, which can bring at most two pieces
together, so it lowers the piece count by at most one. Going from pieces to 1 therefore
needs at least pieces - 1 moves.
Enough: take any spare cable. Removing it leaves the office in the same pieces pieces,
because it was not holding anything together. Plug one of its ends into a computer in a
different piece and the count drops by one. Repeat while spares last.
## The boundary
A single computer is already connected: pieces is 1, need is 0, and the answer is 0 even
though there is nothing to move. A solution that starts by requiring at least one spare gets
this wrong.
## Overflow
Nothing here overflows. n and m both stay at 2 * 10^5, and spare is at most m,
so every quantity fits in a signed 32 bit integer, whose maximum is 2147483647.
## Cross-reference
Problem 396 prints pieces - 1 with no cable budget at all. It is this problem's answer
whenever spares are plentiful, and its wrong answer whenever they are not, which is exactly
the third example.
## Cost
Time O((n + m) alpha(n)). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ m ≤ 200000` - `1 ≤ u, v ≤ n` - `u` is never equal to `v`. - The same pair may be cabled more than once.
Input
The first line contains two integers n and m.
Each of the next m lines contains two integers u and v, the two computers one cable joins.
Output
Print one integer: the fewest moves that connect every computer, or -1 if no sequence of moves can. Print it alone on one line, with no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.