This problem is to implement disjoint set union. There will be 2 incomplete functions namely union and find. You have to complete these functions. 
Union: Join two subsets into a single set.
isConnected: Determine which subset a particular element is in. This can be used for determining if two elements are in same subset.
Example 1:
Input:
N = 5
q = 4
Queries = 
Union(1,3)
isConnected(1,2)
Union(1,5)
isConnected(3,5)
Output:
0
1
Explanation: Initially all nodes 1 2 3 4 5
are not connected. 
After Union(1,3), node 1 and 3 will be
connected.
When we do isConnected(1,2),  as node 1
and 2 are not connected it will return 0.
After Union(1,5), node 1 and 5 will be
connected.
When we do isConnected(3,5),  as node
1 and 3 are connected, and node 1 and 5
are connected, hence 3 and 5 are
connected. Thus it will return 1.
Example 2:
Input:
N = 5
q = 4
Queries = 
Union(1,4)
Union(1,5)
isConnected(2,3)
Union(3,4)
Output: 0
Your Task:
You have to complete the function union_() which merges the node1 and node2. You will also have to complete the function isConnected() which will return whether the two nodes are connected.
Note: Both function will contain two arrays par[] and ranks1[] along with two nodes. Initially par[i] = i and rank1[i] = 1 
Expected Time Complexity: O(N + Q).
Expected Auxiliary Space: O(1).
Constraints: 
1 <= N <= 10^{5}
1<= Q <= 10^{5}
1 <= node1, node2 <= N

Source: geeksforgeeks | Difficulty: EASY
Tags: Spanning trees

Graph algorithms

Data structures

Starter code: #User function Template for python3





class Solution:

    

    #Function to merge two nodes a and b.

    def union_(self,a,b,par,rank1):

        # code here

        

    #Function to check whether 2 nodes are connected or not.

    def isConnected(self,x,y,par,rank1):

        # code here

Solutions:
class Solution:

	@staticmethod
	def find(par, r):
		while par[r] != r:
			r = par[r]
		return r

	@staticmethod
	def compress(par, x, r):
		while x != r:
			par[x] = r
			x = par[x]

	def union_(self, a, b, par, rank1):
		r1 = self.find(par, a)
		r2 = self.find(par, b)
		if r1 != r2:
			par[r1] = r2
		self.compress(par, a, r2)
		self.compress(par, b, r2)

	def isConnected(self, x, y, par, rank1):
		return self.find(par, x) == self.find(par, y)


class Solution:

	def findPar(self, a, par):
		if a == par[a]:
			return a
		parentNode = self.findPar(par[a], par)
		return parentNode

	def union_(self, a, b, par, rank1):
		p1 = self.findPar(a, par)
		p2 = self.findPar(b, par)
		if rank1[p1] > rank1[p2]:
			par[p2] = p1
		elif rank1[p2] > rank1[p1]:
			par[p1] = p2
		else:
			par[p2] = p1
			rank1[p1] += 1

	def isConnected(self, x, y, par, rank1):
		p1 = self.findPar(x, par)
		p2 = self.findPar(y, par)
		return p1 == p2


class Solution:

	def union_(self, a, b, par, rank1):
		a_root = self.find(a, par)
		b_root = self.find(b, par)
		if a_root == b_root:
			return
		if rank1[a_root] > rank1[b_root]:
			par[b_root] = a_root
		elif rank1[a_root] < rank1[b_root]:
			par[a_root] = b_root
		else:
			par[b_root] = a_root
			rank1[a_root] += 1

	def find(self, x, par):
		if par[x] != x:
			par[x] = self.find(par[x], par)
		return par[x]

	def isConnected(self, x, y, par, rank1):
		return self.find(x, par) == self.find(y, par)


class Solution:

	def union_(self, x, y, par, rank1):
		(a, b) = (x, y)
		while a != par[a]:
			a = par[a]
		while b != par[b]:
			b = par[b]
		if rank1[a] > rank1[b]:
			rank1[a] += rank1[b]
			par[b] = a
		else:
			rank1[b] += rank1[a]
			par[a] = b

	def isConnected(self, x, y, par, rank1):
		(a, b) = (x, y)
		while a != par[a]:
			a = par[a]
		while b != par[b]:
			b = par[b]
		return a == b


class Solution:

	def union_(self, a, b, par, rank1):
		while par[a] != a or par[b] != b:
			a = par[a]
			b = par[b]
		if rank1[a] > rank1[b]:
			par[b] = a
		elif rank1[a] < rank1[b]:
			par[a] = b
		else:
			par[b] = a
			rank1[a] += 1

	def isConnected(self, x, y, par, rank1):
		while par[x] != x or par[y] != y:
			x = par[x]
			y = par[y]
		return x == y


