#437 Finding dfs tree

Statement

Statement language

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 .

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.

Input

The input is given in the following format:

$N\ M$ $u_1\ v_1$ $u_{}$

Output

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 .

Constraints

$1 \leq N \leq 100\,000$ .
$0 \leq M \leq 100\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	6	$N \leq 8$ . $M \leq 16$ .
2	14	$M=N-1$ .

Samples

Sample 1

Input

Output

-1 1 1 2 2 3

Choose vertex $1$ as the root and the red edges in the figure as tree edges. Every blue edge points from a descendant to an ancestor.

Sample 2

Input

Output

-1

No rooted spanning tree satisfies all conditions.