## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Strict Permutation CodeChef Solution

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

• $\left({X}_{i},{Y}_{i}\right)$, denoting that the element ${X}_{i}\phantom{\rule{thickmathspace}{0ex}}\left(1\le {X}_{i}\le N\right)$ must appear in the prefix of length ${Y}_{i}$. Formally, if the index of the element ${X}_{i}$ is ${K}_{i}$ (i.e, ${P}_{{K}_{i}}={X}_{i}$), then the condition $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$ and $B$ have the same length $N$, then $A$ is called lexicographically smaller

Solution Click Below:-  👉
👇👇👇👇👇

than $B$ only if there exists an index $i\phantom{\rule{thickmathspace}{0ex}}\left(1\le i\le N\right)$ such that ${A}_{1}={B}_{1},$ ${A}_{2}={B}_{2},$ $\dots ,$ ${A}_{i-1}={B}_{i-1},{A}_{i}<{B}_{i}$.

### Input Format

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

• The first line of each test case contains two space-separated integers $N$ and $M$ — the length of permutation and the number of conditions to be satisfied respectively.
• The next $M$ lines describe the conditions. The $i$-th of these $M$ lines contains two space-separated integers ${X}_{i}$ and ${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$ space-separated integers, denoting the elements of the permutation. If there are multiple answers, output the lexicographically smallest one.

### Constraints

• $1\le T\le {10}^{5}$
• $1\le N\le {10}^{5}$
• $1\le M\le N$
• $1\le {X}_{i},{Y}_{i}\le N$
• ${X}_{i}\ne {X}_{j}$ for each $1\le i.
• The sum of $N$ over all test cases won't exceed $2\cdot {10}^{5}$.