Задача A. Взлом шифра

Автор:А. Васильев, В. Аксёнов (Жюри XXI командной олимпиады школьников СПб по информатике)   Ограничение времени:2 сек
Входной файл:cipher.in   Ограничение памяти:256 Мб
Выходной файл:cipher.out  

Условие

Алан любит вскрывать шифры и кодовые замки. На этот раз ему попался необычайно сложный замок, найти ключ к которому Алану не удалось, поэтому он решил перебрать все возможные комбинации, чтобы узнать ключ.

Замок представляет собой n кнопок, пронумерованных целыми числами от 1 до n. Замок открывается только тогда, когда какие-то последовательные n нажатий на кнопки образуют некоторую секретную перестановку. Кнопки замка следует нажимать по очереди, нажать одновременно две или более кнопки нельзя.

Более формально: предположим, что Алан нажал на кнопки k раз. Пусть ai (1 ≤ i ≤ k) — номер кнопки, которую Алан нажал i по счету, а b1, b2, …, bn — секретная перестановка. Тогда замок открывается, если существует такое число x (1 ≤ x ≤ k − n + 1), что b1 = ax, b2 = ax + 1, , bn = ax + n − 1.

Алан хочет придумать такую универсальную последовательность нажатий, что при нажатии кнопок в такой последовательности замок откроется для любой секретной перестановки. Также Алан хочет, чтобы эта последовательность не была слишком длинной, а именно, ее длина не превышала 2n!, где n! = 1 ⋅ 2 ⋅ … ⋅ n. Например, для n = 3 длина последовательности не должна превышать 12.

Помогите Алану найти такую последовательность.

Формат входного файла

В единственной строке входного файла находится целое число n (1 ≤ n ≤ 9) — количество кнопок на кодовом замке.

Формат выходного файла

В первой строке выходного файла выведите число k (0 ≤ k ≤ 2n!) — длину универсальной последовательности. Во второй строке выведите k целых чисел ai, разделенных пробелами (1 ≤ ai ≤ n) — порядок, в котором следует нажимать кнопки. Обратите внимание, что достаточно вывести любую последовательность длины не более 2n!, минимизировать длину не нужно. Гарантируется, что такая последовательность существует для любого n.

Примеры тестов

Входной файл (cipher.in) Выходной файл (cipher.out)
1
2
3
1 2 1
2
3
10
1 2 3 1 3 2 1 3 1 2

0.087s 0.009s 13