There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network.

You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.

Return the minimum number of times you need to do this in order to make all the computers connected. If it is not possible, return -1.

&nbsp;
Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.


Example 2:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
Output: 2


Example 3:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
Output: -1
Explanation: There are not enough cables.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 105
	1 &lt;= connections.length &lt;= min(n * (n - 1) / 2, 105)
	connections[i].length == 2
	0 &lt;= ai, bi &lt; n
	ai != bi
	There are no repeated connections.
	No two computers are connected by more than one cable.


class Solution(object):
    def __init__(self):
        self.parents = []
        self.count = []

    def makeConnected(self, n, connections):
        """
        :type n: int
        :type connections: List[List[int]]
        :rtype: int
        """
        if len(connections) < n-1:
            return -1
        self.parents = [i for i in range(n)]
        self.count = [1 for _ in range(n)]
        for connection in connections:
            a, b = connection[0], connection[1]
            self.union(a, b)
        return len({self.find(i) for i in range(n)}) - 1

    def find(self, node):
        """
        :type node: int
        :rtype: int
        """
        while(node != self.parents[node]):
            node = self.parents[node];
        return node

    def union(self, a, b):
        """
        :type a: int
        :type b: int
        :rtype: None
        """
        a_parent, b_parent = self.find(a), self.find(b)
        a_size, b_size = self.count[a_parent], self.count[b_parent]

        if a_parent != b_parent:
            if a_size < b_size:
                self.parents[a_parent] = b_parent
                self.count[b_parent] += a_size
            else:
                self.parents[b_parent] = a_parent
                self.count[a_parent] += b_size
class Solution {
    public int makeConnected(int n, int[][] connections) {
        int m = connections.length;
        if(m < n - 1) return -1;
        UnionFind uf = new UnionFind(n);
        
        for(int[] connection: connections){
            uf.union(connection[0], connection[1]);
        }
        return uf.getIsolated();
    }
}
class UnionFind{
    int[] root;
    int[] rank;
    int isolated;
    public UnionFind(int n){
        root = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++){
            root[i] = i;
            rank[i] = 1;
        }
        isolated = 0;
    }
    public int find(int x){
        if(root[x] != x) root[x] = find(root[x]);
        return root[x];
    }
    public void union(int x, int y){
        int rootx = find(x);
        int rooty = find(y);
        if(rootx == rooty) return;
        if(rank[rootx] > rank[rooty]){
            root[rooty] = rootx;
        }else if(rank[rootx] < rank[rooty]){
            root[rootx] = rooty;
        }else{
            root[rootx] = rooty;
            rank[rooty] += 1;
        }
    }
    public int getIsolated(){
        for(int i = 0; i < root.length; i ++){
            if(root[i] == i) isolated++;
        }
        return isolated - 1;
    }
}
class Solution {
public:

	// Union Find Approach

	vector<int> root;

	int find(int node){
		if(root[node] != node){
			return find(root[node]);
		}
		return node;
	}

	int makeConnected(int n, vector<vector<int>>& connections) {

		int m = connections.size();

		if(m < n-1){
			return -1;
		}

		for(int i=0 ; i<n ; i++){
			root.push_back(i);
		}

		for(int i=0 ; i<m ; i++){

			int v1 = connections[i][0];
			int v2 = connections[i][1];

			int r1 = find(v1);
			int r2 = find(v2);

			if(r1 != r2){
				root[r1] = r2;
			}
		}

		int ans = 0;
		for(int i=0 ; i<n ; i++){
			if(root[i] == i){
				ans++;
			}
		}

		return ans - 1;
	}
};
/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
class UnionFind {
    constructor(n) {
        this.root = new Array(n).fill().map((_, index)=>index);
        this.components = n;
    }
    find(x) {
        if(x == this.root[x]) return x;
        return this.root[x] = this.find(this.root[x]);
    }
    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if(rootX != rootY) {
            this.root[rootY] = rootX;
            this.components--;
        }
    }
}
var makeConnected = function(n, connections) {
    // We need at least n - 1 cables to connect all nodes (like a tree).
    if(connections.length < n-1) return -1;
    const uf = new UnionFind(n);
    for(const [a, b] of connections) {
        uf.union(a, b);
    }
    return uf.components - 1;
};
Number of Operations to Make Network Connected