Sortowanie topologiczne

Limit czasu: 0.5s | Limit pamięci: 64MB

Dany jest skierowany, acykliczny graf $G = (V, E)$. Przyporządkuj wierzchołkom $V$ parami różne numery $a[v_1], a[v_2], \ldots, a[v_{|V|}]$, gdzie $1 \le a[v] \le |V|$, tak by numeracja spełniała następujący warunek: $(u, v) \in E \implies a[u] < a[v]$.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $|V|$ i $|E|$. Następne $|E|$ wierszy zawiera po dwie liczby całkowite $u$ i $v$, oznaczające że $(u, v) \in E$. Wierzchołki oznaczamy identyfikatorami $1, 2, \ldots, |V|$.

Wyjście

Pierwszy wiersz wyjścia powinien zawierać $|V|$ liczb całkowitych. $a[v]$-tą liczbą powinno być $v$. Wypisz dowolne z rozwiązań.

Ograniczenia

• $1 \le n \le 10^5$
• $1 \le m \le 2 \cdot 10^5$
• $G$ jest DAG-iem

Przykłady

Wejście 1

5 3
1 2
3 1
4 5

Przykładowe wyjście 1

3 4 1 5 2