Half-Topological Ordering

Jacob is studying graph theory. Today he learned that a \(\textit{topological ordering}\) of a directed graph is a linear ordering of its vertices such that for every directed edge \((u, v)\) the vertex \(u\) comes before \(v\) in the ordering.

However, topological orderings exist only for acyclic graphs. Jacob now wants to generalize this concept for arbitrary graphs. He introduces the concept of a half-topological ordering: a linear ordering of the vertices such that for at least half of all directed edges \((u, v)\) in the graph, \(u\) comes before \(v\) in the ordering. Formally, if the graph has \(m\) edges and an ordering satisfies the property for \(k\) of them, then the ordering is called half-topological if \(k \geq \lceil \frac{m}{2} \rceil\).

Your task is to help Jacob find any half-topological ordering for a given directed graph. If such an ordering exists, output one valid ordering; otherwise, output -1.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of vertices and edges respectively. The vertices are numbered from 1 to \(n\). Each of the following \(m\) lines contains two integers \(u\) and \(v\), indicating a directed edge from vertex \(u\) to vertex \(v\).

outputFormat

If a half-topological ordering exists, output a single line containing a permutation of vertices \(1, 2, ..., n\) that forms a half-topological ordering. Otherwise, output -1.

sample

3 2
1 2
3 2

1 2 3