class Solution:

	def find(self, a, par):
		if par[a] == a:
			return a
		par[a] = self.find(par[a], par)
		return par[a]

	def union_(self, a, b, par, rank1):
		f1 = self.find(a, par)
		f2 = self.find(b, par)
		if f1 == f2:
			return
		if rank1[f1] > rank1[f2]:
			par[f2] = f1
		elif rank1[f1] < rank1[f2]:
			par[f1] = f2
		else:
			rank1[f1] += 1
			par[f2] = f1

	def isConnected(self, x, y, par, rank1):
		if self.find(x, par) != self.find(y, par):
			return 0
		return 1


class Solution:

	def union_(self, a, b, par, rank1):
		aroot = self.find(par, a)
		broot = self.find(par, b)
		if aroot == broot:
			return
		elif rank1[aroot] < rank1[broot]:
			par[aroot] = broot
		elif rank1[aroot] > rank1[broot]:
			par[broot] = aroot
		else:
			par[broot] = aroot
			rank1[aroot] += 1

	def isConnected(self, x, y, par, rank1):
		x_repr = self.find(par, x)
		y_repr = self.find(par, y)
		if x_repr == y_repr:
			return True
		else:
			return False

	def find(self, par, x):
		if x != par[x]:
			par[x] = self.find(par, par[x])
		return par[x]


class Solution:

	def union_(self, a, b, par, rank1):
		rep_a = self.find(a, par)
		rep_b = self.find(b, par)
		if rep_a == rep_b:
			return
		if rank1[rep_a] == rank1[rep_b]:
			par[rep_b] = rep_a
			rank1[rep_a] += 1
		elif rank1[rep_a] < rank1[rep_b]:
			par[rep_a] = rep_b
		else:
			par[rep_b] = rep_a

	def isConnected(self, x, y, par, rank1):
		rep_x = self.find(x, par)
		rep_y = self.find(y, par)
		return rep_x == rep_y

	def find(self, x, par):
		while x != par[x]:
			x = par[x]
		return x


class Solution:

	def findpar(self, node, par):
		if par[node] == node:
			return node
		par[node] = self.findpar(par[node], par)
		return par[node]

	def union_(self, a, b, par, rank1):
		u = self.findpar(a, par)
		v = self.findpar(b, par)
		if rank1[u] < rank1[v]:
			par[u] = v
		elif rank1[u] > rank1[v]:
			par[v] = u
		else:
			par[v] = u
			rank1[u] += 1

	def isConnected(self, x, y, par, rank1):
		return self.findpar(x, par) == self.findpar(y, par)


class Solution:

	def find_(self, par, a):
		if par[a] != a:
			par[a] = self.find_(par, par[a])
		return par[a]

	def union_(self, a, b, par, rank1):
		a = self.find_(par, a)
		b = self.find_(par, b)
		if rank1[a] < rank1[b]:
			par[a] = b
		elif rank1[a] > rank1[b]:
			par[b] = a
		else:
			par[b] = a
			rank1[a] += 1

	def isConnected(self, x, y, par, rank1):
		rep_x = self.find_(par, x)
		rep_y = self.find_(par, y)
		return rep_x == rep_y


class Solution:

	def union_(self, a, b, par, rank1):
		parentx = self.Find(a, par)
		parenty = self.Find(b, par)
		if parentx == parenty:
			return
		if rank1[parentx] > rank1[parenty]:
			par[parenty] = parentx
		elif rank1[parenty] > rank1[parentx]:
			par[parentx] = parenty
		else:
			par[parenty] = parentx
			rank1[parentx] += 1

	def Find(self, x, parent):
		if parent[x] != x:
			parent[x] = self.Find(parent[x], parent)
		return parent[x]

	def isConnected(self, x, y, par, rank1):
		return 1 if self.Find(x, par) == self.Find(y, par) else 0


class Solution:

	def union_(self, a, b, par, rank1):
		a_r = self.find(a, par)
		b_r = self.find(b, par)
		if a_r != b_r:
			if rank1[a_r] < rank1[b_r]:
				par[a_r] = b_r
			elif rank1[a_r] > rank1[b_r]:
				par[b_r] = a_r
			else:
				par[a_r] = b_r
				rank1[b_r] += 1

	def isConnected(self, x, y, par, rank1):
		return self.find(x, par) == self.find(y, par)

	def find(self, x, par):
		if par[x] == x:
			return x
		par[x] = self.find(par[x], par)
		return par[x]


