You are given a permutation of the numbers 1, 2, ..., n and m pairs of positions (a_{j}, b_{j}).

At each step you can choose a pair from the given positions and swap the numbers in that positions. What is the lexicographically maximal permutation one can get?

Let p and q be two permutations of the numbers 1, 2, ..., n. p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so p_{k} = q_{k} for 1 ≤ k < i and p_{i} < q_{i}.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^6) — the length of the permutation p and the number of pairs of positions.

The second line contains n distinct integers p_{i} (1 ≤ p_{i} ≤ n) — the elements of the permutation p.

Each of the last m lines contains two integers (a_{j}, b_{j}) (1 ≤ a_{j}, b_{j} ≤ n) — the pairs of positions to swap. Note that you are given a positions, not the values to swap.


-----Output-----

Print the only line with n distinct integers p'_{i} (1 ≤ p'_{i} ≤ n) — the lexicographically maximal permutation one can get.


-----Example-----
Input
9 6
1 2 3 4 5 6 7 8 9
1 4
4 7
2 5
5 8
3 6
6 9

Output
7 8 9 4 5 6 1 2 3

Difficulty: MEDIUM_HARD
Tags: Spanning trees

Graph traversal

Mathematics

Starter code:

Solutions:
import sys
(n, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split(' '))
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split(' ')))
adj = [[] for _ in range(n)]
for (u, v) in (map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer):
	adj[u - 1].append(v - 1)
	adj[v - 1].append(u - 1)
visited = [0] * n
for i in range(n):
	if visited[i]:
		continue
	visited[i] = 1
	num = [a[i]]
	i_list = [i]
	stack = [i]
	while stack:
		v = stack.pop()
		for dest in adj[v]:
			if not visited[dest]:
				visited[dest] = 1
				num.append(a[dest])
				i_list.append(dest)
				stack.append(dest)
	num.sort(reverse=True)
	i_list.sort()
	for (j, v) in zip(i_list, num):
		a[j] = v
sys.stdout.buffer.write(' '.join(map(str, a)).encode('utf-8'))


from collections import defaultdict
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
parent = [i for i in range(N)]
rank = [0] * N

def find(i):
	if parent[i] == i:
		return i
	else:
		parent[i] = find(parent[i])
		return parent[i]

def same(x, y):
	return find(x) == find(y)

def unite(x, y):
	x = find(x)
	y = find(y)
	if x == y:
		return
	if rank[x] > rank[y]:
		parent[y] = x
	else:
		parent[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1
P = list(map(int, input().split()))
for i in range(M):
	(a, b) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	unite(a, b)
d = defaultdict(list)
cnt = defaultdict(int)
for i in range(N):
	d[find(i)].append(P[i])
for i in range(N):
	if find(i) == i:
		d[i] = sorted(d[i], reverse=True)
ans = []
for i in range(N):
	k = find(i)
	ans.append(d[k][cnt[k]])
	cnt[k] += 1
print(' '.join(map(str, ans)))


from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
from random import *
from itertools import permutations
input = stdin.readline
prin = stdout.write
from random import sample
from collections import Counter, deque
from fractions import *
from math import sqrt, ceil, log2, gcd, cos, pi, floor
from copy import deepcopy
mod = 10 ** 9 + 7
mod2 = 998244353

class DisjSet:

	def __init__(self, n):
		self.rank = [1] * 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):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			return
		if self.rank[xset] < self.rank[yset]:
			self.parent[xset] = yset
		elif self.rank[xset] > self.rank[yset]:
			self.parent[yset] = xset
		else:
			self.parent[yset] = xset
			self.rank[xset] = self.rank[xset] + 1

def ps(n):
	cp = 0
	lk = 0
	arr = {}
	lk = 0
	ap = n
	cc = 0
	while n % 2 == 0:
		n = n // 2
		cc = 1
	if cc == 1:
		lk += 1
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		cc = 0
		while n % ps == 0:
			n = n // ps
			cc = 1
		lk += 1 if cc == 1 else 0
	if n != 1:
		lk += 1
	if lk == 1:
		return False
	return True

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n):
		qlr = qlr * ip % mod
	for ij in range(1, r):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def power(arr):
	listrep = arr
	subsets = []
	for i in range(2 ** len(listrep)):
		subset = []
		for k in range(len(listrep)):
			if i & 1 << k:
				subset.append(listrep[k])
		subsets.append(subset)
	return subsets

