A. LRC и VIP
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$ размером $$$n$$$ — $$$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$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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)$$$. Следовательно, это не является ответом.