class Solution:

	def union_(self, a, b, par, rank1):
		a_par = self.find_parent(a, par)
		b_par = self.find_parent(b, par)
		if rank1[a_par] > rank1[b_par]:
			par[b_par] = a_par
		elif rank1[b_par] > rank1[a_par]:
			par[a_par] = b_par
		else:
			par[b_par] = a_par
			rank1[a_par] += 1

	def find_parent(self, x, par):
		if x != par[x]:
			return self.find_parent(par[x], par)
		return par[x]

	def isConnected(self, x, y, par, rank1):
		xpar = self.find_parent(x, par)
		ypar = self.find_parent(y, par)
		return xpar == ypar


class Solution:

	def find(self, a, par):
		while par[a] != a:
			a = par[a]
		return a

	def union_(self, a, b, par, rank1):
		(aroot, broot) = (self.find(a, par), self.find(b, par))
		if aroot == broot:
			return
		if rank1[aroot] > rank1[broot]:
			par[broot] = aroot
			rank1[aroot] += rank1[broot]
		else:
			par[aroot] = broot
			rank1[broot] += rank1[aroot]

	def isConnected(self, x, y, par, rank1):
		return self.find(x, par) == self.find(y, par)


class Solution:

	def MainParent(self, b, par):
		if par[b] == b:
			return b
		par[b] = self.MainParent(par[b], par)
		return par[b]

	def union_(self, a, b, par, rank1):
		ulp_a = self.MainParent(a, par)
		ulp_b = self.MainParent(b, par)
		if rank1[ulp_a] < rank1[ulp_b]:
			par[ulp_a] = ulp_b
		elif rank1[ulp_a] > rank1[ulp_b]:
			par[ulp_b] = ulp_a
		else:
			par[ulp_b] = ulp_a
			rank1[ulp_a] += 1

	def isConnected(self, x, y, par, rank1):
		if self.MainParent(x, par) == self.MainParent(y, par):
			return 1
		else:
			return 0


class Solution:

	def root(self, i, par):
		while i != par[i]:
			i = par[i]
		return i

	def union_(self, a, b, par, rank1):
		(x, y) = (self.root(a, par), self.root(b, par))
		if x == y:
			return
		if rank1[x] >= rank1[y]:
			rank1[x] += 1
			par[y] = par[x]
		else:
			rank1[y] += 1
			par[x] = par[y]

	def isConnected(self, x, y, par, rank1):
		return self.root(x, par) == self.root(y, par)


class Solution:

	def findSet(self, i, par):
		if i == par[i]:
			return i
		ans = self.findSet(par[i], par)
		par[i] = ans
		return ans

	def union_(self, a, b, par, rank1):
		a = self.findSet(a, par)
		b = self.findSet(b, par)
		if a != b:
			if rank1[a] < rank1[b]:
				(a, b) = (b, a)
			rank1[a] += rank1[b]
			par[b] = a

	def isConnected(self, x, y, par, rank1):
		x = self.findSet(x, par)
		y = self.findSet(y, par)
		return x == y


class Solution:

	def union_(self, a, b, par, rank1):
		a = self.ancestor(par, a)
		b = self.ancestor(par, b)
		if rank1[a] > rank1[b]:
			par[b] = a
			rank1[a] += rank1[b]
		else:
			par[a] = b
			rank1[b] += rank1[a]

	def ancestor(self, par, i):
		if par[i] == i:
			return i
		par[i] = self.ancestor(par, par[i])
		return par[i]

	def isConnected(self, x, y, par, rank1):
		return self.ancestor(par, x) == self.ancestor(par, y)


class Solution:

	def find(self, a, par):
		if a == par[a]:
			return a
		return self.find(par[a], par)

	def union_(self, a, b, par, rank1):
		ra = self.find(a, par)
		rb = self.find(b, par)
		rank1[ra] = ra
		rank1[rb] = rb
		if ra > rb:
			par[ra] = par[rb]
			rank1[ra] += rank1[rb]
		else:
			par[rb] = par[ra]
			rank1[rb] += rank1[ra]
		return

	def isConnected(self, x, y, par, rank1):
		x1 = self.find(x, par)
		x2 = self.find(y, par)
		if x1 == x2:
			return 1
		return 0


class Solution:

	def Parent(self, node, par):
		if par[node] == node:
			return node
		return self.Parent(par[node], par)

	def union_(self, a, b, par, rank1):
		a1 = self.Parent(a, par)
		b1 = self.Parent(b, par)
		if rank1[a1] > rank1[b1]:
			par[b1] = a1
			rank1[a1] += rank1[b1]
		else:
			par[a1] = b1
			rank1[b1] += rank1[a1]
		return

	def isConnected(self, x, y, par, rank1):
		a1 = self.Parent(x, par)
		b1 = self.Parent(y, par)
		return a1 == b1


