CF2107A LRC and VIP

You have an array $ a $ of size $ n $ — $ a_1, a_2, \ldots a_n $ . You need to divide the $ n $ elements into $ 2 $ sequences $ B $ and $ C $ , satisfying the following conditions: - Each element belongs to exactly one sequence. - Both sequences $ B $ and $ C $ contain at least one element. - $ \gcd $ $ (B_1, B_2, \ldots, B_{|B|}) \ne \gcd(C_1, C_2, \ldots, C_{|C|}) $ $ ^{\text{∗}} $ $ ^{\text{∗}} $ $ \gcd(x, y) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 2 \le n \le 100 $ ). The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le 10^4 $ ).

For each test case, first output $ \texttt{Yes} $ if a solution exists or $ \texttt{No} $ if no solution exists. You may print each character in either case, for example $ \texttt{YES} $ and $ \texttt{yEs} $ will also be accepted. Only when there is a solution, output $ n $ integers on the second line. The $ i $ -th number should be either $ 1 $ or $ 2 $ . $ 1 $ represents that the element belongs to sequence $ B $ and $ 2 $ represents that the element belongs to sequence $ C $ . You should guarantee that $ 1 $ and $ 2 $ both appear at least once.

In the first test case, $ B = [51, 9] $ and $ C = [1, 20] $ . You can verify $ \gcd(B_1, B_2) = 3 \ne 1 = \gcd(C_1, C_2) $ . In the second test case, it is impossible to find a solution. For example, suppose you distributed the first $ 3 $ elements to array $ B $ and then the last element to array $ C $ . You have $ B = [5, 5, 5] $ and $ C = [5] $ , but $ \gcd(B_1, B_2, B_3) = 5 = \gcd(C_1) $ . Hence it is invalid.