You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.
You can swap the characters at any pair of indices in the given pairs any number of times.
Return the lexicographically smallest string that s can be changed to after using the swaps.
 
Example 1:
Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

Example 2:
Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"
Example 3:
Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination: 
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

 
Constraints:

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.

Source: leetcode | Difficulty: MEDIUM
Tags: Spanning trees

Data structures

Graph traversal

String algorithms

Starter code: class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        

Solutions:
class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		pr = [i for i in range(len(s))]

		def union(x, y):
			p1 = find(x)
			p2 = find(y)
			if p1 != p2:
				pr[p1] = p2

		def find(x):
			while pr[x] != x:
				pr[x] = pr[pr[x]]
				x = pr[x]
			return x
		for i in pairs:
			union(i[0], i[1])
		from collections import defaultdict
		dp = defaultdict(list)
		for i in range(len(s)):
			ld = find(i)
			dp[ld].append(i)
		ans = [0] * len(s)
		for i in dp:
			dp[i].sort()
			st = ''
			for j in dp[i]:
				st += s[j]
			st = sorted(st)
			c = 0
			for j in dp[i]:
				ans[j] = st[c]
				c += 1
		return ''.join(ans)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		parents = [i for i in range(n)]

		def find_parent(i):
			while parents[i] != i:
				parents[i] = parents[parents[i]]
				i = parents[i]
			return i

		def do_union(p, q):
			i = find_parent(p)
			j = find_parent(q)
			parents[i] = j
		for (p, q) in pairs:
			do_union(p, q)
		groups = defaultdict(list)
		for i in range(len(s)):
			root = find_parent(i)
			groups[root].append(i)
		s = list(s)
		for indices in sorted(groups.values()):
			vals = sorted([s[i] for i in indices])
			for (i, c) in enumerate(vals):
				s[indices[i]] = c
		return ''.join(s)


class UnionFind:

	def __init__(self, N):
		self.par = list(range(N))
		self.rank = [0] * N

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

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px == py:
			return
		if self.rank[px] < self.rank[py]:
			self.par[px] = py
		elif self.rank[px] > self.rank[py]:
			self.par[py] = px
		else:
			self.par[py] = px
			self.rank[px] += 1

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		N = len(s)
		uf = UnionFind(N)
		res = [''] * N
		indices = defaultdict(list)
		for (u, v) in pairs:
			uf.union(u, v)
		for i in range(N):
			indices[uf.find(i)].append(i)
		for i in indices:
			chars = sorted([s[j] for j in indices[i]])
			for j in range(len(indices[i])):
				res[indices[i][j]] = chars[j]
		return ''.join(res)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		self.parent = {i: i for i in range(len(s))}
		for (pos1, pos2) in pairs:
			self.merge(pos1, pos2)
		connected_component = defaultdict(list)
		for i in range(len(s)):
			connected_component[self.find(i)].append(s[i])
		for k in connected_component.keys():
			connected_component[k].sort(reverse=True)
		res = []
		for i in range(len(s)):
			res.append(connected_component[self.find(i)].pop())
		return ''.join(res)

	def find(self, e):
		while e != self.parent[e]:
			self.parent[e] = self.parent[self.parent[e]]
			e = self.parent[e]
		return e

	def merge(self, e1, e2):
		(root1, root2) = (self.find(e1), self.find(e2))
		if root1 != root2:
			self.parent[root1] = root2
		return


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		parent = [i for i in range(n)]
		group = collections.defaultdict(list)
		res = []

		def find(a):
			p = parent[a]
			while p != parent[p]:
				p = parent[p]
			parent[a] = p
			return p

		def union(a, b):
			(pa, pb) = (find(a), find(b))
			if pa != pb:
				parent[pa] = pb
		for (u, v) in pairs:
			union(u, v)
		for i in range(n):
			group[find(i)].append(s[i])
		for k in group:
			group[k].sort(reverse=True)
		for i in range(n):
			res.append(group[find(i)].pop())
		return ''.join(res)


from typing import List
from collections import defaultdict

class DisjointSet:

	def __init__(self, n):
		self.makeSet(n)

	def makeSet(self, n):
		self.parent = [i for i in range(n)]

	def union(self, i, j):
		self.parent[self.find(i)] = self.find(j)

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

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		sa = list(s)
		lens = len(s)
		ds = DisjointSet(lens)
		for pair in pairs:
			i = pair[0]
			j = pair[1]
			ip = ds.find(i)
			jp = ds.find(j)
			if ip != jp:
				ds.union(i, j)
		cm = defaultdict(lambda : [])
		for i in range(lens):
			ip = ds.find(i)
			cm[ip].append((i, sa[i]))
		for (_, li) in list(cm.items()):
			if li:
				lsv = sorted(li, key=lambda t: t[1])
				for i in range(len(li)):
					sa[li[i][0]] = lsv[i][1]
		return ''.join(sa)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		class UF:

			def __init__(self, n):
				self.p = list(range(n))

			def union(self, x, y):
				self.p[self.find(x)] = self.find(y)

			def find(self, x):
				if x != self.p[x]:
					self.p[x] = self.find(self.p[x])
				return self.p[x]
		(uf, res, m) = (UF(len(s)), [], defaultdict(list))
		for (x, y) in pairs:
			uf.union(x, y)
		for i in range(len(s)):
			m[uf.find(i)].append(s[i])
		for comp_id in list(m.keys()):
			m[comp_id].sort(reverse=True)
		for i in range(len(s)):
			res.append(m[uf.find(i)].pop())
		return ''.join(res)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		p = list(range(len(s)))
		d = defaultdict(list)

		def find(x):
			if x != p[x]:
				p[x] = find(p[x])
			return p[x]

		def union(x, y):
			p[find(x)] = find(y)
		for (a, b) in pairs:
			union(a, b)
		for i in range(len(p)):
			d[find(i)].append(s[i])
		for i in d:
			d[find(i)].sort(reverse=True)
		ret = ''
		for i in range(len(s)):
			ret += d[find(i)].pop()
		return ret


