Problem 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.

3 3
1 2
2 3
3 1

1 2 3

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

1 3 4 2

5 8
1 2
2 3
3 4
4 1
2 5
4 5
5 1
5 3

1 2 3 4 5
1 2 5 3 4

5 10
1 2
1 3
2 3
2 4
3 4
3 5
4 1
4 5
5 1
5 2

1 2 3 4 5
1 3 5 2 4

6 15
1 3
1 4
1 5
2 1
2 3
2 4
3 1
3 4
4 2
4 6
5 2
5 3
6 1
6 2
6 3

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

6 15
1 3
1 5
2 1
2 4
3 1
3 2
3 4
3 5
3 6
4 6
5 1
5 4
5 6
6 3
6 5

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

6 16
1 3
1 6
2 3
2 4
2 6
3 1
3 6
4 2
4 3
4 5
4 6
5 2
5 6
6 1
6 3
6 5

1 6 5 2 4 3

6 21
1 2
1 5
1 6
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 6
4 1
4 2
4 6
5 1
5 2
5 4
5 6
6 2
6 3
6 4

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

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