You are given an integer N. You have to find a [permutation] P of the integers \{1, 2, \ldots, N\} that satisfies M conditions of the following form:
(X_{i}, Y_{i}), denoting that the element X_{i}\;(1≤ X_{i} ≤ N) 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≤ K_{i} ≤ 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 than B only if there exists an index i \; (1≤ i ≤ N) such that A_{1}=B_{1}, A_{2}=B_{2}, \ldots, 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 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ N$
$1 ≤ X_{i}, Y_{i} ≤ N$
$X_{i} \neq X_{j}$ for each $1 ≤ i < j ≤ M$.
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

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

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

Test case $2$: There is no permutation of length $4$ that satisfies all the given conditions.

Test case $3$: There are many permutations of length $4$ 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]$, etc. $[1,2,3,4]$ is the lexicographically smallest among them.

Difficulty: HARD
Tags: Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from heapq import heappush, heappop

def solve():
	(n, m) = rl()
	z = []
	for i in range(n + 1):
		z.append([])
	visited = [0] * (n + 1)
	for _ in range(m):
		(x, y) = rl()
		z[y].append(x)
		visited[x] = 1
	prev = 0
	for i in range(1, n + 1):
		if prev + len(z[i]) > i:
			return [-1]
		prev += len(z[i])
	for i in range(1, n + 1):
		if not visited[i]:
			z[-1].append(i)
	ans = [0] * (n + 1)
	heap = []
	for i in range(n, 0, -1):
		while z[i]:
			heappush(heap, -z[i].pop())
		ans[i] = -heappop(heap)
	return ans[1:]

def main():
	for _ in range(ri()):
		print(*solve())
main()


import heapq
for _ in range(int(input())):
	(n, n_quer) = list(map(int, input().split()))
	quer = [n] * (n + 1)
	for _ in range(n_quer):
		(x, y) = list(map(int, input().split()))
		quer[x] = y
	ind = [[] for _ in range(n + 1)]
	for i in range(1, n + 1):
		ind[quer[i]].append(i)
	pq = []
	res = [1] * (n + 1)
	flag = False
	for i in range(n, 0, -1):
		for val in ind[i]:
			heapq.heappush(pq, -val)
		if not pq:
			print(-1)
			flag = True
			break
		res[i] = -heapq.heappop(pq)
	if not flag:
		print(*res[1:])


import heapq
t = int(input())
while t > 0:
	(n, m) = [int(x) for x in input().split()]
	last = [n for i in range(n + 1)]
	for i in range(m):
		(x, y) = [int(x) for x in input().split()]
		last[x] = y
	v = [[] for i in range(n + 1)]
	for i in range(1, n + 1):
		v[last[i]].append(i)
	ans = [None for i in range(n + 1)]
	q = list()
	for i in range(n, 0, -1):
		for ele in v[i]:
			heapq.heappush(q, -ele)
		if len(q) == 0:
			ans[0] = -1
			break
		ans[i] = -heapq.heappop(q)
	if ans[0] is not None:
		print(-1)
	else:
		print(*ans[1:])
	t -= 1


import heapq
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	max_idx = [[] for _1 in range(n)]
	used = [False] * n
	fail = False
	for _1 in range(m):
		(x, y) = list(map(int, input().split()))
		max_idx[y - 1].append(x)
		used[x - 1] = True
	for i in range(n):
		if used[i] == False:
			max_idx[-1].append(i + 1)
	pq = []
	ans = []
	for i in range(n - 1, -1, -1):
		for x in max_idx[i]:
			heapq.heappush(pq, -x)
		if len(pq) == 0:
			fail = True
			break
		ans.append(-heapq.heappop(pq))
	if fail:
		print(-1)
		continue
	ans = reversed(ans)
	print(*ans)


strng = lambda : input().split()[0]
inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
slst = lambda : list(input().split())
silst = lambda : list(map(int, input().split()))
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
import sys
input = sys.stdin.readline
from heapq import heapify, nsmallest, nlargest, heappush, heappop
from collections import defaultdict, deque
from math import ceil, log, floor, sqrt, gcd, log10
for _ in range(inp()):
	(n, m) = mul()
	d = defaultdict(lambda : [])
	vis = [False] * (n + 1)
	for i in range(m):
		(val, pos) = mul()
		d[pos] += [val]
		vis[val] = True
	for i in range(1, n + 1):
		if vis[i] == False:
			d[n] += [i]
	a = []
	ans = [0] * (n + 1)
	for i in range(n, 0, -1):
		for val in d[i]:
			heappush(a, -val)
		if a:
			ans[i] = -heappop(a)
		else:
			break
	else:
		print(*ans[1:])
		continue
	print(-1)