class UF:

	def __init__(self, n):
		self.f = list(range(n))
		self.cc = [1] * n

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

	def union(self, x, y):
		(fx, fy) = (self.find(x), self.find(y))
		if fx != fy:
			if self.cc[fx] <= self.cc[fy]:
				self.f[fx] = fy
				(self.cc[fx], self.cc[fy]) = (0, self.cc[fx] + self.cc[fy])
			else:
				self.f[fy] = fx
				(self.cc[fx], self.cc[fy]) = (self.cc[fx] + self.cc[fy], 0)

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		if not s or not pairs:
			return s
		n = len(s)
		uf = UF(n)
		for p in pairs:
			(a, b) = (p[0], p[1])
			uf.union(a, b)
		f2c = collections.defaultdict(list)
		for i in range(n):
			f = uf.find(i)
			f2c[f].append(i)
		ls = [''] * n
		for (_, comp) in list(f2c.items()):
			if not comp:
				continue
			tmp = [s[c] for c in comp]
			comp.sort()
			tmp.sort()
			for i in range(len(comp)):
				ls[comp[i]] = tmp[i]
		return ''.join(ls)


from heapq import *

class Solution:

	def smallestStringWithSwaps(self, s: str, prs: List[List[int]]) -> str:
		f = {}
		for p in prs:
			(r_a, r_b) = (self.fnd(f, p[0]), self.fnd(f, p[1]))
			if r_a != r_b:
				f[r_b] = r_a
		(m, res) = (defaultdict(list), [])
		for i in range(len(s)):
			m[self.fnd(f, i)].append(s[i])
		for v in list(m.values()):
			heapify(v)
		for i in range(len(s)):
			res.append(heappop(m[self.fnd(f, i)]))
		return ''.join(res)

	def fnd(self, f, n):
		f[n] = f.get(n, n)
		if f[n] == n:
			return n
		f[n] = self.fnd(f, f[n])
		return f[n]


class Solution:

	def dfs(self, i):
		self.tmp.append(self.ls[i])
		self.idx.append(i)
		self.visited.add(i)
		for j in self.d[i]:
			if j not in self.visited:
				self.dfs(j)

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		self.ls = list(s)
		self.visited = set()
		self.d = [[] for _ in range(len(self.ls))]
		for (i, j) in pairs:
			self.d[i].append(j)
			self.d[j].append(i)
		for i in range(len(self.ls)):
			if i not in self.visited:
				self.tmp = []
				self.idx = []
				self.dfs(i)
				sorted_tmp = sorted(self.tmp)
				sorted_idx = sorted(self.idx)
				for index in range(len(sorted_idx)):
					self.ls[sorted_idx[index]] = sorted_tmp[index]
		return ''.join(self.ls)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		parent = {i: i for i in range(len(s))}

		def find(x):
			if x != parent[x]:
				parent[x] = find(parent[x])
			return parent[x]
		for edge in pairs:
			parent[find(edge[0])] = find(edge[1])
		parent_table = collections.defaultdict(list)
		for i in list(parent.keys()):
			parent_table[find(i)].append(i)
		ans = list(s)
		for i in list(parent_table.keys()):
			ids = sorted(parent_table[i])
			t = sorted((ans[j] for j in ids))
			for j in range(len(ids)):
				ans[ids[j]] = t[j]
		return ''.join(ans)


class DisjSet:

	def __init__(self, n):
		self.disj_set = [-1] * n

	def find(self, x):
		while self.disj_set[x] >= 0:
			x = self.disj_set[x]
		return x

	def union(self, x, y):
		i = self.find(x)
		j = self.find(y)
		if i == j:
			return
		if self.disj_set[i] < self.disj_set[j]:
			self.disj_set[j] = i
		else:
			if self.disj_set[i] == self.disj_set[j]:
				self.disj_set[j] -= 1
			self.disj_set[i] = j

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		result = []
		disj = DisjSet(n)
		for (a, b) in pairs:
			disj.union(a, b)
		g = collections.defaultdict(collections.Counter)
		for i in range(n):
			g[disj.find(i)][s[i]] += 1
		for i in g:
			g[i] = [[k, v] for (k, v) in g[i].items()]
			g[i].sort(reverse=True)
		for i in range(n):
			j = disj.find(i)
			chars = g[j]
			result.append(chars[-1][0])
			chars[-1][1] -= 1
			if chars[-1][1] == 0:
				chars.pop()
		return ''.join(result)


