Фарбування кола#12878

Фарбування кола

1 second
256 megabytes
Medium

Розглянемо точок, розташованих на колі. Ми хочемо пофарбувати їх в три кольори таким чином, щоб жодні дві сусідні точки не мали однаковий колір.

Але є додаткова умова: ми не можемо фарбувати точку в колір b_i. Чи можна пофарбувати всі точки?

Іншими словами, визначте, чи існують такі a_1, a_2, \ldots, a_n, що для кожного :

Якщо так, то знайдіть якісь такі a_1, a_2, \ldots, a_n.

Input

Перший рядок містить єдине ціле число (1 \le t \le 10^4)  — кількість наборів вхідних даних. Далі слідує опис наборів вхідних даних.

Перший рядок кожного набору вхідних даних містить єдине ціле число (3 \le n \le 2\cdot 10^5)  — кількість точок.

Другий рядок кожного набору вхідних даних містить цілих чисел b_1, b_2, \ldots, b_n (1 \le b_i \le 3)  — заборонені кольори.

Гарантується, що сума по всіх наборах вхідних даних не перевищує 2 \cdot 10^5.

Output

Для кожного набору вхідних даних, якщо такого розфарбування не існує, виведіть NO.

Інакше, виведіть YES. В наступному рядку виведіть чисел a_1, a_2, \ldots, a_n, що задовольняють всім вимогам з умови.

Виводити YES та NO можна у будь-якому регістрі (наприклад, рядки yEs, yes, Yes будуть сприйняті як позитивна відповідь).

Examples

Example 1

Loading
Loading