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: interview

Starter code:

Solutions:
from collections import defaultdict
import sys
input = sys.stdin.readline
N, M = list(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 = list(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 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)))

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)