Topological Sort (DFS-based) - Classic Problems | Repovive

CLS18. Topological Sort (DFS-based)

1s256 MB

Given a directed acyclic graph (DAG) with $n$ vertices and $m$ edges, find a topological ordering of the vertices using DFS-based algorithm.

A topological ordering is a linear ordering of vertices such that for every directed edge $u \to v$ , vertex $u$ comes before $v$ .

Output the topological ordering produced by starting DFS from the highest-numbered unvisited vertex and processing neighbors in reverse order of their vertex numbers. If the graph contains a cycle, output -1.

Constraints

$1 \le n \le 10^5$
$0 \le m \le 10^5$

Input

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

Output

\begin{cases} p_1 \quad p_2 \quad \cdots \quad p_n & \text{any valid topological order} \\ -1 & \text{if a cycle exists} \end{cases}

Samples

Input

Explanation

For this input, the required output is 1 3 2 4.

Output

1 3 2 4

Input

Explanation

For this input, the required output is -1.

Output

-1

Input

Explanation

For this input, the required output is 1 3 2 4 6 5.

Output

1 3 2 4 6 5

Given a directed acyclic graph (DAG) with $n$ vertices and $m$ edges, find a topological ordering of the vertices using DFS-based algorithm.

A topological ordering is a linear ordering of vertices such that for every directed edge $u \to v$ , vertex $u$ comes before $v$ .

$1 \le n \le 10^5$
$0 \le m \le 10^5$

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

\begin{cases} p_1 \quad p_2 \quad \cdots \quad p_n & \text{any valid topological order} \\ -1 & \text{if a cycle exists} \end{cases}