def dfs(index, s, edges, visited):
	indices = []
	vals = []
	stack = [index]
	while stack:
		index = stack.pop()
		if index not in visited:
			visited.add(index)
			indices.append(index)
			vals.append(s[index])
			for kid in edges[index]:
				stack.append(kid)
	indices.sort()
	vals.sort()
	for index in indices:
		s[index] = vals.pop(0)

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		visited = set()
		s = list(s)
		edges = {}
		for (a, b) in pairs:
			if a not in edges.keys():
				edges[a] = []
			if b not in edges.keys():
				edges[b] = []
			edges[a].append(b)
			edges[b].append(a)
		for i in edges.keys():
			if i not in visited:
				dfs(i, s, edges, visited)
		return ''.join(s)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		g = collections.defaultdict(list)
		for (a, b) in pairs:
			g[a].append(b)
			g[b].append(a)
		n = len(s)
		s = list(s)
		while g:
			(i, j) = g.popitem()
			visited = {i}
			visited.update(j)
			chars = collections.Counter()
			q = collections.deque(j)
			while q:
				i = q.popleft()
				if i in g:
					j = g.pop(i)
					q.extend(j)
					visited.update(j)
			visited = sorted(visited)
			for i in visited:
				chars[s[i]] += 1
			j = 0
			for c in sorted(chars):
				for k in range(chars[c]):
					s[visited[j]] = c
					j += 1
		return ''.join(s)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		parents = [i for (i, _) in enumerate(s)]

		def find(i):
			if i == parents[i]:
				return i
			parents[i] = find(parents[i])
			return parents[i]

		def union(i, j):
			(i, j) = (find(i), find(j))
			if i != j:
				parents[i] = parents[j]
		for (i, j) in pairs:
			union(i, j)
		groups = reduce(lambda group, i: group[find(i)].append(i) or group, range(len(s)), defaultdict(list))
		res = [0] * len(s)
		for items in groups.values():
			for (i, c) in zip(items, sorted((s[i] for i in items))):
				res[i] = c
		return ''.join(res)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		def dfs(i):
			visited[i] = True
			component.append(i)
			for j in adj_lst[i]:
				if not visited[j]:
					dfs(j)
		n = len(s)
		adj_lst = [[] for _ in range(n)]
		for (i, j) in pairs:
			adj_lst[i].append(j)
			adj_lst[j].append(i)
		visited = [False for _ in range(n)]
		lst = list(s)
		for i in range(n):
			if not visited[i]:
				component = []
				dfs(i)
				component.sort()
				chars = [lst[k] for k in component]
				chars.sort()
				for i in range(len(component)):
					lst[component[i]] = chars[i]
		return ''.join(lst)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		d = {}
		for (a, b) in pairs:
			if a not in d:
				d[a] = []
			if b not in d:
				d[b] = []
			d[a].append(b)
			d[b].append(a)

		def dfs(x, result):
			if x in d:
				result.append(x)
				for y in d.pop(x):
					dfs(y, result)
		s = list(s)
		while d:
			x = next(iter(d))
			result = []
			dfs(x, result)
			result = sorted(result)
			B = sorted([s[i] for i in result])
			for (i, b) in enumerate(B):
				s[result[i]] = b
		return ''.join(s)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		self.p = [i for i in range(n)]
		for (x, y) in pairs:
			self.union(x, y)
		dic = collections.defaultdict(list)
		for i in range(n):
			dic[self.find(i)].append(s[i])
		for k in dic.keys():
			dic[k] = sorted(dic[k])
		res = []
		for i in range(n):
			res.append(dic[self.find(i)].pop(0))
		return ''.join(res)

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

	def union(self, x, y):
		self.p[self.find(x)] = self.find(y)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		if not pairs:
			return s
		adj_list = {}
		visited = set()
		sub_string = ''
		sub_indices = []
		for i in range(len(pairs)):
			adj_list[pairs[i][0]] = adj_list.get(pairs[i][0], []) + [pairs[i][1]]
			adj_list[pairs[i][1]] = adj_list.get(pairs[i][1], []) + [pairs[i][0]]

		def dfs(index):
			nonlocal sub_string
			sub_string += s[index]
			sub_indices.append(index)
			visited.add(index)
			if index in adj_list:
				for neighbor in adj_list[index]:
					if neighbor not in visited:
						dfs(neighbor)
		for i in range(len(s)):
			sub_string = ''
			sub_indices = []
			if i not in visited:
				dfs(i)
				sub_string = sorted(sub_string)
				sub_indices.sort()
				for i in range(len(sub_indices)):
					s = s[:sub_indices[i]] + sub_string[i] + s[sub_indices[i] + 1:]
		return s


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

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

		def union(x, y):
			px = find(x)
			py = find(y)
			parent[px] = py
		parent = dict()
		for (i, j) in pairs:
			x = i
			y = j
			px = find(x)
			py = find(y)
			if px != py:
				union(x, y)
		graph = collections.defaultdict(list)
		for i in range(len(s)):
			px = find(i)
			heapq.heappush(graph[px], s[i])
		res = ''
		mem = collections.defaultdict(int)
		for i in range(len(s)):
			px = find(i)
			res += heapq.heappop(graph[px])
		return res


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		par = {i: i for i in range(len(s))}

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

		def union(x, y):
			(rx, ry) = (find(x), find(y))
			if rx != ry:
				par[rx] = ry
		for (x, y) in pairs:
			union(x, y)
		group2chars = defaultdict(list)
		for (idx, char) in enumerate(s):
			gid = find(idx)
			group2chars[gid].append(char)
		for gid in group2chars:
			group2chars[gid].sort(reverse=True)
		outstr = ''
		for (idx, char) in enumerate(s):
			gid = find(idx)
			outchar = group2chars[gid].pop()
			outstr += outchar
		return outstr