from sys import stdin
input = stdin.readline

class Node:

	def __init__(self, val=-1):
		self.val = val

class maxheap:

	def __init__(self):
		self.a = []

	def getsize(self):
		return len(self.a)

	def insert(self, node):
		self.a.append(node)
		ci = len(self.a) - 1
		pi = (ci - 1) // 2
		while pi >= 0:
			if self.a[pi].val < self.a[ci].val:
				(self.a[pi], self.a[ci]) = (self.a[ci], self.a[pi])
			else:
				break
			ci = pi
			pi = (ci - 1) // 2

	def remove(self):
		if len(self.a) == 0:
			return 'Empty'
		(self.a[0], self.a[-1]) = (self.a[-1], self.a[0])
		ele = self.a.pop()
		te = len(self.a)
		pi = 0
		while 1:
			if 2 * pi + 2 < te:
				if self.a[2 * pi + 1].val >= self.a[2 * pi + 2].val:
					if self.a[pi].val >= self.a[2 * pi + 1].val:
						break
					else:
						(self.a[pi], self.a[2 * pi + 1]) = (self.a[2 * pi + 1], self.a[pi])
						pi = 2 * pi + 1
				elif self.a[pi].val >= self.a[2 * pi + 2].val:
					break
				else:
					(self.a[pi], self.a[2 * pi + 2]) = (self.a[2 * pi + 2], self.a[pi])
					pi = 2 * pi + 2
			elif 2 * pi + 1 < te:
				if self.a[pi].val >= self.a[2 * pi + 1].val:
					break
				else:
					(self.a[pi], self.a[2 * pi + 1]) = (self.a[2 * pi + 1], self.a[pi])
					pi = 2 * pi + 1
			else:
				break
		return ele
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	d = {}
	e = {}
	b = []
	for i in range(m):
		(x, y) = map(int, input().split())
		a.append([x, y])
		e[x] = True
		if y not in d:
			d[y] = [x]
		else:
			d[y].append(x)
		b.append(y)
	b.sort()
	check = 1
	for i in range(m):
		if b[i] < i + 1:
			check = 0
			break
	if check:
		left = []
		for i in range(n):
			if e.get(i + 1) is None:
				left.append(i + 1)
		mxh = maxheap()
		for num in left:
			mxh.insert(Node(num))
		ans = []
		for i in range(n, 0, -1):
			if d.get(i) is not None:
				for num in d[i]:
					mxh.insert(Node(num))
			ans.append(mxh.remove().val)
		ans.reverse()
		print(*ans)
	else:
		print(-1)


import heapq
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	nums = [1 for i in range(n + 1)]
	a = [[] for i in range(n + 1)]
	for i in range(m):
		(x, y) = map(int, input().split())
		nums[x] = 0
		a[y].append(x)
	for i in range(1, n + 1):
		if nums[i]:
			a[n].append(i)
	q = []
	ans = []
	f = 1
	for i in range(n, 0, -1):
		for j in a[i]:
			heapq.heappush(q, -1 * j)
		if len(q) == 0:
			print(-1)
			f = 0
			break
		ans.append(-1 * heapq.heappop(q))
	if f:
		print(*ans[::-1])


import heapq
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	heap = []
	heapq.heapify(heap)
	check = {}
	arr = [0] * (n + 1)
	for _ in range(m):
		(x, y) = map(int, input().split())
		if y not in check:
			check[y] = [x]
		else:
			check[y] += [x]
		arr[x] = 1
	for i in range(1, len(arr)):
		if not arr[i]:
			heapq.heappush(heap, -i)
	flag = 0
	res = [0] * n
	for i in range(n, 0, -1):
		if i in check:
			for j in check[i]:
				heapq.heappush(heap, -j)
		if not heap:
			flag = 1
			break
		res[i - 1] = -heapq.heappop(heap)
	if flag:
		print(-1)
	else:
		print(*res)


from heapq import heappush, heappop, heapify
from sys import stdin
input = stdin.readline

def solve(N, M, conditions):
	V = [[] for i in range(N + 1)]
	used = set(range(1, N + 1))
	for (X, Y) in conditions:
		V[Y].append(X)
		used.remove(X)
	V[N] += list(used)
	possible = []
	permutation = [None] * (N + 1)
	for i in reversed(range(1, N + 1)):
		for p in V[i]:
			heappush(possible, -p)
		if not possible:
			return [-1]
		permutation[i] = -heappop(possible)
	return permutation[1:]