class Solution:

	def find_root(self, i, par):
		if i == par[i]:
			return i
		par[i] = self.find_root(par[i], par)
		return par[i]

	def union_(self, a, b, par, rank1):
		a = self.find_root(a, par)
		b = self.find_root(b, par)
		if rank1[a] > rank1[b]:
			rank1[a] += rank1[b]
			par[b] = a
		else:
			rank1[b] += rank1[a]
			par[a] = b

	def isConnected(self, x, y, par, rank1):
		if self.find_root(x, par) == self.find_root(y, par):
			return True
		return False


class Solution:

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

	def union_(self, a, b, par, rank1):
		ulp_a = self.findUParent(a, par)
		ulp_b = self.findUParent(b, par)
		if ulp_a == ulp_b:
			return
		if rank1[a] < rank1[b]:
			par[ulp_a] = ulp_b
		elif rank1[a] == rank1[b]:
			par[ulp_a] = ulp_b
			rank1[ulp_b] += 1
		else:
			par[ulp_b] = ulp_a

	def isConnected(self, x, y, par, rank1):
		ulp_x = self.findUParent(x, par)
		ulp_y = self.findUParent(y, par)
		if ulp_x == ulp_y:
			return 1
		else:
			return 0


class Solution:

	def findpar(self, a, par):
		if a == par[a]:
			return a
		return self.findpar(par[a], par)

	def union_(self, a, b, par, rank1):
		apar = self.findpar(a, par)
		bpar = self.findpar(b, par)
		if rank1[apar] > rank1[bpar]:
			par[bpar] = apar
		elif rank1[bpar] > rank1[apar]:
			par[apar] = bpar
		else:
			par[bpar] = apar
			rank1[apar] += 1

	def isConnected(self, x, y, par, rank1):
		apar = self.findpar(x, par)
		bpar = self.findpar(y, par)
		return apar == bpar


class Solution:

	def find(self, node, par):
		if par[node] != node:
			par[node] = self.find(par[node], par)
		return par[node]

	def union_(self, a, b, par, rank):
		x = self.find(a, par)
		y = self.find(b, par)
		if x == y:
			return
		if rank[x] < rank[y]:
			par[y] = par[x]
		elif rank[x] > rank[y]:
			par[x] = par[y]
		else:
			par[y] = par[x]
			rank[x] += 1

	def isConnected(self, x, y, par, rank1):
		nodex = self.find(x, par)
		nodey = self.find(y, par)
		if nodex == nodey:
			return True
		return False


class Solution:

	def find(self, x, par):
		if par[x] == x:
			return x
		else:
			return self.find(par[x], par)

	def union_(self, a, b, par, rank1):
		par_a = self.find(a, par)
		par_b = self.find(b, par)
		rank_par_a = rank1[par_a]
		rank_par_b = rank1[par_b]
		if rank_par_a > rank_par_b:
			par[par_b] = par_a
			rank1[par_a] += rank1[par_b]
		else:
			par[par_a] = par_b
			rank1[par_b] += rank1[par_a]
		return

	def isConnected(self, x, y, par, rank1):
		if self.find(x, par) == self.find(y, par):
			return 1
		else:
			return 0


class Solution:

	def union_(self, a, b, par, rank1):
		par_a = a
		par_b = b
		while par[par_a] != par_a:
			par_a = par[par_a]
		while par[par_b] != par_b:
			par_b = par[par_b]
		if rank1[par_a] > rank1[par_b]:
			par[par_b] = par_a
		elif rank1[par_a] < rank1[par_b]:
			par[par_a] = par_b
		else:
			par[par_a] = par_b
			rank1[b] += 1

	def isConnected(self, x, y, par, rank1):
		par_x = x
		par_y = y
		while par[par_x] != par_x:
			par_x = par[par_x]
		while par[par_y] != par_y:
			par_y = par[par_y]
		if par_x != par_y:
			return 0
		return 1


class Solution:

	def find(self, x, par):
		if x == par[x]:
			return x
		par[x] = self.find(par[x], par)
		return par[x]

	def union_(self, a, b, par, rank):
		x_rep = self.find(a, par)
		y_rep = self.find(b, par)
		if x_rep == y_rep:
			return
		if rank[x_rep] < rank[y_rep]:
			par[x_rep] = y_rep
		elif rank[y_rep] < rank[x_rep]:
			par[y_rep] = x_rep
		else:
			par[y_rep] = x_rep
			rank[x_rep] += 1

	def isConnected(self, x, y, par, rank):
		return self.find(x, par) == self.find(y, par)


class Solution:

	def findRoot(self, x, par):
		if par[x] == x:
			return x
		return self.findRoot(par[x], par)

	def union_(self, a, b, par, rank1):
		a1 = self.findRoot(a, par)
		b1 = self.findRoot(b, par)
		if rank1[a1] > rank1[b1]:
			par[b1] = a1
			rank1[a1] += rank1[b1]
		else:
			par[a1] = b1
			rank1[b1] += rank1[a1]
		return

	def isConnected(self, x, y, par, rank1):
		a2 = self.findRoot(x, par)
		b2 = self.findRoot(y, par)
		if a2 == b2:
			return True
		else:
			return False


