Repovive

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/CLS/problems/11

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/CLS/problems/11

Repovive

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$

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

Each edge goes from $u_i$ to $v_i$ .

$p_1 \quad p_2 \quad \cdots \quad p_n$

Any valid topological ordering, or $-1$ if a cycle exists.

CLS11. Topological Sort (DFS-based)

Constraints

Input

Output

Samples

Constraints