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

시간 제한2초메모리 제한1024 MB

요약

길이 n인 사이클의 아크로마틱 수와, 모든 색 쌍이 어떤 변의 양 끝에 나타나는 올바른 색칠을 출력한다.

난이도: 보통10점 중 6점
유형: 수학, 그리디, 조합론
정답자: 아직 제출이 없습니다

문제

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

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

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

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

입력

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

출력

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

예제1

예제 1
입력
```
3
```
예상 출력
```
3
1 2 3
```