class Solution:

	def union_(self, a, b, par, rank1):

		def find(x, par):
			if x == par[x]:
				return x
			par[x] = find(par[x], par)
			return par[x]
		x_rep = find(a, par)
		y_rep = find(b, par)
		if x_rep == y_rep:
			return
		else:
			if rank1[x_rep] > rank1[y_rep]:
				par[y_rep] = x_rep
			elif rank1[x_rep] < rank1[y_rep]:
				par[x_rep] = y_rep
			else:
				par[x_rep] = y_rep
				rank1[y_rep] += 1
			return

	def isConnected(self, x, y, par, rank1):

		def find(x, par):
			if x == par[x]:
				return x
			par[x] = find(par[x], par)
			return par[x]
		x_rep = find(x, par)
		y_rep = find(y, par)
		if x_rep == y_rep:
			return True
		return False


class Solution:

	def union_(self, a, b, par, rank1):
		i = a
		while par[i] != i:
			i = par[i]
		j = b
		while par[j] != j:
			j = par[j]
		if i == j:
			return
		if rank1[i] > rank1[j]:
			par[j] = i
			rank1[i] += 1
		else:
			par[i] = j
			rank1[j] += 1

	def isConnected(self, x, y, par, rank1):
		i = x
		while par[i] != i:
			i = par[i]
		j = y
		while par[j] != j:
			j = par[j]
		if i == j:
			return True
		return False


class Solution:

	def find(self, a, par, rank):
		if par[a] == a:
			return a
		else:
			par[a] = self.find(par[a], par, rank)
			return par[a]

	def union_(self, a, b, par, rank):
		roota = self.find(a, par, rank)
		rootb = self.find(b, par, rank)
		if roota == rootb:
			return
		if rank[roota] > rank[rootb]:
			par[rootb] = roota
		elif rank[roota] < rank[rootb]:
			par[roota] = rootb
		else:
			par[rootb] = roota
			rank[roota] += 1

	def isConnected(self, x, y, par, rank):
		roota = self.find(x, par, rank)
		rootb = self.find(y, par, rank)
		return roota == rootb


class Solution:

	def find_op(self, node, parent_list):
		if parent_list[node] != node:
			parent_list[node] = self.find_op(parent_list[node], parent_list)
		return parent_list[node]

	def union_(self, a, b, parent_list, rank_list):
		parent_a = self.find_op(a, par)
		parent_b = self.find_op(b, par)
		if rank_list[parent_a] > rank_list[parent_b]:
			parent_list[parent_b] = parent_a
			rank_list[parent_a] += rank_list[parent_b]
		elif rank_list[parent_b] > rank_list[parent_a]:
			parent_list[parent_a] = parent_b
			rank_list[parent_b] += rank_list[parent_a]
		else:
			parent_list[parent_a] = parent_b
			rank_list[parent_b] += 1

	def isConnected(self, x, y, par, rank1):
		parent_x = self.find_op(x, par)
		parent_y = self.find_op(y, par)
		return parent_x == parent_y


class Solution:

	def findParent(self, parent, u):
		if parent[u] == u:
			return u
		parent[u] = self.findParent(parent, parent[u])
		return parent[u]

	def union_(self, a, b, par, rank1):
		a = self.findParent(par, a)
		b = self.findParent(par, b)
		if a != b:
			if rank1[a] < rank1[b]:
				(a, b) = (b, a)
			par[b] = a
			rank1[a] += rank1[b]

	def isConnected(self, x, y, par, rank1):
		if self.findParent(par, x) != self.findParent(par, y):
			return 0
		else:
			return 1


class Solution:

	def findRoot(self, x, par):
		if x == par[x]:
			return x
		return self.findRoot(par[x], par)

	def union_(self, a, b, par, rank1):
		root_a = self.findRoot(a, par)
		root_b = self.findRoot(b, par)
		rank_root_a = rank1[root_a]
		rank_root_b = rank1[root_b]
		if rank_root_a > rank_root_b:
			par[root_b] = root_a
			rank1[root_a] += rank1[root_b]
		else:
			par[root_a] = root_b
			rank1[root_b] += rank1[root_a]
		return

	def isConnected(self, x, y, par, rank1):
		root_x = self.findRoot(x, par)
		root_y = self.findRoot(y, par)
		if root_x == root_y:
			return True
		else:
			return False


