二分图排列

题目限制

1000 ms 256 M

题目描述

给出一个 $1$ 到 $n$ 的排列 $a$ ，我们将每个数字看做一个点，如果存在 $a[i]\gt a[j]$ 且 $i\lt j$ ，则在 $(i,j)$ 之间连一条边。

最终如果得到的图为二分图，那么我们称 $a$ 为二分图排列。二分图排列很稀有，因此给你一些机会，你可以选择 $a$ 中的一些数字，把他的值变为 $a[i]$ 的相反数。

问能否通过这样的修改，使得 $a$ 变为二分图排列？如果可以，请输出合法的修改方案，如果有多种方案，请输出字典序最小的。

输入格式

本题包含多组测试数据。第一行输入一个整数t，表示测试组数。 之后对于每组数据，第一行输入一个整数n； 第二行输入n个整数a[i]。 其中1≤n≤1e6，且保证所有测试数据中n的总和不超过1e6。

输出格式

对于每个测试用例，按以下格式输出答案： 如果这样的数组a不存在，仅输出一行一个"NO"； 否则第一行输出"YES"，并在第二行输出n个数，表示修改后的a[i]，数字间以空格隔开。

数据范围

对于10%的数据，$1\le t \le 5, 1\le n \le 5$；

对于50%的数据，$1\le t \le 100, 1\le n \le 50$；

对于100%的数据，$1\le t \le 2000, 1\le n \le 10^6, \sum n \le 10^6$。

输入样例

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