from collections import defaultdict
from typing import List

class DSU:

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

	def make_set(self, val):
		self.parent[val] = val
		self.size[val] = 1

	def get_parent(self, val):
		if self.parent[val] == val:
			return val
		parent = self.get_parent(self.parent[val])
		self.parent[val] = parent
		return parent

	def union(self, val1, val2):
		parent1 = self.get_parent(val1)
		parent2 = self.get_parent(val2)
		if parent1 != parent2 and self.size[parent1] >= self.size[parent2]:
			self.parent[parent2] = parent1
			self.size[parent1] += self.size[parent2]
		elif parent1 != parent2 and self.size[parent1] < self.size[parent2]:
			self.parent[parent1] = parent2
			self.size[parent2] += self.size[parent1]
		return True

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		dsu = DSU()
		for i in range(len(s)):
			dsu.make_set(i)
		for (x, y) in pairs:
			dsu.union(x, y)
		m = defaultdict(list)
		for i in range(len(s)):
			parent = dsu.get_parent(i)
			m[parent].append(s[i])
		for (key, list_val) in m.items():
			m[key] = sorted(list_val)
		res = []
		for j in range(len(s)):
			parent = dsu.get_parent(j)
			smallest_letter = m[parent].pop(0)
			res.append(smallest_letter)
		return ''.join(res)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		graph = defaultdict(list)
		visited = [False] * len(s)
		out = [None] * len(s)
		for (u, v) in pairs:
			graph[u].append(v)
			graph[v].append(u)

		def dfs(i, stash):
			visited[i] = True
			stash.append(i)
			for vertice in graph[i]:
				if not visited[vertice]:
					stash = dfs(vertice, stash)
			return stash
		for i in range(len(s)):
			if not visited[i]:
				indices = sorted(dfs(i, []))
				letters = sorted([s[i] for i in indices])
				for j in range(len(indices)):
					out[indices[j]] = letters[j]
		return ''.join(out)


import collections

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		self.uf_table = [idx for idx in range(len(s))]

		def find(p):
			if p != self.uf_table[p]:
				self.uf_table[p] = find(self.uf_table[p])
			return self.uf_table[p]
		for (p, q) in pairs:
			rp = find(p)
			rq = find(q)
			if rp != rq:
				self.uf_table[rp] = rq
		conn = collections.defaultdict(list)
		for (idx, p) in enumerate(self.uf_table):
			conn[find(p)].append(s[idx])
		for (k, v) in conn.items():
			conn[k] = sorted(v)
		result = []
		for idx in range(len(s)):
			result.append(conn[find(idx)].pop(0))
		return ''.join(result)


class DSU:

	def __init__(self, n):
		self.parent = list(range(n))

	def getP(self, i):
		if self.parent[i] != i:
			self.parent[i] = self.getP(self.parent[i])
			return self.parent[i]
		else:
			return i

	def rewrire(self):
		tops = set()
		for i in range(len(self.parent)):
			if i != self.parent[i]:
				self.parent[i] = self.getP(i)

	def merge(self, a, b):
		(pa, pb) = (self.getP(a), self.getP(b))
		if pa == pb:
			return
		if pa < pb:
			self.parent[pb] = pa
		else:
			self.parent[pa] = pb

	def connect(self, xs):
		for (a, b) in xs:
			self.merge(a, b)
		self.rewrire()

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		uf = DSU(n)
		uf.connect(pairs)
		group = defaultdict(list)
		for (i, pindex) in enumerate(uf.parent):
			group[pindex].append((s[i], i))
		r = [None] * n
		for (gk, gv) in list(group.items()):
			cxs = []
			ixs = []
			for (c, index) in gv:
				cxs.append(c)
				ixs.append(index)
			cxs.sort()
			ixs.sort()
			for i in range(len(ixs)):
				r[ixs[i]] = cxs[i]
		return ''.join(r)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		m = len(pairs)
		if n <= 1 or m == 0:
			return s
		parent = [i for i in range(n)]

		def find(i):
			pi = parent[i]
			while parent[pi] != pi:
				pi = parent[pi]
			parent[i] = pi
			return parent[i]

		def union(i, j):
			pi = find(i)
			pj = find(j)
			if pi != pj:
				parent[pj] = pi
		for (index1, index2) in pairs:
			union(index1, index2)
		groups = {}
		for index in range(n):
			leader = find(index)
			groups[leader] = groups.get(leader, [])
			groups[leader].append(s[index])
		for leader in groups.keys():
			groups[leader].sort()
		group_index = {}
		result = ''
		for index in range(n):
			leader = find(index)
			group_index[leader] = group_index.get(leader, 0) + 1
			result += groups[leader][group_index[leader] - 1]
		return result


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		p = {}

		def getP(i: int) -> int:
			if i not in p:
				return -1
			return i if p[i] == i else getP(p[i])
		uf = {}
		index = 0
		for (x, y) in pairs:
			px = getP(x)
			py = getP(y)
			if px == -1 and py == -1:
				p[x] = min(x, y)
				p[y] = min(x, y)
				uf[min(x, y)] = pairs[index]
			elif px == -1:
				uf[py].append(x)
				p[x] = py
			elif py == -1:
				uf[px].append(y)
				p[y] = px
			elif px != py:
				p[px] = min(px, py)
				p[py] = min(px, py)
				uf[min(px, py)] += uf.pop(max(px, py))
			index += 1
		ans = list(s)
		for k in list(uf.keys()):
			st = sorted(set(uf[k]))
			tmp = [s[i] for i in st]
			tmp.sort()
			idx = 0
			for i in st:
				ans[i] = tmp[idx]
				idx += 1
		return ''.join(ans)