class Solution:

	def union_(self, x, y, parent, rank):
		x_rep = self.find(x, parent)
		y_rep = self.find(y, parent)
		x_rank = rank[x_rep]
		y_rank = rank[y_rep]
		if x_rank < y_rank:
			parent[x_rep] = y_rep
		elif x_rank > y_rank:
			parent[y_rep] = x_rep
		else:
			parent[x_rep] = y_rep
			rank[x_rep] += 1

	def find(self, x, parent):
		if parent[x] == x:
			return x
		parent[x] = self.find(parent[x], parent)
		return parent[x]

	def isConnected(self, x, y, parent, rank):
		x_rep = self.find(x, parent)
		y_rep = self.find(y, parent)
		return x_rep == y_rep


class Solution:

	def union_(self, a, b, par, rank1):
		x = self.find(a, par)
		y = self.find(b, par)
		if x == y:
			return
		else:
			par[x] = y
			rank1[y] = rank1[y] + 1

	def find(self, x, par):
		if par[x] == x:
			return x
		par[x] = self.find(par[x], par)
		return par[x]

	def isConnected(self, x, y, par, rank1):
		u = self.find(x, par)
		v = self.find(y, par)
		if u == v:
			return 1
		return 0


class Solution:

	def find(self, c, par):
		if par[c] == c:
			return c
		z = self.find(par[c], par)
		return self.find(par[c], par)

	def union_(self, a, b, par, rank1):
		a = self.find(a, par)
		b = self.find(b, par)
		if a == b:
			return
		elif rank1[a] > rank1[b]:
			par[b] = a
			rank1[a] += 1
		else:
			par[a] = b
			rank1[b] += 1

	def isConnected(self, x, y, par, rank1):
		return self.find(x, par) == self.find(y, par)


class Solution:

	def union_(self, a, b, par, rank1):
		par1 = self.find(a, par)
		par2 = self.find(b, par)
		if par1 == par2:
			return
		if rank1[par1] >= rank1[par2]:
			rank1[par1] += 1
			par[par2] = par1
		else:
			rank1[par2] += 1
			par[par1] = par2

	def find(self, node, par):
		if node == par[node]:
			return node
		return self.find(par[node], par)

	def isConnected(self, x, y, par, rank1):
		return self.find(x, par) == self.find(y, par)


class Solution:

	def find_set(self, p, par):
		if par[p] == p:
			return p
		par[p] = self.find_set(par[p], par)
		return par[p]

	def union_(self, a, b, par, rank1):
		a = self.find_set(a, par)
		b = self.find_set(b, par)
		if a != b:
			if rank1[a] < rank1[b]:
				(a, b) = (b, a)
			par[b] = a
			rank1[a] += rank1[b]

	def isConnected(self, x, y, par, rank1):
		if self.find_set(x, par) == self.find_set(y, par):
			return 1
		else:
			return 0


class Solution:

	def find(self, a, par):
		if par[a] == a:
			return a
		par[a] = self.find(par[a], par)
		return par[a]

	def union_(self, a, b, par, rank1):
		p1 = self.find(a, par)
		p2 = self.find(b, par)
		if rank1[p1] >= rank1[p2]:
			par[p2] = p1
		else:
			par[p1] = p2

	def isConnected(self, x, y, par, rank1):
		return self.find(x, par) == self.find(y, par)


class Solution:

	def union_(self, a, b, par, rank1):
		a = self.getParent(a, par)
		b = self.getParent(b, par)
		if a == b:
			return
		if rank1[a] >= rank1[b]:
			rank1[a] += 1
			par[b] = a
		else:
			rank1[b] += 1
			par[a] = b

	def getParent(self, x, par):
		if x == par[x]:
			return x
		return self.getParent(par[x], par)

	def isConnected(self, x, y, par, rank1):
		return self.getParent(x, par) == self.getParent(y, par)


class Solution:

	def getPar(self, a, par):
		if a != par[a]:
			par[a] = self.getPar(par[a], par)
		return par[a]

	def union_(self, a, b, par, rank1):
		x = self.getPar(a, par)
		y = self.getPar(b, par)
		par[x] = y

	def isConnected(self, x, y, par, rank1):
		return self.getPar(x, par) == self.getPar(y, par)


class Solution:

	def find(self, x, par):
		if par[x] == x:
			return x
		par[x] = self.find(par[x], par)
		return par[x]

	def union_(self, a, b, par, rank1):
		para = self.find(a, par)
		parb = self.find(b, par)
		if para == parb:
			return
		if rank1[para] < rank1[parb]:
			par[para] = parb
			rank1[para] += 1
		elif rank1[para] > rank1[parb]:
			par[parb] = para
			rank1[parb] += 1
		else:
			par[parb] = para
			rank1[para] += 1

	def isConnected(self, x, y, par, rank1):
		parx = self.find(x, par)
		pary = self.find(y, par)
		if parx == pary:
			return True
		return False


