P8281 "MCOI-08" Fast Enumeration
Description
Technoblade abstracts Skyblock as a simple directed graph with $n$ nodes ($n\le 50$) and $m$ edges. He needs to find **all** Hamiltonian cycles in this graph, i.e., all permutations $p_1,p_2,\dots,p_n$ such that $p_1=1$ and $p_1\to p_2\to \dots\to p_{n-1}\to p_n\to p_1$ is a valid path.
**The testdata guarantees that the number of Hamiltonian cycles is non-zero and less than $10^4$.**
**The testdata is sampled randomly from all valid inputs.**
Input Format
The first line contains two positive integers $n,m$.
The next $m$ lines each contain two positive integers $u,v$.
Output Format
Output several lines. Each line outputs $n$ positive integers, representing one Hamiltonian cycle. Output them in increasing lexicographical order.
Explanation/Hint
#### Explanation for Sample 1
There is $1$ Hamiltonian cycle:
- $1\to2\to3\to1$.
#### Explanation for Sample 2
There is $1$ Hamiltonian cycle:
- $1\to3\to4\to2\to1$.
#### Explanation for Sample 3
There are $2$ Hamiltonian cycles:
- $1\to2\to3\to4\to5\to1$;
- $1\to2\to5\to3\to4\to1$.
#### Explanation for Sample 4
There are $2$ Hamiltonian cycles:
- $1\to2\to3\to4\to5\to1$;
- $1\to3\to5\to2\to4\to1$.
#### Explanation for Sample 5
There are $3$ Hamiltonian cycles:
- $1\to5\to2\to3\to4\to6\to1$;
- $1\to5\to2\to4\to6\to3\to1$;
- $1\to5\to3\to4\to6\to2\to1$.
#### Explanation for Sample 6
There are $2$ Hamiltonian cycles:
- $1\to3\to2\to4\to6\to5\to1$;
- $1\to5\to4\to6\to3\to2\to1$.
#### Explanation for Sample 7
There is $1$ Hamiltonian cycle:
- $1\to6\to5\to2\to4\to3\to1$.
#### Explanation for Sample 8
There are $12$ Hamiltonian cycles:
- $1\to2\to5\to4\to6\to3\to1$;
- $1\to2\to5\to6\to3\to4\to1$;
- $1\to5\to2\to3\to6\to4\to1$;
- $1\to5\to2\to4\to6\to3\to1$;
- $1\to5\to4\to6\to2\to3\to1$;
- $1\to5\to4\to6\to3\to2\to1$;
- $1\to5\to6\to2\to3\to4\to1$;
- $1\to5\to6\to3\to2\to4\to1$;
- $1\to5\to6\to3\to4\to2\to1$;
- $1\to5\to6\to4\to2\to3\to1$;
- $1\to6\to3\to2\to5\to4\to1$;
- $1\to6\to3\to4\to2\to5\to1$.
#### Constraints and Notes
For fixed $n$ and $P$, any graph with $m$ edges has weight $\left(\frac{1}{P}\right)^m\left(\frac{P-1}{P}\right)^{n^2-n-m}$.
- Subtask 1 (1 pts): the samples.
- Subtask 2 (16 pts): $n=15$.
- Subtask 3 (20 pts): $n=30$.
- Subtask 4 (26 pts): $n=40$.
- Subtask 5 (37 pts): $n=50$.
Translated by ChatGPT 5