Злам шифру#6283

Злам шифру

2 секунди

256 мегабайтів

Складна

Алан захоплюється розгадуванням шифрів і кодових замків. Цього разу він зіткнувся з надзвичайно складним замком, для якого не зміг знайти ключ, тому вирішив перебрати всі можливі комбінації, щоб дізнатися код.

Замок має $n$ кнопок, пронумерованих від $1$ до $n$ . Замок відкривається лише тоді, коли певна послідовність із $n$ натискань утворює секретну перестановку. Кнопки потрібно натискати по черзі, одночасне натискання кількох кнопок неможливе.

Більш формально: припустимо, що Алан натиснув кнопки $k$ разів. Нехай $a_{i}$ a_i ( $1 \leq i \leq k$ 1 \leq i \leq k) — це номер кнопки, яку Алан натиснув $i$ -м за рахунком, а $b_{1}$ b_1, $b_{2}$ b_2, ..., $b_{n}$ b_n — секретна перестановка. Замок відкриється, якщо існує таке число $x$ ( $1 \leq x \leq k - n + 1$ 1 \leq x \leq k - n + 1), що $b_{1} = a_{x}$ b_1 = a_x, $b_{2} = a_{x + 1}$ b_2 = a_{x+1}, ..., $b_{n} = a_{x + n - 1}$ b_n = a_{x+n-1}.

Алан хоче створити універсальну послідовність натискань, яка відкриє замок для будь-якої секретної перестановки. Він також прагне, щоб ця послідовність не була занадто довгою, тобто її довжина не перевищувала $2 n!$ , де $n! = 1 \cdot 2 \cdot ... \cdot n$ n! = 1 \cdot 2 \cdot ... \cdot n. Наприклад, для $n = 3$ n = 3 довжина послідовності не повинна перевищувати $12$ .

Допоможіть Алану знайти таку послідовність.

Вхідні дані

У єдиному рядку вхідного файлу задано ціле число $n$ ( $1 \leq n \leq 9$ 1 \leq n \leq 9) — кількість кнопок на кодовому замку.

Вихідні дані

У першому рядку вихідного файлу виведіть число $k$ ( $0 \leq k \leq 2 n!$ 0 \leq k \leq 2n!) — довжину універсальної послідовності. У другому рядку виведіть $k$ цілих чисел $a_{i}$ a_i, розділених пробілами ( $1 \leq a_{i} \leq n$ 1 \leq a_i \leq n) — порядок натискання кнопок. Зверніть увагу, що достатньо вивести будь-яку послідовність довжини не більше $2 n!$ , мінімізувати довжину не потрібно. Гарантується, що така послідовність існує для будь-якого $n$ .

Приклади

Приклад 1