CF1198F GCD Groups 2

给定一个包含 $n$ 个整数的数组。你需要将所有整数分成两个组，使得第一个组中所有整数的最大公约数等于 $1$，第二个组中所有整数的最大公约数也等于 $1$。 一组整数的最大公约数是能够整除该组所有整数的最大非负整数。 两个组都必须非空。

第一行包含一个整数 $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$ 个整数，第 $i$ 个整数为 $1$ 表示 $a_i$ 属于第一组，为 $2$ 表示 $a_i$ 属于第二组。 如果有多种方案，输出任意一种即可。

由 ChatGPT 4.1 翻译