IITKWPCI  Find Lexicographically Smallest Permutation
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 seperated 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
Aditya Joshi:
20141128 10:53:39
Nice one. 

Hasil Sharma:
20140107 10:18:44
Beautiful Problem :) 

Piyush Kapoor:
20131226 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:
20130820 14:02:52
cool problem :) 
Added by:  praveen123 
Date:  20130805 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  IITK ACA CSE online judge 