IITKWPCI - Find Lexicographically Smallest Permutation

no tags 

You are given n numbers a1, a2, ... an. You have to permute the numbers in such a way that resulting permutation should be lexicographically smallest . But there is a problem, you can not swap every pair of numbers. You can only swap the position i and j if they are good position. You will be given m pairs of i and j's which will denote good positions.

So complying to restrictions posed here, find the lexicographically smallest permutation of a1, a2 ... an.

Definition:  (a1, a2 ... an) is lexicographically smaller than (b1, b2 ... bn) if first index i where ai and bi differs, ai < bi satisfies.

eg. (1, 2, 3, 4) is smaller than (2, 1, 3, 4)

Input

T : number of test cases (T <= 10)

Next Line will contain n and m. (1 <= n <= 10^3 and 0 <= m <= min (n * (n - 1) / 2, 10^5).

Next Line will contains a1, a2, ... an. (a[i] >= 1 && a[i] <=10^6)

For next m lines, each line will contain i, j separated by space which will denote that you can swap ai and aj.

Output

For each test case, output n numbers representing the permutation of a1, a2 ... an according to problem statement.

Example

Input:
2
3 1
3 2 1
2 3
4 2
2 4 3 1
1 3
3 4
Output: 3 1 2
1 4 2 3

hide comments
cpchef7: 2022-01-28 08:18:12

AC in one go, all the connected good positions can be interchanged, done with dfs and visited array

nadstratosfer: 2021-04-05 06:50:23

Beware of blanklines in input when solving with Python.

codingjedi048: 2021-04-04 11:31:51

Very Cool Problem. Actually I'm Just in Learning DSU...
After solving this Problem, feeling my progression is Going well.
ACC in one go...

manujk: 2020-09-22 16:12:45

DSU + Map

Aditya Joshi: 2014-11-28 10:53:39

Nice one.

Hasil Sharma: 2014-01-07 10:18:44

Beautiful Problem :)

Piyush Kapoor: 2013-12-26 14:23:48

This problem was asked in Facebook coding round for hiring at my college last year. Also similar problem asked in TwitchTV challenge (https://twitchtvchallenge.interviewstreet.com/challenges/dashboard/#problem/4fa4e6c9b4464)

Miguel Oliveira: 2013-08-20 14:02:52

cool problem :)


Added by:praveen123
Date:2013-08-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge