From one to en (2) P53046

Write a program that prints all the permutations of $\{ 1, \dots, n \}$ with exactly one cycle, for a given $n$. Assume that the content of the position $i$ of a permutation indicates “the next position to visit”.

For instance, consider the permutation $(4,3,2,5,1,7,6)$. The position 1 has a 4, the position 4 has a 5, and the position 5 has a 1. Therefore, one of the cycles of this permutation is $1 \to 4 \to 5 \to 1$. The other two cycles are $2 \to 3 \to 2$ and $6 \to 7 \to 6$. The permutation $(3,2,1)$ has the two cycles $1 \to 3 \to 1$ and $2 \to 2$. The permutation $(3,4,5,6,7,1,2)$ has only the cycle $1 \to 3 \to 5 \to 7 \to 2 \to 4 \to 6 \to 1$.

Input

Input consists of a natural number $n > 0$.

Output

Print all the permutations of $\{ 1, \dots, n \}$ with only one cycle.

Information about the checker

You can print the solutions to this exercise in any order.

Hint

The judge may accept a program that generates all the permutations and, for each one, checks if it only has one cycle. However, this is not the right solution for this problem.