시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB82342544.643%

문제

 $1$부터 $N$까지의 자연수를 색칠한다. 단, 서로소가 아닌 서로 다른 두 자연수는 다른 색으로 칠해야 한다. 최소한의 색을 써서 모든 자연수를 칠하는 방법을 찾는 프로그램을 작성하자.

입력

첫째 줄에 자연수 $N$이 주어진다. ($1 \le N \le 500\,000$)

출력

첫째 줄에 사용한 색의 수 $K$를 출력한다.

둘째 줄에 $N$개의 수를 공백을 사이에 두고 출력한다. $i$번째 수는 자연수 $i$의 색이다. 색은 $1$ 이상 $K$ 이하의 정수로 나타낸다.

예제 입력 1

5

예제 출력 1

2
1 1 1 2 1

출처