← 返回题目列表

Codeforces · 776/B

B. 夏洛克和他的女朋友

中文机器翻译题面 查看原题

夏洛克有了一个新女朋友(和他很不一样!)。情人节快到了,他想送她一些珠宝。

他买了n件珠宝。第 i 件首饰的价格等于 i + 1,即首饰的价格为 2, 3, 4, ... n + 1。

Watson 向 Sherlock 提出了一项挑战,要求他为这些珠宝首饰上色,如果一件首饰的价格是另一件首饰价格的质因数,则两件首饰的颜色不会相同。此外,沃森要求他尽量减少使用不同颜色的数量。

帮助夏洛克完成这个琐碎的任务。

输入

唯一一行包含单个整数 n (1 ≤ n ≤ 100000) — 珠宝首饰的数量。

输出

输出的第一行应包含一个整数 k,即在给定约束下可用于为珠宝首饰着色的最小颜色数。

下一行应包含 n 个空格分隔的整数(1 到 k 之间),按价格递增的顺序指定每件的颜色。

如果有多种使用 k 种颜色为碎片着色的方法,您可以输出其中任何一种。

示例

输入 #1

3

输出 #1

2
1 1 2

输入 #2

4

输出 #2

2
2 1 1 2

注意

在第一输入中,价格分别为2、3和4的第一件、第二件和第三件珠宝的颜色分别是1、1和2。

在这种情况下,由于 2 是 4 的质因数,因此价格为 2 和 4 的珠宝的颜色必须不同。