Strict Permutation CodeChef Solution


Strict Permutation CodeChef Solution

Strict Permutation CodeChef Solution

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.

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.

Strict Permutation CodeChef Solution


  • 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 

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 2 3 4
1 3 2 5 4


Strict Permutation CodeChef Solution

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.


Strict Permutation CodeChef Solution


Strict Permutation CodeChef Solution


Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

Related Posts

Leave a Reply

Your email address will not be published.