Enumeration of Hamiltonian Cycles in a Directed Graph

Technoblade abstracts Skyblock as a simple directed graph with \(n\) nodes and \(m\) edges where \(n \le 50\). You are required to find all Hamiltonian cycles in this graph.

A Hamiltonian cycle is defined as a permutation \(p_1, p_2, \dots, p_n\) of the vertices such that \(p_1 = 1\) and the path \[ p_1 \to p_2 \to \dots \to p_{n-1} \to p_n \to p_1 \] is valid (i.e. there exists a directed edge from each vertex to the next, and from \(p_n\) back to \(p_1\)).

Constraints:

• The number of Hamiltonian cycles is guaranteed to be nonzero and less than \(10^4\).
• The input is randomly sampled from all valid test cases.

inputFormat

The first line contains two integers \(n\) and \(m\), which represent the number of nodes and edges respectively.

The following \(m\) lines each contain two integers \(u\) and \(v\), representing a directed edge from \(u\) to \(v\) in the graph.

It is guaranteed that \(1 \leq u, v \leq n\) and the graph does not contain multiple edges or self loops.

outputFormat

Output all Hamiltonian cycles starting from vertex 1. Each cycle should be printed as a single line with \(n\) space-separated integers representing the order of vertices in the cycle.

The cycle \(p_1, p_2, \dots, p_n\) is valid if there exists a directed edge from \(p_i\) to \(p_{i+1}\) for \(1 \leq i < n\), and an edge from \(p_n\) to \(p_1\).

sample

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

1 2 3 4