You are given a graph with n vertices and m edges.
You can remove one edge from anywhere and add that edge between any two vertices in one operation.
Find the minimum number of operation that will be required to make the graph connected.
If it is not possible to make the graph connected, return -1.
 
Example 1: 
Input:
n=4
m=3
Edge=[ [0, 1] , [0, 2] , [1, 2] ]
Output:
1
Explanation:
Remove edge between vertices 1 and 2 and add between vertices 1 and 3.
 
Example 2:
Input:
n=6
m=5
Edge=[ [0,1] , [0,2] , [0,3] , [1,2] , [1,3] ]
Output:
2
Explanation:
Remove edge between (1,2) and(0,3) and add edge between (1,4) and (3,5)
 
 
Your Task:
You don't need to read or print anything. Your task is to complete the function Solve() which takes an integer n denoting no. of vertices and a matrix edge[][] denoting the the edges of graph and return the minimum number of operation to connect a graph
 
Constraints:
1<=n<=10^{5}
0<=m<=10^{5}
0<=edge[i][0],edge[i][1]

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def Solve(self, n, adj):

        # Code here

Solutions:
class UnionFind:

	def __init__(self):
		self.parent = {}
		self.rank = {}

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a == b:
			return
		if self.rank[a] == self.rank[b]:
			self.rank[a] += 1
		elif self.rank[b] > self.rank[a]:
			(a, b) = (b, a)
		self.parent[b] = a

	def find(self, x):
		if x not in self.parent:
			self.parent[x] = x
			self.rank[x] = 0
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

class Solution:

	def Solve(self, n, adj):
		ds = UnionFind()
		cntExtras = 0
		for ele in adj:
			u = ele[0]
			v = ele[1]
			if ds.find(u) == ds.find(v):
				cntExtras += 1
			else:
				ds.union(u, v)
		cntComps = 0
		for i in range(n):
			if ds.find(i) == i:
				cntComps += 1
		ans = cntComps - 1
		if cntExtras >= ans:
			return ans
		else:
			return -1


class DisjointSet:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.size = [1 for i in range(n + 1)]

	def findUParent(self, node):
		if node == self.parent[node]:
			return node
		self.parent[node] = self.findUParent(self.parent[node])
		return self.parent[node]

	def unionByRank(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.rank[up_u] < self.rank[up_v]:
			self.parent[up_u] = up_v
		elif self.rank[up_v] < self.rank[up_u]:
			self.parent[up_v] = up_u
		else:
			self.parent[up_v] = up_u
			self.rank[up_u] += 1
		return

	def unionBySize(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.size[up_u] < self.size[up_v]:
			self.parent[up_u] = up_v
			self.size[up_v] += self.size[up_u]
		else:
			self.parent[up_v] = up_u
			self.size[up_u] += self.size[up_v]
		return

class Solution:

	def Solve(self, n, adj):
		edges = adj
		ds = DisjointSet(n)
		nc = 0
		extra = 0
		for edge in edges:
			u = edge[0]
			v = edge[1]
			if ds.findUParent(u) != ds.findUParent(v):
				ds.unionBySize(u, v)
			else:
				extra += 1
		for i in range(n):
			if ds.parent[i] == i:
				nc += 1
		if extra >= nc - 1:
			return nc - 1
		else:
			return -1


class Solution:

	def findparent(self, node, parent):
		if parent[node] == node:
			return node
		parent[node] = self.findparent(parent[node], parent)
		return parent[node]

	def unite(self, start, end, parent, a, b):
		parent[max(a, b)] = min(a, b)

	def Solve(self, n, adj):
		extra = 0
		parent = [i for i in range(n)]
		for (start, end) in adj:
			a = self.findparent(start, parent)
			b = self.findparent(end, parent)
			if a == b:
				extra += 1
				continue
			self.unite(start, end, parent, a, b)
		comp = 0
		for i in range(n):
			if i == parent[i]:
				comp += 1
		if extra >= comp - 1:
			return comp - 1
		return -1