# Strict Permutation CodeChef Solution

### We Are Discuss About 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(1XiN)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 1KiYi1≤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(1iN)i(1≤i≤N) such that A1=B1,A1=B1, A2=B2,A2=B2, ,…, Ai1=Bi1,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

### Constraints

• 1T1051≤T≤105
• 1N1051≤N≤105
• 1MN1≤M≤N
• 1Xi,YiN1≤Xi,Yi≤N
• XiXjXi≠Xj for each 1i<jM1≤i<j≤M.
• The sum of NN over all test cases won’t exceed 21052⋅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


## 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.

## 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