from typing import List

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		g = [[] for _ in range(len(s))]
		for edge in pairs:
			g[edge[0]].append(edge[1])
			g[edge[1]].append(edge[0])
		visited = set()

		def f(i):
			if i in visited:
				return
			else:
				visited.add(i)
			idxes.append(i)
			chars.append(s[i])
			for adj in g[i]:
				f(adj)
		ans = [''] * len(s)
		for i in range(len(s)):
			if i in visited:
				continue
			idxes = []
			chars = []
			f(i)
			idxes.sort()
			chars.sort()
			for j in range(len(chars)):
				ans[idxes[j]] = chars[j]
		return ''.join(ans)


import collections
import functools
import heapq
import itertools
import sys
from functools import lru_cache
from typing import List
from fractions import gcd

class UFSet:

	def __init__(self, n):
		self.dp = [-1 for _ in range(n)]

	def find(self, x):
		if self.dp[x] < 0:
			return x
		self.dp[x] = self.find(self.dp[x])
		return self.dp[x]

	def union(self, x, y):
		(root_x, root_y) = (self.find(x), self.find(y))
		if root_x == root_y:
			return
		self.dp[root_x] += self.dp[root_y]
		self.dp[root_y] = root_x

	def get_group(self):
		ret = collections.defaultdict(list)
		for i in range(len(self.dp)):
			ret[self.find(i)].append(i)
		return ret

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		ufs = UFSet(n)
		for (i, j) in pairs:
			ufs.union(i, j)
		group_map = ufs.get_group()
		ret = [i for i in s]
		for group in list(group_map.values()):
			sort_group = sorted([s[i] for i in group])
			for (i, j) in zip(group, sort_group):
				ret[i] = j
		return ''.join(ret)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		uf = UF(n)
		for pair in pairs:
			uf.union(pair[0], pair[1])
		groups = collections.defaultdict(list)
		for i in range(n):
			r = uf.root(i)
			groups[r].append(i)
		res = ['' for _ in range(n)]
		for (r, group) in list(groups.items()):
			if len(group) == 1:
				res[r] = s[group[0]]
			else:
				temp = [s[i] for i in group]
				temp.sort()
				for (index, idx) in enumerate(sorted(group)):
					res[idx] = temp[index]
		return ''.join(res)

class UF:

	def __init__(self, n):
		self.parents = list(range(n))

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

	def union(self, x, y):
		px = self.find(x)
		py = self.find(y)
		if px != py:
			self.parents[px] = py

	def root(self, x):
		return self.find(x)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		parents = [i for i in range(len(s))]
		ranks = [1 for _ in range(len(s))]
		components = collections.defaultdict(list)

		def find(x):
			while x != parents[x]:
				parents[x] = parents[parents[x]]
				x = parents[x]
			return x

		def union(x, y):
			(px, py) = (find(x), find(y))
			if px == py:
				return False
			if ranks[px] > ranks[py]:
				parents[py] = px
			elif ranks[px] < ranks[py]:
				parents[px] = py
			else:
				parents[py] = px
				ranks[px] += 1
			return True
		for (a, b) in pairs:
			union(a, b)
		for i in range(len(parents)):
			components[find(i)].append(s[i])
		for comp_id in components:
			components[comp_id].sort(reverse=True)
		res = ''
		for i in range(len(s)):
			res += components[find(i)].pop()
		return res


class DSU:

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

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

	def union(self, x, y):
		(xroot, yroot) = (self.find(x), self.find(y))
		if xroot != yroot:
			self.parent[yroot] = xroot

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		dsu = DSU(n)
		ans = []
		m = collections.defaultdict(list)
		for (i, j) in pairs:
			dsu.union(i, j)
		for i in range(n):
			m[dsu.find(i)].append(s[i])
		for key in list(m.keys()):
			m[key].sort(reverse=True)
		for i in range(n):
			ans.append(m[dsu.find(i)].pop())
		return ''.join(ans)


from collections import defaultdict

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		class UF:

			def __init__(self, s):
				self.p = [i for i in range(len(s))]

			def union(self, x, y):
				self.p[self.find(x)] = self.find(y)

			def find(self, x):
				if x != self.p[x]:
					self.p[x] = self.find(self.p[x])
				return self.p[x]
		(res, cc, uf) = ([], defaultdict(list), UF(s))
		for (x, y) in pairs:
			uf.union(x, y)
		for (i, c) in enumerate(s):
			cc[uf.find(i)].append(c)
		for cc_id in cc.keys():
			cc[cc_id].sort(reverse=True)
		for i in range(len(s)):
			res.append(cc[uf.find(i)].pop())
		return ''.join(res)


