Read problems statements in mandarin chinese, russian and vietnamese as well. 

Consider a sequence of positive integers A = (A_{1}, A_{2}, ... , A_{N}), and another sequence B = (B_{1}, B_{2}, ... , B_{M}). We say that B is a subsequence of A, if B can be written as (Ai_{1}, Ai_{2}, ... , Ai_{M}), where 1 ≤ i_{1} < i_{2} ... < i_{M} ≤ N. If B is a subsequence of A, there could be multiple ways to write it in such a manner, and among all those ways, we choose the way which minimizes i_{M}. We call this minimized i_{M} to be f(B). Note that in the definition of f(B), we are assuming that A is a constant. Also, when B is the empty sequence, it is considered to be a subsequence of A, and f(B) would then be 0.

Now, given A, we will construct a graph G which has N + 1 nodes and labeled directed edges. The nodes are {V_{0}, V_{1}, ..., V_{N}}. If there are two subsequences of A: C_{1} and C_{2}, such that C_{2} is obtained by appending the integer b at the end of C_{1}, and f(C_{1}) ≠ f(C_{2}), then the edge ( Vf(C_{1}), b, Vf(C_{2}) ) is added to the graph G if it is not already present in the graph. (Note that even if an edge with a different label is already present, this edge is added. Just that there will not be multiple edges from one vertex to another with the same label). The edge (V_{i}, b, V_{j}) means that it is a directed edge from V_{i} to V_{j}, and it has the label b.

Chef constructed this graph, but then lost the sequence A, as well as all the labels on the graph. So all he has left is a directed graph (with possibly multiple edges from one vertex to another), and now he wants to find the sequence A. Since there could be many such sequences which fit the graph, he wants to find the lexicographically smallest such sequence. Help Chef in finding this.

------ Input ------ 

The first line contains a single integer, T, which is the number of testcases. The description of each testcase follows.
The first line of each testcase contains two integers, N and M. This means that the input graph has vertices {V_{0}, V_{1}, ..., V_{N}} and M directed multi-edges.
The i-th of the next M lines contains two integers, x_{i} and y_{i}, which denote that there is a directed edge from Vx_{i} to Vy_{i}.

------ Output ------ 

For each testcase, output a single line which contains N positive integers which denote the lexicographically smallest sequence which can lead to the construction of the inputted graph. Or, if such a sequence does not exist, output -1.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N, M ≤ 10^{5}$
$0 ≤ x_{i}, y_{i} ≤ N$

------ Subtasks ------ 

$Subtask 1 (30 points) : N, M ≤  10^{3}$ 
$Subtask 2 (70 points) : Original constraints$

----- Sample Input 1 ------ 
2

5 11

0 1

0 2

0 5

2 3

2 5

1 3

1 5

1 2

3 4

3 5

4 5

3 4

0 3

2 3

1 2

0 1
----- Sample Output 1 ------ 
1 2 1 1 3

-1
----- explanation 1 ------ 
Testcase 1:
Let us consider the sequence A = (1, 2, 1, 1, 3).
f(empty string) = 0, and f( (1) ) = 1. (1) can be obtained by appending 1 to the empty string. Hence there should be an edge from V0 to V1 with the label 1.
Similarly, f( (1, 2, 1) ) = 3 and f( (1, 2, 1, 3) ) = 5. Hence there should be an edge from V3 to V5 with label 3.
By looking at all such possible pairs of valid subsequences, we can see that the edges obtained from this A exactly match the edges given in the input graph. And this is the lexicographically smallest such sequence. Hence the answer is this sequence.

Testcase 2:
There is no sequence which leads to the construction of this graph. Hence the answer is -1.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Graph algorithms

Directed graphs

Greedy algorithms