T = int(input().strip())
for problem in range(1, T + 1):
	(N, M) = [int(x) for x in input().strip().split()]
	conditions = []
	for i in range(M):
		(Xi, Yi) = [int(x) for x in input().strip().split()]
		conditions.append((Xi, Yi))
	print(*solve(N, M, conditions))


from heapq import heappush, heappop
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	bag = dict()
	numset = set()
	for i in range(m):
		(num, p) = map(int, input().split())
		if p in bag:
			bag[p].append(num)
		else:
			bag[p] = [num]
		numset.add(num)
	bottle = []
	for i in range(1, n + 1):
		if not i in numset:
			heappush(bottle, -i)
	ans = [0] * n
	status = True
	while n > 0:
		if n in bag:
			for num in bag[n]:
				heappush(bottle, -num)
		if len(bottle) == 0:
			status = False
			break
		ans[n - 1] = str(-heappop(bottle))
		n -= 1
	if status:
		print(' '.join(ans))
	else:
		print(-1)


import heapq as heap
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = [set() for i in range(n + 1)]
	(ps, ts) = (set(range(1, n + 1)), set())
	for i in range(m):
		(k1, k2) = map(int, input().split())
		arr[k2].add(k1)
		ts.add(k1)
	rms = ps.difference(ts)
	arr[-1] = arr[-1].union(rms)
	hp = []
	flag = True
	ans = [0 for i in range(n)]
	for i in range(n, 0, -1):
		while arr[i]:
			heap.heappush(hp, -arr[i].pop())
		if hp:
			ans[i - 1] = -heap.heappop(hp)
		else:
			print(-1)
			flag = False
			break
	if flag:
		for x in ans:
			print(x, end=' ')
		print('\r')


import heapq

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def yn(ans):
	if ans:
		print('YES')
	else:
		print('NO')
for T in range(int(input())):
	(n, m) = mi()
	a = []
	for i in range(n):
		a.append([])
	curr = set(range(1, n + 1))
	for i in range(m):
		(x, y) = mi()
		if x in curr:
			curr.remove(x)
		a[y - 1].append(x)
	ans = [-1] * n
	curr = list(curr)
	for i in range(len(curr)):
		curr[i] = -curr[i]
	heapq.heapify(curr)
	flag = True
	for i in range(n, 0, -1):
		for j in a[i - 1]:
			heapq.heappush(curr, -j)
		if len(curr) == 0:
			flag = False
			break
		else:
			ans[i - 1] = -int(heapq.heappop(curr))
	if not flag:
		print(-1)
	else:
		print(*ans)


import heapq
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	nums = [[] for _ in range(n)]
	vis = [0] * n
	for i in range(m):
		(x, y) = map(int, input().split())
		nums[y - 1].append(x - 1)
		vis[x - 1] = 1
	for i in range(n):
		if not vis[i]:
			nums[-1].append(i)
	heap = []
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		for j in nums[i]:
			heapq.heappush(heap, -(j + 1))
		if not heap:
			ans = [-1]
			break
		ans[i] = -heapq.heappop(heap)
	print(*ans)


import heapq
from collections import defaultdict
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dic = defaultdict(lambda : [])
	heap = []
	flag = [0] * n
	for i in range(m):
		(x, y) = map(int, input().split())
		dic[y - 1].append(x)
		flag[x - 1] = 1
	for i in range(n):
		if flag[i] == 0:
			heap.append(-(i + 1))
	heapq.heapify(heap)
	flag = 0
	ans = [0] * n
	for i in range(n - 1, -1, -1):
		for value in dic[i]:
			heapq.heappush(heap, -1 * value)
		if heap:
			ans[i] = heapq.heappop(heap)
		else:
			flag = 1
			break
	if flag:
		print(-1)
	else:
		for i in ans:
			print(-1 * i, end=' ')
		print()


from collections import defaultdict
import heapq

def solve():
	(n, m) = map(int, input().split())
	hs = defaultdict(int)
	for _ in range(m):
		(a, b) = map(int, input().split())
		hs[a] = max(hs[a], b)
	qu = sorted(list(hs.items()), key=lambda x: (x[1], x[0]))
	ans = [-1 for _ in range(n + 1)]
	hp = []
	heapq.heapify(hp)
	(rt, rtx) = (n, n)
	while rt > 0:
		if rt < len(qu):
			print(-1)
			return
		while rtx in hs:
			rtx -= 1
		while qu and qu[-1][1] == rt:
			heapq.heappush(hp, -qu.pop()[0])
		if not hp:
			ans[rt] = rtx
			rtx -= 1
		elif rt == len(qu) + 1:
			ans[rt] = -heapq.heappop(hp)
		elif -hp[0] > rtx:
			ans[rt] = -heapq.heappop(hp)
		else:
			ans[rt] = rtx
			rtx -= 1
		rt -= 1
	print(' '.join(map(str, ans[1:])))
