A data center has n servers, numbered 1 through n, joined by m network cables. Each cable directly connects two distinct servers. In one operation you may unplug any one existing cable and plug it back in between any two servers you like. Determine the minimum number of operations needed to make the whole rack connected (every server reachable from every other), or report -1 if it is impossible.
Input format
- Line 1: two integers
nandm. - Next
mlines: two integersuandv(1-indexed,u != v), a cable between serversuand . The same pair may appear more than once.
Output format
A single integer: the minimum number of operations, or -1 if the rack cannot be fully connected.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 1 <= u, v <= n and u != v