CF1198F.GCD Groups 2

You are given an array of $n$ integers. You need to split all integers into two groups so that the GCD of all integers in the first group is equal to one and the GCD of all integers in the second group is equal to one.

The GCD of a group of integers is the largest non-negative integer that divides all the integers in the group.

Both groups have to be non-empty.

给你一个包含 $n$ 个整数的数组。你需要将所有整数划分为两个组，使得第一组中所有整数的最大公约数（GCD）等于 $1$，且第二组中所有整数的最大公约数也等于 $1$。

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

两个组都必须非空。

The first line contains a single integer $n$ ($2 \leq n \leq 10^5$).

The second line contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array.

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

第二行包含 $n$ 个整数 $a_1$, $a_2$, $\ldots$, $a_n$（$1 \leq a_i \leq 10^9$）—— 数组的元素。

In the first line print "YES" (without quotes), if it is possible to split the integers into two groups as required, and "NO" (without quotes) otherwise.

If it is possible to split the integers, in the second line print $n$ integers, where the $i$-th integer is equal to $1$ if the integer $a_i$ should be in the first group, and $2$ otherwise.

If there are multiple solutions, print any.

如果可以将这些整数按要求分成两组，则在第一行输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。

如果可以完成划分，则在第二行输出 $n$ 个整数，其中第 $i$ 个整数为 $1$ 表示整数 $a_i$ 应属于第一组，为 $2$ 表示应属于第二组。

如有多种解法，输出任意一种即可。