Finding dfs tree

You are given a simple directed graph $G$ with vertices numbered $1,2,\cdots,N$. The graph is connected when all edge directions are ignored.

Choose some edges of $G$ to form a rooted spanning tree satisfying all of the following conditions.

• Every non-root vertex $v$ has one parent $P_v$, and the directed edge $P_v \to v$ exists in $G$.
• For the root $r$, $P_r=-1$.
• The selected $N-1$ edges $P_v \to v$ form a rooted spanning tree directed from parents to children.
• For every directed edge $u \to v$ that is not selected as a tree edge, $v$ is a proper ancestor of $u$ in the tree.

A proper ancestor of a vertex is an ancestor other than the vertex itself.

The following figure shows one valid example. Red edges are tree edges directed from parents to children. Blue edges are non-tree edges directed from descendants to ancestors.

Find a parent sequence $P_1,P_2,\cdots,P_N$ satisfying the conditions, or report that none exists.

The input is given in the following format:

$N\ M$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_M\ v_M$

The $i$-th edge is directed from $u_i$ to $v_i$.

If a valid tree exists, print $P_1,P_2,\cdots,P_N$ separated by spaces on one line. The parent of the root must be printed as $-1$.

If there are multiple solutions, print any of them.

If no valid tree exists, print -1 on one line.

When $N=1$, the single value -1 is a valid parent sequence.

• $1 \leq N \leq 100\,000$.
• $0 \leq M \leq 100\,000$.
• $1 \leq u_i,v_i \leq N$ ($1 \leq i \leq M$).
• $u_i \neq v_i$ ($1 \leq i \leq M$).
• $(u_i,v_i) \neq (u_j,v_j)$ ($1 \leq i < j \leq M$).
• The graph is connected when all edge directions are ignored.