Перестановка длины \(n\) — это последовательность целых чисел от \(1\) до \(n\) такая, что каждое число встречается в ней ровно один раз.
Назовем неподвижностью перестановки \(p\) количество неподвижных точек в ней — количество позиций \(j\) таких, что \(p_j = j\), где \(p_j\) — \(j\)-й элемент перестановки \(p\).
От вас требуется построить последовательность перестановок \(a_1, a_2, \dots\), начав с тождественной перестановки (перестановки \(a_1 = [1, 2, \dots, n]\)). Назовем это цепочкой перестановок. Таким образом, каждое \(a_i\) — \(i\)-я перестановка длины \(n\).
Для каждого \(i\) от \(2\) и дальше перестановка \(a_i\) должна быть получена из перестановки \(a_{i-1}\) обменом двух элементов местами (не обязательно соседних). Неподвижность перестановки \(a_i\) должна быть строго меньше неподвижности перестановки \(a_{i-1}\).
Рассмотрим некоторые цепочки для \(n = 3\):
- \(a_1 = [1, 2, 3]\), \(a_2 = [1, 3, 2]\) — это валидная цепочка длины \(2\). От \(a_1\) к \(a_2\) элементы на позициях \(2\) и \(3\) меняются местами, неподвижность уменьшается с \(3\) до \(1\).
- \(a_1 = [2, 1, 3]\), \(a_2 = [3, 1, 2]\) — это не валидная цепочка. Первая перестановка всегда должна быть \([1, 2, 3]\) для \(n = 3\).
- \(a_1 = [1, 2, 3]\), \(a_2 = [1, 3, 2]\), \(a_3 = [1, 2, 3]\) — это не валидная цепочка. От \(a_2\) к \(a_3\) элементы на позициях \(2\) и \(3\) меняются местами, но неподвижность увеличивается с \(1\) до \(3\).
- \(a_1 = [1, 2, 3]\), \(a_2 = [3, 2, 1]\), \(a_3 = [3, 1, 2]\) — это валидная цепочка длины \(3\). От \(a_1\) к \(a_2\) элементы на позициях \(1\) и \(3\) меняются местами, неподвижность уменьшается с \(3\) до \(1\). От \(a_2\) к \(a_3\) элементы на позициях \(2\) и \(3\) меняются местами, неподвижность уменьшается с \(1\) до \(0\).
Найдите самую длинную цепочку перестановок. Если есть несколько самых длинных ответов, то выведите любой из них.
Выходные данные
На каждый набор входных данных сначала выведите длину цепочки перестановок \(k\).
Затем выведите \(k\) перестановок \(a_1, a_2, \dots, a_k\). \(a_1\) должна быть тождественной перестановкой длины \(n\) (\([1, 2, \dots, n]\)). Для каждого \(i\) от \(2\) до \(k\), \(a_i\) должно быть получено обменом двух элементов в \(a_{i-1}\) местами и должно иметь строго меньшее значение, чем \(a_{i-1}\).