[Solution] Strict Permutation CodeChef Solution

You are given an integer N$N$. You have to find a permutation P$P$ of the integers {1,2,…,N}$\{1,2,\dots ,N\}$ that satisfies M$M$ conditions of the following form:

• (Xi,Yi)$(X_i,Y_i)$, denoting that the element Xi(1≤Xi≤N)$X_i(1\le X_i\le N)$ must appear in the prefix of length Yi$Y_i$. Formally, if the index of the element Xi$X_i$ is Ki$K_i$ (i.e, PKi=Xi$P_{K_i}=X_i$), then the condition 1≤Ki≤Yi$1\le K_i\le Y_i$ 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 A$A$ and B$B$ have the same length N$N$, then A$A$ is called lexicographically smaller

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 than B$B$ only if there exists an index i(1≤i≤N)$i(1\le i\le N)$ such that A1=B1,$A_1=B_1,$ A2=B2,$A_2=B_2,$ …,$\dots ,$ Ai−1=Bi−1,Ai<Bi$A_{i-1}=B_{i-1},A_i<B_i$.

Input Format

• The first line of input will contain a single integer T$T$, denoting the number of test cases.

Passes for Fair CodeChef Solution

Fill Candies CodeChef Solution

Buy Lamps CodeChef Solution

Make Palindrome 2 CodeChef Solution

Fill The Grid CodeChef Solution

Positive array CodeChef Solution

Strict Permutation CodeChef Solution

• The first line of each test case contains two space-separated integers N$N$ and M$M$ — the length of permutation and the number of conditions to be satisfied respectively.
• The next M$M$ lines describe the conditions. The i$i$-th of these M$M$ lines contains two space-separated integers Xi$X_i$ and Yi$Y_i$.

Output Format

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

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

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤N≤105$1\le N\le {10}^5$
• 1≤M≤N$1\le M\le N$
• 1≤Xi,Yi≤N$1\le X_i,Y_i\le N$
• Xi≠Xj$X_i\ne X_j$ for each 1≤i<j≤M$1\le i<j\le M$.
• The sum of N$N$ over all test cases won't exceed 2⋅105$2\cdot {10}^5$.