class Solution:

	def find(self, x, p):
		if p[x] == x:
			return x
		return self.find(p[x], p)

	def union_(self, a, b, p, r):
		x = self.find(a, p)
		y = self.find(b, p)
		if x == y:
			return
		if r[x] > r[y]:
			p[y] = x
		elif r[y] > r[x]:
			p[x] = y
		else:
			p[y] = x
			r[x] += 1

	def isConnected(self, x, y, p, r):
		return True if self.find(x, p) == self.find(y, p) else False


class Solution:

	def union_(self, a, b, par, rank1):
		x_root = self.find(a, par)
		y_root = self.find(b, par)
		if x_root == y_root:
			return
		elif rank1[x_root] > rank1[y_root]:
			par[y_root] = x_root
		elif rank1[x_root] < rank1[y_root]:
			par[x_root] = y_root
		else:
			par[y_root] = x_root
			rank1[x_root] += 1

	def isConnected(self, x, y, par, rank1):
		if self.find(x, par) == self.find(y, par):
			return 1
		else:
			return 0

	def find(self, x, par):
		if par[x] == x:
			return x
		par[x] = self.find(par[x], par)
		return par[x]


class Solution:

	def union_(self, a, b, par, rank1):
		a = self.findparent(a, par)
		b = self.findparent(b, par)
		if rank1[a] < rank1[b]:
			par[a] = b
		elif rank1[a] > rank1[b]:
			par[b] = a
		else:
			par[a] = b
			rank1[b] = rank1[b] + 1

	def findparent(self, a, par):
		if par[a] == a:
			return a
		par[a] = self.findparent(par[a], par)
		return par[a]

	def isConnected(self, x, y, par, rank1):
		if self.findparent(x, par) == self.findparent(y, par):
			return True
		else:
			return False


class Solution:

	def union_(self, a, b, par, rank1):
		root1 = self.find(a, par, rank1)
		root2 = self.find(b, par, rank1)
		if root1 == root2:
			return
		if rank1[root1] > rank1[root2]:
			par[root2] = root1
			rank1[root1] += rank1[root2]
		else:
			par[root1] = root2
			rank1[root2] += rank1[root1]

	def find(self, node, par, rank1):
		root = node
		while root != par[root]:
			root = par[root]
		while node != root:
			temp = par[node]
			par[node] = root
			node = temp
		return root

	def isConnected(self, x, y, par, rank1):
		return self.find(x, par, rank1) == self.find(y, par, rank1)


class Solution:

	def union_(self, a, b, par, rank1):
		p_a = self.find(a, par)
		p_b = self.find(b, par)
		if p_a != p_b:
			if rank1[a] < rank1[b]:
				par[p_a] = p_b
			elif rank1[a] > rank1[b]:
				par[p_b] = p_a
			else:
				rank1[p_a] += 1
				par[p_b] = p_a
		return

	def find(self, x, par):
		if par[x] != x:
			par[x] = self.find(par[x], par)
		return par[x]

	def isConnected(self, x, y, par, rank1):
		if self.find(x, par) == self.find(y, par):
			return True
		return False


class Solution:

	def find(self, a, par, rank1):
		if par[a] != a:
			par[a] = self.find(par[a], par, rank1)
		return par[a]

	def union_(self, a, b, par, rank1):
		aRoot = self.find(a, par, rank1)
		bRoot = self.find(b, par, rank1)
		if aRoot != bRoot:
			if rank1[aRoot] > rank1[bRoot]:
				par[aRoot] = bRoot
			elif rank1[aRoot] < rank1[bRoot]:
				par[bRoot] = aRoot
			else:
				par[aRoot] = bRoot
				rank1[bRoot] = rank1[aRoot] + 1
		return

	def isConnected(self, x, y, par, rank1):
		if self.find(x, par, rank1) == self.find(y, par, rank1):
			return 1
		else:
			return 0


class Solution:

	def find(self, par, node):
		if par[node] == node:
			return node
		return self.find(par, par[node])

	def union_(self, a, b, par, rank1):
		p = self.find(par, a)
		par[a] = p
		q = self.find(par, b)
		par[b] = q
		if rank1[p] > rank1[q]:
			par[q] = p
		elif rank1[p] < rank1[q]:
			par[p] = q
		else:
			par[q] = p
			rank1[p] += 1

	def isConnected(self, x, y, par, rank1):
		p = self.find(par, x)
		q = self.find(par, y)
		if par[p] == par[q]:
			return True
		return False


