SP15562 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)

T : number of test cases (T

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