t = int(input())
for _ in range(t):
	solve()


def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	if b == 0:
		return a
	return gcd(b, a % b)
import sys
from heapq import heappush, heappop

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
	(n, m) = get_ints()
	arr = [[] for i in range(n)]
	seen = set()
	for i in range(m):
		(a, b) = get_ints()
		seen.add(a)
		arr[b - 1].append(a)
	for i in range(n):
		if i + 1 not in seen:
			arr[n - 1].append(i + 1)

	def solve():
		pq = []
		res = [None for i in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(len(arr[i])):
				heappush(pq, -arr[i][j])
			if not pq:
				return [-1]
			num = -heappop(pq)
			res[i] = num
		return res
	print(*solve())


import heapq, collections
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	h = []
	a = {}
	ok = True
	d = collections.defaultdict(list)
	for i in range(m):
		(x, y) = map(int, input().split())
		d[y].append(x)
		a[x] = 1
	for i in range(1, n + 1):
		if i not in a:
			d[n].append(i)
	ans = [0] * n
	for i in range(n, 0, -1):
		for j in d[i]:
			heapq.heappush(h, -j)
		if h:
			ans[i - 1] = -heapq.heappop(h)
		else:
			ok = False
	if ok:
		print(*ans)
	else:
		print(-1)


import heapq
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	last = [n for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		last[u] = v
	arr = [[] for i in range(n + 1)]
	for i in range(1, n + 1):
		arr[last[i]].append(i)
	hp = []
	ans = [0 for i in range(n + 1)]
	heapq.heapify(hp)
	fl = 0
	for i in range(n, 0, -1):
		for j in arr[i]:
			heapq.heappush(hp, -j)
		if hp:
			ans[i] = -heapq.heappop(hp)
		else:
			fl = 1
			break
	if fl == 1:
		print(-1)
	else:
		print(*ans[1:])


import heapq
t = int(input())
while t:
	(p, q) = map(int, input().split())
	z = []
	po = {}
	for i in range(q):
		(c, d) = map(int, input().split())
		z.append((c, d))
		po[c] = True
	z.sort(key=lambda x: x[1])
	l = [-i for i in range(p, 0, -1) if i not in po]
	heapq.heapify(l)
	check = []
	for k in range(p, 0, -1):
		while len(z) > 0 and z[-1][1] == k:
			u = z.pop()
			heapq.heappush(l, -u[0])
		if len(l) == 0:
			print(-1)
			break
		check.append(-heapq.heappop(l))
	else:
		print(*check[::-1])
	t -= 1


import random
import math
from collections import defaultdict, Counter
from functools import lru_cache
import bisect
import heapq

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def google(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	(n, m) = map(int, input().split())
	cond = []
	condn = {}
	for i in range(m):
		(a, b) = map(int, input().split())
		cond.append((a, b))
		condn[a] = True
	cond.sort(key=lambda x: x[1])
	canadd = [-i for i in range(n, 0, -1) if i not in condn]
	heapq.heapify(canadd)
	ans = []
	for i in range(n, 0, -1):
		while len(cond) > 0 and cond[-1][1] == i:
			p = cond.pop()
			heapq.heappush(canadd, -p[0])
		if len(canadd) == 0:
			print(-1)
			break
		ans.append(-heapq.heappop(canadd))
	else:
		print(*ans[::-1])
for t in range(int(input())):
	solve()


from heapq import heappush, heappop
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dit = {x: [] for x in range(1, n + 1)}
	s = set([x for x in range(1, n + 1)])
	for i in range(m):
		(a, b) = map(int, input().split())
		dit[b].append(a)
		s.remove(a)
	c = 0
	f = True
	for i in range(1, n + 1):
		c += len(dit[i])
		if c > i:
			f = False
			break
	if not f:
		print(-1)
		continue
	hp = []
	for e in s:
		heappush(hp, -e)
	ans = [0] * n
	for i in range(n, 0, -1):
		for e in dit[i]:
			heappush(hp, -e)
		top = -heappop(hp)
		ans[i - 1] = top
	print(*ans)