def pda(n):
	list = []
	su = 0
	for i in range(1, int(sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				list.append(i)
				su += i
			else:
				list.append(n // i)
				list.append(i)
				su += i
				su += n // i
	return su

def dis(xa, ya, xb, yb):
	return sqrt((xa - xb) ** 2 + (ya - yb) ** 2)

def ii():
	return int(input())

def ilist():
	return [int(x) for x in input().strip().split()]

def islist():
	return list(map(str, input().split().rstrip()))

def inp():
	return input().strip()

def google(test):
	return 'Case #' + str(test) + ': '

def overlap(x1, y1, x2, y2):
	if x2 > y1:
		return y1 - x2
	if y1 > y2:
		return y2 - x2
	return y1 - x2

def dist(x1, y1, x2, y2):
	return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	ans = []
	for i in range(1, n + 1):
		if prime[i]:
			ans.append(i)
	return ans

def prod(arr):
	n = len(arr)
	k = 1
	for j in range(n):
		k *= arr[j]
	return k

def SumOfDigits(s):
	su = 0
	while s:
		su += s % 10
		s = s // 10
	return su

def std():
	return stdout.flush()

def finds(s):
	att = 0
	i = 1
	while i < len(s):
		att = int(s[:i])
		j = i
		cc = 0
		while j < len(s):
			att += 1
			sk = att
			news = str(sk)
			rr = len(news)
			if news == s[j:j + rr]:
				j += rr
			else:
				cc = 1
				break
		if cc == 0:
			return True
		i += 1
	return False
arr = []
for i in range(1, 10001):
	s = str(i)
	j = i
	while len(s) <= 7:
		j += 1
		s += str(j)
		arr.append(int(s))
arr.sort()

def subs(arr):
	res = set()
	pre = {0}
	for x in arr:
		pre = {x | y for y in pre} | {x}
		res |= pre
	return len(res)

def sl(n):
	return n * (n + 1) // 2
t = 1
for pl in range(t):
	(n, m) = ilist()
	arr = ilist()
	ob = DisjSet(n)
	for i in range(m):
		(a, b) = ilist()
		a -= 1
		b -= 1
		ob.union(a, b)
	finds = [0] * n
	for i in range(n):
		finds[i] = ob.find(i)
	dicts = {}
	for i in range(n):
		if finds[i] in dicts:
			dicts[finds[i]].append(i)
		else:
			dicts[finds[i]] = [i]
	brr = [0] * n
	for ij in dicts:
		temp = dicts[ij]
		news = []
		for pj in temp:
			news.append(arr[pj])
		news.sort()
		news = news[::-1]
		co = 0
		for jj in temp:
			brr[jj] = news[co]
			co += 1
	print(*brr)


from sys import stdout, stdin, setrecursionlimit
from bisect import insort, bisect_right, bisect_left
from io import BytesIO, IOBase
from collections import *
from itertools import *
from random import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def primeNums():
	N = 10 ** 5
	SN = int(sqrt(N))
	sieve = [i for i in range(N + 1)]
	sieve[1] = 0
	for i in sieve:
		if i > SN:
			break
		if i == 0:
			continue
		for j in range(2 * i, N + 1, i):
			sieve[j] = 0
	prime = [i for i in range(N + 1) if sieve[i] != 0]
	return prime

def primeFactor(n):
	lst = []
	mx = int(sqrt(n)) + 1
	for i in prime:
		if i > mx:
			break
		while n % i == 0:
			lst.append(i)
			n //= i
	if n > 1:
		lst.append(n)
	return lst
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
(n, m) = zzz()
arr = [0] + zzz()
for i in range(n):
	graph[i + 1] = []
for _ in range(m):
	(x, y) = zzz()
	graph[x].append(y)
	graph[y].append(x)
vis = [0] * (n + 1)

def dfs(u):
	lst = [arr[u]]
	ind = [u]
	que = deque([u])
	vis[u] = 1
	while que:
		p = que.pop()
		for i in graph[p]:
			if vis[i]:
				continue
			lst.append(arr[i])
			vis[i] = 1
			ind.append(i)
			que.append(i)
	lst = sorted(lst, reverse=True)
	ind = sorted(ind)
	for (i, j) in zip(lst, ind):
		arr[j] = i
for i in range(1, n + 1):
	if vis[i]:
		continue
	dfs(i)
print(*arr[1:])


import sys
input = sys.stdin.readline

def make_set(v):
	parent[v] = v

def find_set(v):
	if v == parent[v]:
		return v
	else:
		parent[v] = find_set(parent[v])
		return parent[v]

def union_sets(a, b):
	a = find_set(a)
	b = find_set(b)
	if a != b:
		if rank[a] < rank[b]:
			(a, b) = (b, a)
		parent[b] = a
		if rank[a] == rank[b]:
			rank[a] += 1
(n, m) = list(map(int, input().split()))
arr = list(map(int, input().split()))
parent = [i for i in range(n)]
rank = [0] * n
for i in range(m):
	(a, b) = list(map(int, input().split()))
	a = a - 1
	b = b - 1
	union_sets(a, b)
b = {}
for i in range(n):
	if find_set(i) not in b.keys():
		b[find_set(i)] = []
	b[find_set(i)].append(i)
e = [0] * n
for i in b:
	b[i].sort()
	c = []
	for j in range(len(b[i])):
		c.append(arr[b[i][j]])
	c.sort(reverse=True)
	for j in range(len(b[i])):
		e[b[i][j]] = c[j]
print(*e)


import os, sys
from io import BytesIO, IOBase

def solve(n, p, path):
	(se, x, fin) = ([1] * (n + 1), 1, [0] * n)
	while x != len(se):
		(se[x], jj, curr, inde, vals) = (0, 0, [x], [x - 1], [p[x - 1]])
		while jj != len(curr):
			zz = curr[jj]
			for y in path[zz]:
				if se[y]:
					curr.append(y)
					inde.append(y - 1)
					vals.append(p[y - 1])
					se[y] = 0
			jj += 1
		inde.sort()
		vals.sort()
		for (ind, i) in enumerate(inde):
			fin[i] = vals[-ind - 1]
		while x != n + 1 and (not se[x]):
			x += 1
	for i in fin:
		print(i, end=' ')

def main():
	(n, m) = map(int, input().split())
	p = list(map(int, input().split()))
	path = [[] for _ in range(n + 1)]
	for _ in range(m):
		(u1, v1) = map(int, input().split())
		path[u1].append(v1)
		path[v1].append(u1)
	solve(n, p, path)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import atexit, io, sys, collections, math, heapq, fractions, copy, os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = list(map(int, input().split()))
pis = list(map(int, input().split()))
(parent, size) = ([i for i in range(n)], [1 for i in range(n)])

def f(u, parent):
	if parent[u] != u:
		parent[u] = f(parent[u], parent)
	return parent[u]
for _ in range(k):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	(pu, pv) = (f(u, parent), f(v, parent))
	if pu != pv:
		if size[pu] <= size[pv]:
			parent[pu] = pv
			size[pv] += size[pu]
		else:
			parent[pv] = pu
			size[pu] += size[pv]
cc = collections.defaultdict(list)
for u in range(len(pis)):
	cc[f(u, parent)].append(pis[u])
h = [0 for _ in range(n)]
for k in cc:
	cc[k].sort()
	h[k] = len(cc[k])
for u in range(len(pis)):
	pu = f(u, parent)
	h[pu] -= 1
	pis[u] = cc[pu][h[pu]]
print(' '.join(list(map(str, pis))))


from collections import defaultdict as df
from sys import stdin, stdout
from collections import deque
p = set()
(n, m) = list(map(int, stdin.readline().split()))
a = list(map(int, stdin.readline().rstrip().split()))
a.insert(0, 0)
d = df(list)
visited = [0] * (n + 1)
for i in range(m):
	(c, l) = list(map(int, stdin.readline().split()))
	if c == l:
		continue
	if (min(c, l), max(c, l)) not in p:
		p.add((min(c, l), max(c, l)))
		d[c].append(l)
		d[l].append(c)
mainans = [0] * (n + 1)
for i in range(1, n + 1):
	if visited[i] == False:
		ans = []
		motagota = []
		h = deque()
		ans.append(a[i])
		motagota.append(i)
		visited[i] = True
		h.append(i)
		while len(h) > 0:
			g = h.pop()
			for j in d[g]:
				if visited[j] == False:
					visited[j] = True
					ans.append(a[j])
					motagota.append(j)
					h.append(j)
		ans.sort(reverse=True)
		motagota.sort()
		for j in range(len(ans)):
			mainans[motagota[j]] = ans[j]
mainans.pop(0)
for i in range(len(mainans)):
	stdout.write(str(mainans[i]) + ' ')