Problem G: NPC

Problem G: NPC

Time Limit: 2 Sec  Memory Limit: 256 MB  Special Judge
Submit: 78  Solved: 23
[Submit][Status][Web Board]


Yuki is a clever girl and she firmly believes that \(NP\neq P\).

One day TruthBoy, a friend of Yuki, claims that he has found a polynomial-time algorithm to solve Hamiltonian cycle problem, a famous NP-Complete problem.

There is a graph \(G=(V,E)\) with \(n\) nodes and \(m\) edges. Each road is unidirectional, that is an edge from \(u\) to \(v\) cannot be passed from \(v\) to \(u\). Let node \(1\) be the capital. The path starting at the capital node, visiting every non-capital node exactly once, and finishing in the capital is called a Hamiltonian cycle. And to determine the existence of Hamiltonian cycles in a given graph is called the Hamiltonian cycle problem.

Yuki does not think that TruthBoy has really solved the problem. However, TruthBoy can always give the correct answers to Yuki’s tests. To know the truth, Yuki turns to you for help. Can you help her to find out how TruthBoy solves the problem?


The first line contains two integers: \(n\) and \(m\) \((2 \leq n \leq 100\ 000,\ 0 \leq m \leq n + 20)\) — the number of nodes and directed edges in the graph.

Each of the next \(m\) lines contains two integers: \(u\) and \(v\) \((1 \leq u,\ v\leq n)\), meaning that there is a directional edge from node \(u\) to node \(v\).

Nodes are numbered from \(1\) to \(n\). The capital is numbered as \(1\).


If there are multiple Hamiltonian cycles, you can print any of them. Print one line with \(n+1\) space-separated integers — a list of nodes along the cycle.

If there is no Hamiltonian cycle, just print “ovarB” (without quotation).

Sample Input

4 6
1 4
4 1
4 2
2 1
3 4
1 3

Sample Output

1 3 4 2 1


Please remind that your code is judged by a special judge, and any valid answers will be accepted.