print2148. Ахроматическое число графа

printАхроматическое число графа

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Хроматическим числом графа называют минимальное количество цветов, которое необходимо для того, чтобы раскрасить его вершины таким образом, чтобы никакие две вершины одного цвета не были соединены ребром. Такая раскраска вершин графа называется правильной. Известно, что нахождение хроматического числа графа является трудной задачей.
Правильная раскраска графа в свою очередь называется ахроматической, если каждая пара различных цветов встречается на концах некоторого ребра. Ахроматическим числом графа называют максимальное количество цветов, которое можно использовать для раскраски вершин графа, чтобы полученная раскраска была ахроматической.
Например, ахроматическое число треугольника равно трем, поскольку если раскрасить все его вершины в различные цвета, каждая пара цветов будет встречаться на концах некоторого ребра.
Вам дано число `n`. Найдите ахроматическое число цикла длиной `n` и выведите соответствующую ахроматическую раскраску.
Входной файл содержит одно целое число `n` (`3\ ≤\ n\ ≤\ 1000`).
На первой строке выходного файла выведите одно число `a` – ахроматическое число цикла длиной `n`. Вторая строка должна содержать `n` целых чисел в диапазоне от 1 до `a` и описывать соответствующую правильную ахроматическую раскраску.

Пример ввода

3

Пример вывода

3
1 2 3
Источник: neerc.ifmo.ru/school
loading