← 返回题目列表

Codeforces · 1198/F

F. GCD 组 2

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

给你一个 $$$n$$$ 整数数组。您需要将所有整数分成两组,以便第一组中所有整数的 GCD 等于 1,第二组中所有整数的 GCD 等于 1。

一组整数的 GCD 是整除该组中所有整数的最大非负整数。

两个组都必须非空。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组的元素。

输出

如果可以根据需要将整数分成两组,则在第一行打印“YES”(不带引号),否则打印“NO”(不带引号)。

如果可以拆分整数,则在第二行中打印 $$$n$$$ 个整数,其中如果整数 $$$a_i$$$ 应位于第一组中,则第 $$$i$$$ 个整数等于 $$$1$$$,否则为 $$$2$$$。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

4
2 3 6 7

输出 #1

YES
2 2 1 1

输入 #2

5
6 15 35 77 22

输出 #2

YES
2 1 2 1 1

输入 #3

5
6 10 15 1000 75

输出 #3

NO