Задача №111897. Взлом шифра
Алан любит вскрывать шифры и кодовые замки. На этот раз ему попался необычайно сложный замок, найти ключ к которому Алану не удалось, поэтому он решил перебрать все возможные комбинации, чтобы узнать ключ.
Замок представляет собой \(n\) кнопок, пронумерованных целыми числами от 1 до \(n\). Замок открывается только тогда, когда какие-то последовательные \(n\) нажатий на кнопки образуют некоторую секретную перестановку. Кнопки замка следует нажимать по очереди, нажать одновременно две или более кнопки нельзя.
Более формально: предположим, что Алан нажал на кнопки \(k\) раз. Пусть \(a_i\) (\(1 \le i \le k\)) - номер кнопки, которую Алан нажал \(i\) по счету, а \(b_1, b_2, \ldots, b_n\) - секретная перестановка. Тогда замок открывается, если существует такое число \(x\) (\(1 \le x \le k - n + 1\)), что \(b_1 = a_x\), \(b_2 = a_{x+1}\),..., \(b_n = a_{x+n-1}\).
Алан хочет придумать такую универсальную последовательность нажатий, что при нажатии кнопок в такой последовательности замок откроется для любой секретной перестановки. Также Алан хочет, чтобы эта последовательность не была слишком длинной, а именно, ее длина не превышала \(2n!\), где \(n! = 1 \cdot 2 \cdot \ldots \cdot n\). Например, для \(n = 3\) длина последовательности не должна превышать 12.
Помогите Алану найти такую последовательность.
В единственной строке входного файла находится целое число \(n\) (\(1 \le n \le 9\)) - количество кнопок на кодовом замке.
В первой строке выходного файла выведите число \(k\) (\(0 \le k \le 2n!\)) - длину универсальной последовательности. Во второй строке выведите \(k\) целых чисел \(a_i\), разделенных пробелами (\(1 \le a_i \le n\)) - порядок, в котором следует нажимать кнопки. Обратите внимание, что достаточно вывести любую последовательность длины не более \(2n!\), минимизировать длину не нужно. Гарантируется, что такая последовательность существует для любого \(n\).
2
3 1 2 1
3
9 1 2 3 1 2 1 3 2 1