You are given a directed acyclic graph with n vertices and m edges. There are no self-loops or multiple edges between any pair of vertices. Graph can be disconnected.

You should assign labels to all vertices in such a way that:

  Labels form a valid permutation of length n — an integer sequence such that each integer from 1 to n appears exactly once in it.  If there exists an edge from vertex v to vertex u then label_{v} should be smaller than label_{u}.  Permutation should be lexicographically smallest among all suitable. 

Find such sequence of labels to satisfy all the conditions.


-----Input-----

The first line contains two integer numbers n, m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5).

Next m lines contain two integer numbers v and u (1 ≤ v, u ≤ n, v ≠ u) — edges of the graph. Edges are directed, graph doesn't contain loops or multiple edges.


-----Output-----

Print n numbers — lexicographically smallest correct permutation of labels of vertices.


-----Examples-----
Input
3 3
1 2
1 3
3 2

Output
1 3 2 

Input
4 5
3 1
4 1
2 3
3 4
2 4

Output
4 1 2 3 

Input
5 4
3 1
2 1
2 3
4 5

Output
3 1 2 4 5

Difficulty: HARD
Tags: Graph algorithms

Data structures

Graph traversal

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
from queue import Queue
import heapq
(n, m) = input().split()
n = int(n)
m = int(m)
f = [0] * (n + 1)
sol = [0] * (n + 1)
adya = [[] for _ in range(n + 1)]
for i in range(m):
	(n1, n2) = input().split()
	n1 = int(n1)
	n2 = int(n2)
	adya[n2].append(n1)
	f[n1] += 1
cola = []
cnt = 0
for i in range(1, n + 1):
	if f[i] == 0:
		heapq.heappush(cola, -1 * i)
		cnt += 1
num = int(n)
while cnt > 0:
	v = heapq.heappop(cola)
	v *= -1
	sol[v] = num
	cnt -= 1
	num -= 1
	for to in adya[v]:
		f[to] -= 1
		if f[to] == 0:
			heapq.heappush(cola, -1 * to)
			cnt += 1
stringOut = ''
for i in range(1, n + 1):
	stringOut += str(sol[i])
	if i != n:
		stringOut += ' '
print(stringOut)


import sys, heapq
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
(n, m) = map(int, input().split())
g = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1)
for _ in range(m):
	(u, v) = map(int, input().split())
	g[v].append(u)
	indeg[u] += 1
q = [-u for u in range(1, n + 1) if not indeg[u]]
heapq.heapify(q)
ans = [0] * (n + 1)
cur = n
while q:
	u = -heapq.heappop(q)
	ans[u] = cur
	cur -= 1
	for v in g[u]:
		indeg[v] -= 1
		if not indeg[v]:
			heapq.heappush(q, -v)
print(*ans[1:])


from collections import defaultdict
import heapq
(num_nodes, num_edges) = map(int, input().split())
ins = defaultdict(set)
out = defaultdict(int)
for _ in range(num_edges):
	(node_out, node_in) = map(int, input().split())
	ins[node_in].add(node_out)
	out[node_out] += 1
zeros = [-node for node in range(num_nodes, 0, -1) if out[node] == 0]
final_mappings = {}
current_index = num_nodes
while current_index > 0:
	node = -heapq.heappop(zeros)
	final_mappings[node] = current_index
	current_index -= 1
	for node_out in ins[node]:
		out[node_out] -= 1
		if out[node_out] == 0:
			heapq.heappush(zeros, -node_out)
print(' '.join((str(final_mappings[node]) for node in range(1, num_nodes + 1))))


from heapq import heappush, heappop
q = lambda : map(int, input().split())
(n, m) = q()
a = d = [0] * n
e = [[] for _ in range(n)]
h = []
while m:
	(l, r) = q()
	d[l - 1] += 1
	e[r - 1] += [l - 1]
	m -= 1
for i in range(n):
	if d[i] == 0:
		heappush(h, -i)
j = n
while h:
	t = -heappop(h)
	a[t] = j
	j -= 1
	for x in e[t]:
		d[x] -= 1
		if d[x] == 0:
			heappush(h, -x)
print(''.join((str(x) + ' ' for x in a)))


from heapq import *
(n, m) = map(int, input().split())
g = [[] for _ in range(n + 1)]
out = [0] * (n + 1)
for _ in range(m):
	(u, v) = map(int, input().split())
	g[v].append(u)
	out[u] += 1
q = [-u for u in range(1, n + 1) if not out[u]]
heapify(q)
r = [0] * (n + 1)
c = n
while q:
	u = -heappop(q)
	r[u] = c
	c -= 1
	for v in g[u]:
		out[v] -= 1
		if not out[v]:
			heappush(q, -v)
print(*r[1:])


import collections
import heapq

def constructGraph(n, edges):
	graph = collections.defaultdict(list)
	inDegree = [0 for _ in range(n)]
	for edge in edges:
		(a, b) = (edge[0] - 1, edge[1] - 1)
		graph[b].append(a)
		inDegree[a] += 1
	return [graph, inDegree]

def solve(n, edges):
	(graph, inDegree) = constructGraph(n, edges)
	answer = [0 for _ in range(n)]
	pq = []
	for i in range(n):
		if inDegree[i] == 0:
			heapq.heappush(pq, -i)
	current = n
	while pq:
		currentNode = -heapq.heappop(pq)
		answer[currentNode] = current
		current -= 1
		if currentNode not in graph:
			continue
		for neighNode in graph[currentNode]:
			inDegree[neighNode] -= 1
			if inDegree[neighNode] == 0:
				heapq.heappush(pq, -neighNode)
	return answer
(n, m) = map(int, input().split())
edges = []
for _ in range(m):
	edges.append(list(map(int, input().split())))
print(*solve(n, edges), sep=' ')


(n, m) = map(int, input().split())
d = [0] * n
e = [[] for i in range(n)]
for i in range(m):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	d[u] += 1
	e[v].append(u)
from heapq import heappush, heappop
pq = []
for i in range(n):
	if d[i] == 0:
		heappush(pq, -i)
ind = n
ans = [0] * n
while pq:
	u = -heappop(pq)
	ans[u] = ind
	ind -= 1
	for v in e[u]:
		d[v] -= 1
		if d[v] == 0:
			heappush(pq, -v)
print(' '.join((str(x) for x in ans)))


import sys
from heapq import heappop, heappush
(n, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
rev = [[] for _ in range(n)]
outdeg = [0] * n
for (u, v) in (map(int, line.decode('utf-8').split()) for line in sys.stdin.buffer):
	rev[v - 1].append(u - 1)
	outdeg[u - 1] += 1
ans = [0] * n
num = n
hq = [-i for i in range(n - 1, -1, -1) if outdeg[i] == 0]
while hq:
	v = -heappop(hq)
	ans[v] = num
	num -= 1
	for dest in rev[v]:
		outdeg[dest] -= 1
		if outdeg[dest] == 0:
			heappush(hq, -dest)
assert num == 0
sys.stdout.buffer.write(' '.join(map(str, ans)).encode('utf-8'))