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

Starter code:

Solutions:
#!/usr/local/bin/python3

from collections import defaultdict
import heapq

num_nodes, num_edges = list(map(int, input().split()))

ins = defaultdict(set)
out = defaultdict(int)

for _ in range(num_edges):
    node_out, node_in = list(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))

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

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:])

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)

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)