class UnionFind(object):

	def __init__(self, n):
		self._parent = [0] * n
		self._size = [1] * n
		self.count = n
		for i in range(n):
			self._parent[i] = i

	def union(self, p, q):
		rootp = self.find(p)
		rootq = self.find(q)
		if rootp == rootq:
			return
		self.count -= 1
		if self._size[rootp] > self._size[rootq]:
			self._size[rootp] += self._size[rootq]
			self._parent[rootq] = self._parent[q] = rootp
		else:
			self._size[rootq] += self._size[rootp]
			self._parent[rootp] = self._parent[p] = rootq

	def find(self, n):
		while self._parent[n] != n:
			self._parent[n] = self._parent[self._parent[n]]
			n = self._parent[n]
		return n

	def connected(self, p, q):
		return self.find(p) == self.find(q)

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		N = len(s)
		if N < 2:
			return s
		uf = UnionFind(N)
		for pair in pairs:
			uf.union(pair[0], pair[1])
		dict = defaultdict(list)
		for i in range(N):
			r = uf.find(i)
			dict[r].append(i)
		res = [' '] * N
		for lst in list(dict.values()):
			subs = []
			for idx in lst:
				subs.append(s[idx])
			subs.sort()
			i2 = 0
			for idx in lst:
				res[idx] = subs[i2]
				i2 += 1
		return ''.join(res)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		dd = {x: x for x in [i for v in pairs for i in v]}

		def merge(x, y):
			(x, y) = (find(x), find(y))
			if x != y:
				dd[x] = y

		def find(x):
			if dd[x] != x:
				dd[x] = find(dd[x])
			return dd[x]
		for (i, x) in pairs:
			merge(i, x)
		agg = collections.defaultdict(list)
		for i in dd:
			agg[find(i)].append(s[i])
		for i in agg:
			agg[i] = sorted(agg[i], reverse=1)
		s = list(s)
		for i in range(len(s)):
			if i in dd:
				s[i] = agg[find(i)].pop()
		return ''.join(s)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		edges = collections.defaultdict(list)
		for p in pairs:
			edges[p[0]].append(p[1])
			edges[p[1]].append(p[0])
		ans = list(s)
		seen = set()
		for (i, c) in enumerate(s):
			if i in seen:
				continue
			seen.add(i)
			(h1, h2) = ([], [])
			frontier = [i]
			while frontier:
				cur = frontier.pop()
				heapq.heappush(h1, cur)
				heapq.heappush(h2, ans[cur])
				for j in edges[cur]:
					if j not in seen:
						seen.add(j)
						frontier.append(j)
			while h1:
				ans[heapq.heappop(h1)] = heapq.heappop(h2)
		return ''.join(ans)


from heapq import heappush, heappop

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		def parent(a):
			(val, _) = d[a]
			if val == a:
				return a
			return parent(val)

		def union(a, b):
			parent1 = parent(a)
			parent2 = parent(b)
			if parent1 == parent2:
				return
			(a, n1) = d[parent1]
			(b, n2) = d[parent2]
			if n1 > n2:
				d[b] = (a, n2)
				d[a] = (a, n1 + n2)
			else:
				d[a] = (b, n1)
				d[b] = (b, n1 + n2)
		d = [(i, 1) for i in range(len(s))]
		for (i, j) in pairs:
			union(i, j)
		arrs = [[] for _ in range(len(s))]
		for i in range(len(s)):
			heappush(arrs[parent(i)], s[i])
		sol = list()
		for i in range(len(s)):
			sol.append(heappop(arrs[parent(i)]))
		return ''.join(sol)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		res = list(s)
		adj = defaultdict(set)
		for (a, b) in pairs:
			adj[a].add(b)
			adj[b].add(a)
		while adj:
			i = next(iter(adj))
			v = []
			self.dfs(i, adj, v)
			v = sorted(v)
			chars = sorted([s[i] for i in v])
			for (i, c) in enumerate(chars):
				res[v[i]] = c
		return ''.join(res)

	def dfs(self, i, adj, res):
		if i in adj:
			res.append(i)
			for j in adj.pop(i):
				self.dfs(j, adj, res)


from collections import defaultdict

class DisjointSet:

	class Node:

		def __init__(self, x):
			self.val = x
			self.parent = self
			self.rank = 0

	def __init__(self, node_num):
		self.val_to_node = {}
		for val in range(node_num):
			self.val_to_node[val] = DisjointSet.Node(val)

	def find(self, x):
		return self._find(self.val_to_node[x]).val

	def _find(self, node):
		if node.parent is node:
			return node
		node.parent = self._find(node.parent)
		return node.parent

	def union(self, val1, val2):
		root1 = self._find(self.val_to_node[val1])
		root2 = self._find(self.val_to_node[val2])
		if root1 is root2:
			return
		if root2.rank > root1.rank:
			(root1, root2) = (root2, root1)
		if root1.rank == root2.rank:
			root1.rank += 1
		root2.parent = root1

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		if not pairs:
			return s
		disjoint_set = DisjointSet(len(s))
		for (u, v) in pairs:
			disjoint_set.union(u, v)
		connected_components = defaultdict(list)
		for i in range(len(s)):
			connected_components[disjoint_set.find(i)].append(i)
		res = [None] * len(s)
		for group in list(connected_components.values()):
			sorted_chars = sorted([s[i] for i in group])
			for (idx, s_i) in enumerate(sorted(group)):
				res[s_i] = sorted_chars[idx]
		return ''.join(res)


