29496번 - Ахроматическое число графа 스페셜 저지다국어

문제

Хроматическим числом графа называют минимальное количество цветов, которое необходимо для того, чтобы раскрасить его вершины таким образом, чтобы никакие две вершины одного цвета не были соединены ребром. Такая раскраска вершин графа называется правильной. Известно, что нахождение хроматического числа графа является трудной задачей.

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

Например, ахроматическое число треугольника равно трем, поскольку если раскрасить все его вершины в различные цвета, каждая пара цветов будет встречаться на концах некоторого ребра.

Вам дано число $n$. Найдите ахроматическое число цикла длиной $n$ и выведите соответствующую ахроматическую раскраску.

입력

Входной файл содержит одно целое число $n$ (3ドル \le n \le 1000$).

출력

На первой строке выходного файла выведите одно число $a$ --- ахроматическое число цикла длиной $n$. Вторая строка должна содержать $n$ целых чисел в диапазоне от 1 до $a$ и описывать соответствующую правильную ахроматическую раскраску.5

제한

힌트