← 返回题目列表

Codeforces · 2107/A

A. LRC 和 VIP

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

你有一个大小为 $$$n$$$ 的数组 $$$a$$$ — $$$a_1, a_2, \ldots a_n$$$。

需要将$$$n$$$元素划分为$$$2$$$序列$$$B$$$和$$$C$$$,满足以下条件:

  • 每个元素都属于一个序列。
  • 序列 $$$B$$$ 和 $$$C$$$ 都至少包含一个元素。
  • $$$\gcd$$$ $$$(B_1, B_2, \ldots, B_{|B|}) \ne \gcd(C_1, C_2, \ldots, C_{|C|})$$$ $$$^{\text{*}}$$$

$$$^{\text{*}}$$$$$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^4$$$)。

输出

对于每个测试用例,如果存在解决方案,则首先输出 $$$\texttt{Yes}$$$;如果不存在解决方案,则首先输出 $$$\texttt{No}$$$。您可以在任一情况下打印每个字符,例如 $$$\texttt{YES}$$$ 和 $$$\texttt{yEs}$$$ 也将被接受。

只有当有解时,才在第二行输出$$$n$$$个整数。第 $$$i$$$ 个数字应该是 $$$1$$$ 或 $$$2$$$。 $$$1$$$表示该元素属于序列$$$B$$$,$$$2$$$表示该元素属于序列$$$C$$$。

您应该保证 $$$1$$$ 和 $$$2$$$ 都至少出现一次。

示例

输入
复制

3
4
1 20 51 9
4
5 5 5 5
3
1 2 2

输出
复制

Yes
2 2 1 1
No
Yes
1 2 2

注意

在第一个测试用例中,$$$B = [51, 9]$$$ 和 $$$C = [1, 20]$$$。您可以验证 $$$\gcd(B_1, B_2) = 3 \ne 1 = \gcd(C_1, C_2)$$$。

在第二个测试用例中,不可能找到解决方案。例如,假设您将前 $$$3$$$ 元素分配给数组 $$$B$$$,然后将最后一个元素分配给数组 $$$C$$$。您有 $$$B = [5, 5, 5]$$$ 和 $$$C = [5]$$$,但是 $$$\gcd(B_1, B_2, B_3) = 5 = \gcd(C_1)$$$。因此它是无效的。