Solutions:
def fun():
	t = int(input())
	for a0 in range(t):
		(n, q) = map(int, input().strip().split())
		arr = []
		ans = []
		flag = 0
		for i in range(n + 1):
			arr.append([])
			ans.append(-1)
		for i in range(q):
			(a, b) = map(int, input().strip().split())
			arr[a].append(b)
			if a >= b:
				flag = 1
		if flag == 1:
			print(-1)
			continue
		s = len(arr[0])
		po = [i for i in range(1, s + 1)]
		pok = tuple(po)
		pos = [list(pok) for i in range(n)]
		ans[0] = 0
		for i in range(n):
			arr[i].sort()
			j = 0
			if ans[i] == -1:
				flag = 1
				break
			while j < len(arr[i]):
				if ans[arr[i][j]] == -1:
					if len(pos[i]) == 0:
						flag = 1
						break
					else:
						ans[arr[i][j]] = pos[i][0]
						arr_remove = arr[i][j]
						pos_remove = pos[i][0]
						remove_till = arr[i][j]
						pos[i].pop(0)
						m = i + 1
						while m < remove_till:
							if arr_remove not in arr[m] or pos_remove not in pos[m]:
								flag = 1
								break
							arr[m].remove(arr_remove)
							pos[m].remove(pos_remove)
							m = m + 1
				j = j + 1
			if len(pos[i]) != 0:
				ks = 0
				ke = len(pos[i])
				while ks != ke:
					ls = i + 1
					mc = pos[i][ks]
					while ls != n:
						pos[ls].remove(mc)
						ls = ls + 1
					ks = ks + 1
		if ans[n] == -1:
			flag = 1
		if flag == 1:
			print(-1)
		else:
			for i in range(1, n + 1):
				print(ans[i], end=' ')
			print()
fun()


from collections import defaultdict
T = int(input())
for t in range(T):
	G = defaultdict(set)
	(N, M) = map(int, input().split())
	edges = []
	for m in range(M):
		(u, v) = map(int, input().split())
		G[v].add(u)
		edges.append((u, v))
	edges.sort()
	answer = [0] * (N + 1)
	counter = 0
	for (u, v) in edges:
		if u == 0:
			counter += 1
			answer[v] = counter
		elif answer[v] == 0:
			answer[v] = answer[u]
	last_instance = {}
	valid = True
	for i in range(1, N + 1):
		val = answer[i]
		last = last_instance.get(val, 0)
		last_instance[val] = i
		if len(G[i]) != i - last:
			valid = False
			break
	print(' '.join(map(str, answer[1:])) if valid else -1)


from collections import defaultdict

def stringra(P, n):
	if 0 in P or any((i not in P for i in range(1, n + 1))):
		return [-1]
	for i in range(1, len(P) + 1):
		P[i].sort()
	Q = defaultdict(list)
	Q[1].append(0)
	X = [0] * (n + 1)
	k = 0
	for i in range(1, len(P) + 1):
		if P[i][0] == 0:
			k += 1
			X[i] = k
		else:
			X[i] = X[P[i][0]]
	for i in range(2, len(P) + 1):
		for j in range(i - 1, -1, -1):
			if X[i] != X[j]:
				Q[i].append(j)
			else:
				Q[i].append(j)
				break
		Q[i].reverse()
	if any((Q[i] != P[i] for i in range(1, n + 1))):
		return [-1]
	return X[1:n + 1]
for t in range(int(input())):
	(n, m) = map(int, input().split())
	adjList = defaultdict(list)
	for _ in range(m):
		(x, y) = map(int, input().split())
		adjList[y].append(x)
	print(*stringra(adjList, n))


def getElist(ee):
	ret = []
	ee = sorted(ee)
	for (a, b) in ee:
		while a >= len(ret):
			ret += [[]]
		ret[a] += [b]
	return ret

def checkElist(ee):
	se = [set(x) for x in ee]
	for (i, e) in enumerate(ee):
		if e[0] != i:
			return False
		if i + 1 < len(ee):
			s = se[i + 1]
			for q in e[1:]:
				if q not in s:
					return False
	return True

def solve(n, ee):
	ee = getElist(ee)
	ret = [-1] * n
	if not checkElist(ee):
		return -1
	for (i, e) in enumerate(ee[0]):
		ret[e] = i + 1
	ss = set(ee[0])
	for (i, e) in enumerate(ee):
		if i == 0:
			continue
		nn = []
		for k in e:
			if k not in ss:
				ss.add(k)
				nn += [k]
		if len(nn) > 1:
			return -1
		elif len(nn) == 1:
			ret[nn[0]] = ret[i - 1]
	if any((x == -1 for x in ret)):
		return -1
	return ' '.join(map(str, ret))
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(n, m) = map(int, f.readline().split())
	e = []
	for j in range(m):
		(a, b) = map(int, f.readline().split())
		e += [(a, b - 1)]
	print(solve(n, e))