class Solution:

	def find_par(self, x, par):
		if par[x] == x:
			return x
		ans = self.find_par(par[x], par)
		par[x] = ans
		return ans

	def union_(self, a, b, par, rank1):
		pa = self.find_par(a, par)
		pb = self.find_par(b, par)
		if rank1[pa] > rank1[pb]:
			par[pb] = pa
		elif rank1[pa] < rank1[pb]:
			par[pa] = pb
		else:
			par[pb] = pa
			rank1[pa] += 1

	def isConnected(self, x, y, par, rank1):
		if self.find_par(x, par) == self.find_par(y, par):
			return True
		return False


class Solution:

	def findRoot(self, a, par):
		i = a
		while par[i] != i:
			i = par[i]
		return i

	def union_(self, a, b, par, rank1):
		rootA = self.findRoot(a, par)
		rootB = self.findRoot(b, par)
		if rootA != rootB:
			if rank1[rootA] >= rank1[rootB]:
				rank1[rootA] += rank1[rootB]
				par[rootB] = rootA
			else:
				rank1[rootB] += rank1[rootA]
				par[rootA] = rootB

	def isConnected(self, x, y, par, rank1):
		rootX = self.findRoot(x, par)
		par[x] = rootX
		rootY = self.findRoot(y, par)
		par[y] = rootY
		return rootX == rootY


class Solution:

	def root(self, arr, i):
		while arr[i] != i:
			i = arr[arr[i]]
		return i

	def union_(self, a, b, par, rank1):
		roota = self.root(par, a)
		rootb = self.root(par, b)
		if rank1[roota] > rank1[rootb]:
			par[rootb] = roota
			rank1[roota] += rank1[rootb]
		else:
			par[roota] = rootb
			rank1[rootb] += rank1[roota]

	def isConnected(self, x, y, par, rank1):
		if self.root(par, x) == self.root(par, y):
			return True
		return False


class Solution:

	def union_(self, a, b, par, rank1):
		par[self.fp(a, par)] = self.fp(b, par)

	def isConnected(self, x, y, par, rank1):
		a = self.fp(x, par)
		b = self.fp(y, par)
		if a == b:
			return 1
		return 0

	def fp(self, i, par):
		if par[i] == i:
			return i
		par[i] = self.fp(par[i], par)
		return par[i]


class Solution:

	def absParent(self, a, par):
		if par[a] == a:
			return a
		par[a] = self.absParent(par[a], par)
		return par[a]

	def union_(self, a, b, par, rank1):
		A = self.absParent(a, par)
		B = self.absParent(b, par)
		if rank1[A] == rank1[B]:
			par[B] = A
			rank1[A] += 1
		elif rank1[A] > rank1[B]:
			par[B] = A
		else:
			par[A] = B

	def isConnected(self, x, y, par, rank1):
		X = self.absParent(x, par)
		Y = self.absParent(y, par)
		if X != Y:
			return 0
		return 1


class Solution:

	def parent(self, t, par):
		while par[t] != t:
			t = par[t]
		return t

	def union_(self, a, b, par, rank1):
		par_a = self.parent(a, par)
		par_b = self.parent(b, par)
		if rank1[par_a] < rank1[par_b]:
			par[par_a] = par_b
		else:
			par[par_b] = par_a
			if rank1[par_a] == rank1[par_b]:
				rank1[par_a] += 1

	def isConnected(self, x, y, par, rank1):
		if self.parent(x, par) == self.parent(y, par):
			return 1
		return 0


class Solution:

	def find_root(self, a, par):
		if a == par[a]:
			return a
		else:
			return self.find_root(par[a], par)

	def union_(self, a, b, par, rank1):
		root_a = self.find_root(a, par)
		root_b = self.find_root(b, par)
		ranka = rank1[root_a]
		rankb = rank1[root_b]
		if ranka > rankb:
			par[root_b] = root_a
			rank1[root_a] = rank1[root_a] + rank1[root_b]
		else:
			par[root_a] = root_b
			rank1[root_b] = rank1[root_a] + rank1[root_b]
		return

	def isConnected(self, x, y, par, rank1):
		a = self.find_root(x, par)
		b = self.find_root(y, par)
		if a == b:
			return True
		else:
			return False


class Solution:

	def union_(self, a, b, parent, rank1):
		pa = self.find_parent(a, parent)
		pb = self.find_parent(b, parent)
		if rank1[pa] > rank1[pb]:
			parent[pb] = pa
			rank1[pa] += rank1[pb]
		else:
			parent[pa] = pb
			rank1[pb] += rank1[pb]

	def isConnected(self, x, y, par, rank1):
		px = self.find_parent(x, par)
		py = self.find_parent(y, par)
		return px == py

	def find_parent(self, x, parent):
		while x != parent[x]:
			parent[x] = parent[parent[x]]
			x = parent[x]
		return x