par = [0] * 100005
rank = [1] * 100005

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

def union(x, y):
	xs = find(x)
	ys = find(y)
	if xs != ys:
		if rank[xs] < rank[ys]:
			par[xs] = ys
		elif rank[xs] > rank[ys]:
			par[ys] = xs
		else:
			par[ys] = xs
			rank[xs] += 1

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		n = len(s)
		for i in range(n + 3):
			rank[i] = 1
			par[i] = i
		for i in pairs:
			union(i[0], i[1])
		poi = [0] * (n + 3)
		for i in range(n):
			par[i] = find(par[i])
		ans = [[] for i in range(n + 3)]
		for i in range(n):
			ans[par[i]].append(s[i])
		for i in range(n):
			ans[i].sort()
		fin = ''
		for i in range(n):
			tmp = par[i]
			fin += ans[tmp][poi[tmp]]
			poi[tmp] += 1
		return fin


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		class UF:

			def __init__(self, n):
				self.p = list(range(n))

			def union(self, x, y):
				self.p[self.find(x)] = self.find(y)

			def find(self, x):
				if x != self.p[x]:
					self.p[x] = self.find(self.p[x])
				return self.p[x]
		(union_find, result, group) = (UF(len(s)), [], defaultdict(list))
		for pair in pairs:
			union_find.union(pair[0], pair[1])
		for i in range(len(s)):
			group[union_find.find(i)].append(s[i])
		for comp_id in list(group.keys()):
			group[comp_id].sort(reverse=True)
		for i in range(len(s)):
			result.append(group[union_find.find(i)].pop())
		return ''.join(result)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		l = len(s)
		union_find = [i for i in range(l)]
		union_set = {}
		for i in range(l):
			union_set[i] = [i]
		for p in pairs:
			x = p[0]
			y = p[1]
			(t, t1) = (union_find[y], union_find[x])
			if union_find[x] < union_find[y]:
				(t, t1) = (union_find[x], union_find[y])
			if t == t1:
				continue
			for i in union_set[t1]:
				union_set[t].append(i)
				union_find[i] = t
			union_set[t1] = []
		print(union_find)
		print(union_set)
		res_cand = {}
		for (k, v) in list(union_set.items()):
			union_set = []
			for i in v:
				union_set.append(s[i])
			union_set.sort(reverse=True)
			res_cand[k] = union_set
		print(res_cand)
		res = ''
		for i in range(l):
			res = res + res_cand[union_find[i]][-1]
			res_cand[union_find[i]].pop()
		return res


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		def dfs(u, cc):
			cc.append(u)
			visited_set.add(u)
			if u in graph:
				for v in graph[u]:
					if v not in visited_set:
						dfs(v, cc)
		if len(pairs) == 0:
			return s
		graph = {}
		for (u, v) in pairs:
			if u in graph:
				graph[u].append(v)
			else:
				graph[u] = [v]
			if v in graph:
				graph[v].append(u)
			else:
				graph[v] = [u]
		result = [c for c in s]
		visited_set = set()
		for u in graph:
			if u not in visited_set:
				cc = []
				dfs(u, cc)
				cc.sort()
				auxr = [s[i] for i in cc]
				auxr.sort()
				for (i, index) in enumerate(cc):
					result[index] = auxr[i]
		return ''.join(result)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		def dfs(u, cc):
			visited_set[u] = cc
			if u in graph:
				for v in graph[u]:
					if visited_set[v] == 0:
						dfs(v, cc)
		if len(pairs) == 0:
			return s
		graph = {}
		for (u, v) in pairs:
			if u in graph:
				graph[u].append(v)
			else:
				graph[u] = [v]
			if v in graph:
				graph[v].append(u)
			else:
				graph[v] = [u]
		visited_set = [0 for i in range(len(s))]
		cc = 0
		for u in graph:
			if visited_set[u] == 0:
				cc += 1
				dfs(u, cc)
		dd = defaultdict(list)
		result = [c for c in s]
		for (i, key) in enumerate(visited_set):
			if key != 0:
				dd[key].append(s[i])
		for key in dd:
			dd[key].sort(reverse=True)
		for (i, key) in enumerate(visited_set):
			if key != 0:
				result[i] = dd[key].pop()
		return ''.join(result)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		g = collections.defaultdict(list)
		for (a, b) in pairs:
			g[a].append(b)
			g[b].append(a)

		def find(i, idx):
			for k in g[i]:
				if not visited[k]:
					visited[k] = 1
					idx.append(k)
					find(k, idx)
		n = len(s)
		s = list(s)
		visited = [0] * n
		for i in range(n):
			if visited[i]:
				continue
			visited[i] = 1
			idx = [i]
			find(i, idx)
			idx.sort()
			chars = [s[j] for j in idx]
			chars.sort()
			for (j, c) in zip(idx, chars):
				s[j] = c
		return ''.join(s)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		def dfs(u, cc):
			visited_set[u] = cc
			if u in graph:
				for v in graph[u]:
					if visited_set[v] == 0:
						dfs(v, cc)
		if len(pairs) == 0:
			return s
		graph = {}
		for (u, v) in pairs:
			if u in graph:
				graph[u].append(v)
			else:
				graph[u] = [v]
			if v in graph:
				graph[v].append(u)
			else:
				graph[v] = [u]
		visited_set = [0 for i in range(len(s))]
		cc = 0
		for u in graph:
			if visited_set[u] == 0:
				cc += 1
				dfs(u, cc)
		dd = {}
		result = [c for c in s]
		for (i, key) in enumerate(visited_set):
			if key != 0:
				if key in dd:
					heapq.heappush(dd[key], s[i])
				else:
					dd[key] = [s[i]]
		for (i, key) in enumerate(visited_set):
			if key != 0:
				result[i] = heapq.heappop(dd[key])
		return ''.join(result)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		def dfs(root, res):
			if letters[root] == 1:
				return
			letters[root] = 1
			res.append(root)
			for node in graph[root]:
				dfs(node, res)
		letters = [0] * len(s)
		graph = [[] for _ in range(len(s))]
		for (a, b) in pairs:
			graph[a].append(b)
			graph[b].append(a)
		res = list(s)
		for i in range(len(s)):
			if letters[i] == 0:
				visited = []
				dfs(i, visited)
				nodes = []
				for node in visited:
					nodes.append(res[node])
				nodes.sort()
				visited.sort()
				for (node, index) in zip(nodes, visited):
					res[index] = node
		return ''.join(res)