def gen(N, E):
	G = [N + 1 for _ in range(N + 1)]
	S = [set() for _ in range(N + 1)]
	for (x, y) in E:
		if x >= y or x in S[y]:
			return -1
		G[y] = min(G[y], x)
		S[y].add(x)
	C = []
	cpt = 1
	for i in range(1, N + 1):
		if len(S[i]) == 0 or i - G[i] != len(S[i]):
			return -1
		if G[i] == 0:
			C.append(cpt)
			cpt += 1
		else:
			C.append(C[G[i] - 1])
	E = set(E)
	D = {}
	m = 0
	for i in range(N - 1, -1, -1):
		D[C[i]] = i + 1
		for x in D:
			if not (i, D[x]) in E:
				return -1
			m += 1
			if m > len(E):
				return -1
	if m != len(E):
		return -1
	return ' '.join(map(str, C))

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = map(int, input().split())
		E = [tuple(map(int, input().split())) for _ in range(M)]
		print(gen(N, E))
main()


def rebuild(PG, PGS):
	for pv in PG:
		for (l, r) in zip(pv, pv[1:]):
			if l == r:
				return None
	kinds = 0
	locations = {}
	res = []
	for (idx, pv) in enumerate(PG[1:], start=1):
		if len(pv) == idx:
			kinds += 1
			res.append(kinds)
			locations[kinds] = [idx]
		else:
			matched = None
			for kind in range(1, kinds + 1):
				got = True
				if len(pv) != idx - locations[kind][-1]:
					got = False
					continue
				for (tidx, t) in enumerate(pv):
					if tidx + locations[kind][-1] != t:
						got = False
						break
				if got:
					matched = kind
					break
			if matched is None:
				return None
			res.append(matched)
			locations[matched].append(idx)
	return res
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	PG = [[] for _ in range(N + 1)]
	PGS = [set() for _ in range(N + 1)]
	for _ in range(M):
		(f, t) = map(int, input().split())
		if f > t:
			(f, t) = (t, f)
		PG[t].append(f)
		PGS[t].add(f)
	for pv in PG:
		pv.sort()
	ans = rebuild(PG, PGS)
	if ans is None:
		print(-1)
	else:
		print(' '.join((str(item) for item in ans)))


import sys

def find():
	(N, M) = list(map(int, input().strip().split(' ')))
	edge = set()
	edges = [[] for i in range(N + 1)]
	index = 1
	check = 1
	for i in range(M):
		(a, b) = list(map(int, input().strip().split(' ')))
		if a >= b:
			check = 0
		elif (a, b) in edge:
			check = 0
		else:
			edge.add((a, b))
			edges[b] += [a]
	if check == 0:
		print(-1)
		return 0
	ans = [1] * N
	count1 = 0
	for i in range(1, N + 1):
		edges[i] = sorted(edges[i])
		if edges[i] == []:
			print(-1)
			return 0
		begin = edges[i][0]
		if i - begin != len(edges[i]):
			print(-1)
			return 0
		if begin == 0:
			ans[i - 1] = index
			index += 1
		else:
			ans[i - 1] = ans[begin - 1]
	X = max(ans)
	counting = {}
	for i in range(1, X + 1):
		counting[i] = []
	for i in range(len(ans)):
		if ans[i] not in counting:
			print(-1)
			return 0
		counting[ans[i]] += [i + 1]
	for x in counting:
		array = counting[x]
		for i in range(len(array)):
			if i == 0:
				k = array[i]
				if edges[k][0] != 0:
					print(-1)
					return 0
			else:
				k1 = array[i]
				k2 = array[i - 1]
				if edges[k1][0] != k2:
					print(-1)
					return 0
	print(*ans)
	return 0
for _ in range(int(input())):
	find()


from collections import deque
for t in range(int(input())):
	(n, m) = map(int, input().split())
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		g[u].append(v)
	val = [None] * (n + 1)
	nums = set()
	g[0].sort()
	for i in range(len(g[0])):
		val[g[0][i]] = i + 1
		nums.add(i + 1)
	invalid = False
	for u in range(1, n + 1):
		if val[u] is None:
			invalid = True
			break
		ss = set()
		nxt = None
		for v in g[u]:
			ss.add(val[v])
			if val[v] is None:
				nxt = v
		if len(g[u]) != len(ss) or (len(ss) != len(nums) and len(ss) != len(nums) - 1):
			invalid = True
			break
		if None in ss:
			ss.remove(None)
			ss.add(val[u])
			if ss != nums:
				invalid = True
				break
			val[nxt] = val[u]
		else:
			nums.remove(val[u])
			if ss != nums:
				invalid = True
				break
	if invalid:
		print(-1)
	else:
		print(*val[1:])