Permutations and cycles (1) P93873

Write a program to print all the permutations of {1, …, n} with exactly k cycles, where 1 ≤ k ≤ n. For exemple, consider the permutation (4, 3, 2, 5, 1, 7, 6). At position 1 there is a 4, at position 4 there is a 5, and at position 5 there is a 1. Therefore, one of the cycles is 1 → 4 → 5 → 1. The other two cycles are 2 → 3 → 2 and 6 → 7 → 6. The permutation (3,2,1) has the two cycles 1 → 3 → 1 and 2 → 2, and the permutation (3,4,5,6,7,1,2) only has the cycle 1 → 3 → 5 → 7 → 2 → 4 → 6 → 1.

Input

Input consists of n and k, with 1 ≤ k ≤ n.

Output

Print all the permutations of {1, …, n} with k cycles.

Information about the checker

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

Hint

A possible program does not build the permutations consecutively from left to right, but jumping over the solution, using a function

where i is the next cell to fill, ini is where the current cycle—still to be closed—starts, cells is the number of cells still free, and cycles is the number of cycles yet to be created.