Problem Description

Technoblade abstracts Skyblock into a simple directed graph with $n$ ($n \leq 50$) nodes and $m$ edges. He needs to find all Hamiltonian circuits, 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 data guarantees that the number of Hamiltonian circuits is non-zero and less than $10^4$.

The data is sampled randomly from all valid data.

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 contains $n$ positive integers, representing a Hamiltonian circuit. Output them in increasing lexicographical order.

Sample Input and Output

Sample Input #1

3 3
1 2
2 3
3 1

Sample Output #1

1 2 3

Sample Input #2

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

Sample Output #2

1 3 4 2

Sample Input #3

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

Sample Output #3

1 2 3 4 5
1 2 5 3 4

Sample Input #4

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

Sample Output #4

1 2 3 4 5
1 3 5 2 4

Sample Input #5

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

Sample Output #5

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

Sample Input #6

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

Sample Output #6

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

Sample Input #7

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

Sample Output #7

1 6 5 2 4 3

Sample Input #8

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

Sample Output #8

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

Notes

Sample 1 Explanation

There is 1 Hamiltonian circuit:

• $1 \to 2 \to 3 \to 1$.

Sample 2 Explanation

There is 1 Hamiltonian circuit:

• $1 \to 3 \to 4 \to 2 \to 1$.

Sample 3 Explanation

There are 2 Hamiltonian circuits:

• $1 \to 2 \to 3 \to 4 \to 5 \to 1$;
• $1 \to 2 \to 5 \to 3 \to 4 \to 1$.

Sample 4 Explanation

There are 2 Hamiltonian circuits:

• $1 \to 2 \to 3 \to 4 \to 5 \to 1$;
• $1 \to 3 \to 5 \to 2 \to 4 \to 1$.

Sample 5 Explanation

There are 3 Hamiltonian circuits:

• $1 \to 5 \to 2 \to 3 \to 4 \to 6 \to 1$;
• $1 \to 5 \to 2 \to 4 \to 6 \to 3 \to 1$;
• $1 \to 5 \to 3 \to 4 \to 6 \to 2 \to 1$.

Sample 6 Explanation

There are 2 Hamiltonian circuits:

• $1 \to 3 \to 2 \to 4 \to 6 \to 5 \to 1$;
• $1 \to 5 \to 4 \to 6 \to 3 \to 2 \to 1$.

Sample 7 Explanation

There is 1 Hamiltonian circuit:

• $1 \to 6 \to 5 \to 2 \to 4 \to 3 \to 1$.

Sample 8 Explanation

There are 12 Hamiltonian circuits:

• $1 \to 2 \to 5 \to 4 \to 6 \to 3 \to 1$;
• $1 \to 2 \to 5 \to 6 \to 3 \to 4 \to 1$;
• $1 \to 5 \to 2 \to 3 \to 6 \to 4 \to 1$;
• $1 \to 5 \to 2 \to 4 \to 6 \to 3 \to 1$;
• $1 \to 5 \to 4 \to 6 \to 2 \to 3 \to 1$;
• $1 \to 5 \to 4 \to 6 \to 3 \to 2 \to 1$;
• $1 \to 5 \to 6 \to 2 \to 3 \to 4 \to 1$;
• $1 \to 5 \to 6 \to 3 \to 2 \to 4 \to 1$;
• $1 \to 5 \to 6 \to 3 \to 4 \to 2 \to 1$;
• $1 \to 5 \to 6 \to 4 \to 2 \to 3 \to 1$;
• $1 \to 6 \to 3 \to 2 \to 5 \to 4 \to 1$;
• $1 \to 6 \to 3 \to 4 \to 2 \to 5 \to 1$.

Data Constraints

For fixed $n$ and $P$, the weight of any graph with $m$ edges is $\left(\frac{1}{P}\right)^m\left(\frac{P-1}{P}\right)^{n^2-n-m}$.

• Subtask 1 (1 pts): Example cases.
• Subtask 2 (16 pts): $n = 15$.
• Subtask 3 (20 pts): $n = 30$.
• Subtask 4 (26 pts): $n = 40$.
• Subtask 5 (37 pts): $n = 50$.

见题面 Input 部分

见题面 Output 部分