Valid Arrangement of Pairs

Hard

0/120

Contributed by

6 upvotes

Problem statement

You are given a 2-d integer array (0-based indexing) “pairs”, where pairs[i] = [ starti, endi ]. Your task is to arrange the given pairs such that for every ‘i’ where 1 <= i <= pairs.length, the endi-1 is equal to starti

Note:

The input is generated in such a way that the answer always exists.

If there are multiple answers print any of them.

Example:

If pairs = [ [1,2] , [3,1] , [2,3] ] then the following arrangement is valid:

Arrangement =  [ [1,2] , [2,3] , [3,1] ] here, you can see for every ‘i’ where 1 <= i <= 2, the endi-1 is equal to starti

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an Integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. 

The first line of each test case contains a single integer ‘N’, denoting the number of pairs.

Then next ‘N’ lines follow in each test case. The ith line consists of two space-separated integers ‘start’ and ‘end’ representing the start and end of the ith pair.

Output Format :

For each test case, print the ‘N’ lines.  The ith line consists of two space-separated integers ‘start’ and ‘end’ representing the start and end of the arranged pair.

Print a separate line for each test case.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 5 * 10^4
0 <= start , end <= 10^9
starti != endi
No two pairs are exactly the same.

Time limit: 1 sec

Sample Input 1 :

Sample output 1 :

Explanation For Sample Output 1:

For the first test case, pairs = [ [1,2] , [3,1] , [2,3] ] then the following arrangement is valid:
Arrangement =  [ [1,2] , [2,3] , [3,1] ] here, you can see for every ‘i’ where 1 <= i <= 2, the endi-1 is equal to start   

For the second test case, pairs =  [1,2], here the given pair is itself a valid pair.

Sample Input 2 :

Sample output 2 :

Console