[Solution] Strict Permutation solution codechef

Strict Permutation solution codechef – You are given an integer NN. You have to find a permutation PP of the integers {1,2,…,N}{1,2,…,N} that satisfies MM conditions of the following form:

• (Xi,Yi)(Xi,Yi), denoting that the element Xi(1≤Xi≤N)Xi(1≤Xi≤N) must appear in the prefix of length YiYi. Formally, if the index of the element XiXi is KiKi (i.e, PKi=XiPKi=Xi), then the condition 1≤Ki≤Yi1≤Ki≤Yi must hold.

[Solution] Strict Permutation solution codechef

Print -1 if no such permutation exists. In case multiple permutations that satisfy all the conditions exist, find the lexicographically smallest one.

Note: If two arrays AA and BB have the same length NN, then AA is called lexicographically smaller than BB only if there exists an index i(1≤i≤N)i(1≤i≤N) such that A1=B1,A1=B1, A2=B2,A2=B2, …,…, Ai−1=Bi−1,Ai<BiAi−1=Bi−1,Ai<Bi.

Input Format

• The first line of input will contain a single integer TT, denoting the number of test cases.
• The first line of each test case contains two space-separated integers NN and MM — the length of permutation and the number of conditions to be satisfied respectively.
• The next MM lines describe the conditions. The ii-th of these MM lines contains two space-separated integers XiXi and YiYi.

Output Format

For each test case, output a single line containing the answer:

• If no permutation satisfies the given conditions, print −1.
• Otherwise, print NN space-separated integers, denoting the elements of the permutation. If there are multiple answers, output the lexicographically smallest one.

[Solution] Strict Permutation solution codechef

• 1≤T≤1051≤T≤105
• 1≤N≤1051≤N≤105
• 1≤M≤N1≤M≤N
• 1≤Xi,Yi≤N1≤Xi,Yi≤N
• Xi≠XjXi≠Xj for each 1≤i<j≤M1≤i<j≤M.
• The sum of NN over all test cases won’t exceed 2⋅1052⋅105.

Sample Input 1 

4
3 2
2 1
1 2
4 3
1 2
4 1
3 2
4 1
2 3
5 2
5 4
3 2

Sample Output 1 

2 1 3
-1
1 2 3 4
1 3 2 5 4

[Solution] Strict Permutation solution codechef Explanation

Test case 11: The only permutation of length 33 that satisfies all the conditions is [2,1,3][2,1,3].

Test case 22: There is no permutation of length 44 that satisfies all the given conditions.

Test case 33: There are many permutations of length 44 that satisfy all the conditions, such as [1,2,3,4],[1,4,2,3],[1,3,2,4],[2,1,4,3],[2,1,3,4][1,2,3,4],[1,4,2,3],[1,3,2,4],[2,1,4,3],[2,1,3,4], etc. [1,2,3,4][1,2,3,4] is the lexicographically smallest among them.

For Solution

“Click Here“