class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		graph = defaultdict(list)
		for (node, neigbor) in pairs:
			graph[node].append(neigbor)
			graph[neigbor].append(node)
		visited = set()

		def dfs(index):
			if index not in visited:
				visited.add(index)
				newgroup.add(index)
				for neigbor in graph[index]:
					dfs(neigbor)
		n = len(s)
		result = [None] * n
		for i in range(n):
			newgroup = set()
			dfs(i)
			subseq = [s[i] for i in newgroup]
			subseq.sort()
			for (letter, index) in zip(subseq, sorted(newgroup)):
				result[index] = letter
		return ''.join(result)


from collections import defaultdict

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		array = [char for char in s]
		edges = defaultdict(list)
		for (i, j) in pairs:
			edges[i].append(j)
			edges[j].append(i)
		parents = {}
		components = defaultdict(list)
		for i in range(len(pairs)):
			for j in edges[i]:
				self.union(i, j, parents)
		for (child, parent) in list(parents.items()):
			components[self.find(parent, parents)].append(child)
		print(parents)
		print(components)
		for (parent, children) in list(components.items()):
			tmp = sorted([array[child] for child in children])
			print(tmp)
			components[parent] = sorted(children)
			for k in range(len(children)):
				array[components[parent][k]] = tmp[k]
		return ''.join(array)

	def union(self, i, j, parents):
		if not parents.get(i):
			parents[i] = i
		if not parents.get(j):
			parents[j] = j
		(pi, pj) = (self.find(i, parents), self.find(j, parents))
		parents[pj] = pi
		parents[i] = pi

	def find(self, i, parents):
		while parents[i] != i:
			parents[i] = parents[parents[i]]
			i = parents[i]
		return parents[i]


from collections import defaultdict

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		def find(node):
			path = []
			while root[node] != node:
				path.append(node)
				node = root[node]
			for n in path:
				root[n] = node
			return node

		def union(a, b):
			(r1, r2) = (find(a), find(b))
			if r1 != r2:
				root[r1] = r2
		root = {i: i for i in range(len(s))}
		for (a, b) in pairs:
			union(a, b)
		root_to_char = defaultdict(list)
		for k in list(root.keys()):
			root_to_char[find(k)].append(s[k])
		for v in list(root_to_char.values()):
			v.sort(reverse=True)
		res = []
		for i in range(len(s)):
			res.append(root_to_char[root[i]].pop())
		return ''.join(res)


class UnionFind:

	def __init__(self, n):
		self.parents = [i for i in range(n)]
		self.rank = [0] * n

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

	def union(self, x, y):
		self.parents[self.find(x)] = self.find(y)

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
		UF = UnionFind(len(s))
		res = []
		for (x, y) in pairs:
			UF.union(x, y)
		parent_to_heap = collections.defaultdict(list)
		for (i, p) in enumerate(UF.parents):
			heapq.heappush(parent_to_heap[UF.find(p)], s[i])
		for (i, p) in enumerate(UF.parents):
			res.append(heapq.heappop(parent_to_heap[UF.find(p)]))
		return ''.join(res)


class UF:

	def __init__(self, N):
		self.N = N
		self.parent = [i for i in range(N)]
		self.rank = [0 for i in range(N)]

	def union(self, a, b):
		ra = self.find(a)
		rb = self.find(b)
		if ra != rb:
			self.parent[ra] = rb

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

class Solution:

	def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:

		class UF:

			def __init__(self, n):
				self.p = list(range(n))

			def union(self, x, y):
				self.p[self.find(x)] = self.find(y)

			def find(self, x):
				if x != self.p[x]:
					self.p[x] = self.find(self.p[x])
				return self.p[x]
		(uf, res, m) = (UF(len(s)), [], defaultdict(list))
		for (x, y) in pairs:
			uf.union(x, y)
		for i in range(len(s)):
			m[uf.find(i)].append(s[i])
		for comp_id in list(m.keys()):
			m[comp_id].sort(reverse=True)
		for i in range(len(s)):
			res.append(m[uf.find(i)].pop())
		return ''.join(res)