Minimum New Edges to Connect

You are given an undirected graph with n nodes labeled 1 to n and an array edges, where edges[i] = [a, b] is an existing connection. The list may contain duplicate connections and self-loops.

You may add new connections between any pairs of nodes. Make the whole graph connected, with every node reachable from every other, using as few new connections as possible.

Return the minimum number of new connections required.

Examples

Example 1

Input: n = 4, edges = [[1,2],[3,4]]
Output: 1
Explanation: The graph has two connected components, {1,2} and {3,4}. One new connection between them (for example 2-3) connects everything.

Example 2

Input: n = 5, edges = []
Output: 4
Explanation: Five isolated nodes form five components; connecting k components needs k - 1 new connections.