如果长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ 被称为有效,如果它具有以下两个属性:
- 这是双音$$$^{\dagger}$$$;
- 其子集中的$$$m$$$ 恰好是周期$$$^{\ddagger}$$$。
令$$$k$$$表示满足上述条件的排列数。您的任务是查找并打印 $$$\min(k, 2000)$$$ 此类排列的示例。
$$$^{\dagger}$$$ 如果存在索引 $$$i$$$ ($$$1 \leq i \leq n$$$) ,则排列 $$$p_1, p_2, \ldots, p_n$$$ 是双调的
- $$$p_{j-1} \leq p_j$$$ 对于 $$$2 \leq j \leq i$$$;
- $$$p_j \geq p_{j+1}$$$ 对于 $$$i \leq j \leq n-1$$$。
$$$^{\ddagger}$$$ 子集 $$$C \subseteq \{ 1, 2, \ldots, n \}$$$ 是一个循环,如果它满足以下条件:
- $$$C$$$ 非空;
- 如果 $$$x \in C$$$,则 $$$p_x \in C$$$;
- $$$C$$$ 是最小的,即不存在循环 $$$C'$$$ 使得 $$$C'\子集 C$$$。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
输入由一行组成,其中包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \le m \leq n \le 100$$$) - 排列的长度和目标循环数。
输出
在第一行中,打印一个整数 $$$r$$$:要打印的排列数。请注意,$$$r$$$ 必须是语句中定义的 $$$\min(k, 2000)$$$。
然后,打印 $$$r$$$ 行。每行必须包含长度为 $$$n$$$ 的双音排列,循环为 $$$m$$$。
示例
输入复制
6 3
输出复制
9 1 4 5 6 3 2 6 5 4 3 2 1 1 2 4 5 6 3 1 2 5 6 4 3 1 3 4 6 5 2 1 5 6 4 3 2 3 5 6 4 2 1 1 3 6 5 4 2 2 6 5 4 3 1
注意
在示例中,有 $$$9$$$ 有效排列(即,长度为 $$$6$$$ 的双音排列,具有 $$$3$$$ 周期)。例如,$$$[3, 5, 6, 4, 2, 1]$$$ 是双调的(在上面的定义中,$$$i = 3$$$),并且它有 $$$3$$$ 周期:$$$\{1, 3, 6\}$$$,$$$\{2, 5\}$$$,$$$\{4\}$$$。所以你必须打印 $$$r = \min(9, 2000) = 9$$$ 这样的排列。