Вам задана перестановка \(p\), состоящая из \(n\) чисел \(1, 2, \dots, n\) (перестановка — это массив, в котором каждый элемент от \(1\) до \(n\) встречается ровно один раз).
Назовем массив \(a\) двудольным, если следующий неориентированный граф является двудольным:
Ваша задача — найти двудольный массив целых чисел \(a\) размера \(n\), такой что \(a_i = p_i\) или \(a_i = -p_i\), или сообщить, что такого массива не существует. Если существует несколько ответов, выведите любой из них.
Первая строка содержит одно целое число \(t\) (\(1 \le t \le 2 \cdot 10^5\)) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число \(n\) (\(1 \le n \le 10^6\)) — размер перестановки.
Вторая строка содержит \(n\) целых чисел \(p_1, p_2, \dots, p_n\).
Сумма \(n\) по всем наборам входных данных не превосходит \(10^6\).
Для каждого набора входных данных выведите ответ в следующей формате. Если соответствующего массива \(a\) не существует, выведите «NO» в единственной строке. Иначе выведите «YES» в первой строке и \(n\) целых чисел — массив \(a\) во второй строке.
4 3 1 2 3 6 1 3 2 6 5 4 4 4 1 3 2 8 3 2 1 6 7 8 5 4
YES 1 2 3 NO YES -4 -1 -3 -2 YES -3 -2 1 6 7 -8 -5 -4
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач