CF2157H Keygen 3

[Trey Frey - Refresh](https://soundcloud.com/user-553403696/refresh-trey-frey) ⠀ A permutation $ ^{\text{∗}} $ of length $ n $ is called valid if it has both of the following properties: - It is bitonic $ ^{\dagger} $ ; - Exactly $ m $ of its subsets are cycles $ ^{\ddagger} $ . Let $ k $ denote the number of permutations satisfying the above condition. Your task is to find and print $ \min(k, 2000) $ examples of such permutations. $ ^{\dagger} $ A permutation $ p_1, p_2, \ldots, p_n $ is bitonic if there exists an index $ i $ ( $ 1 \leq i \leq n $ ) such that - $ p_{j-1} \leq p_j $ for $ 2 \leq j \leq i $ ; - $ p_j \geq p_{j+1} $ for $ i \leq j \leq n-1 $ . $ ^{\ddagger} $ A subset $ C \subseteq \{ 1, 2, \ldots, n \} $ is a cycle if it satisfies the following conditions: - $ C $ is non-empty; - if $ x \in C $ , then $ p_x \in C $ ; - $ C $ is minimal, i.e., there does not exist a cycle $ C' $ such that $ C' \subset C $ . $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

The input consists of a single line containing two integers $ n $ , $ m $ ( $ 1 \le m \leq n \le 100 $ ) — the length of the permutations and the target number of cycles.

In the first line, print a single integer $ r $ : the number of permutations you are going to print. Note that $ r $ must be $ \min(k, 2000) $ as defined in the statement. Then, print $ r $ lines. Each line must contain a bitonic permutation of length $ n $ , with $ m $ cycles.

In the example, there are $ 9 $ valid permutations (i.e., bitonic permutations of length $ 6 $ , with $ 3 $ cycles). For example, $ [3, 5, 6, 4, 2, 1] $ is bitonic (in the above definition, $ i = 3 $ ), and it has $ 3 $ cycles: $ \{1, 3, 6\} $ , $ \{2, 5\} $ , $ \{4\} $ . So you have to print $ r = \min(9, 2000) = 9 $ such permutations.