Petya is preparing a problem for a local contest in his school. The problem is to find a longest increasing subsequence in a given permutation. A permutation of size n$n$ is a sequence of n$n$ numbers a1,…,an$a_1, \ldots, a_n$ such that every number from 1$1$ to n$n$ occurs in the sequence exactly once. An increasing subsequence of length k$k$ of the sequence a1,…,an$a_1, \ldots, a_n$ is a sequence of indices i1,…,ik$i_1, \ldots, i_k$ such that 1≤i1<…<ik≤n$1 \leq i_1 < \ldots < i_k \leq n$ and ai1<…<aik$a_{i_1} < \ldots < a_{i_k}$. A longest increasing subsequence is an increasing subsequences with the largest length. Note that in general there may be several longest increasing subsequences.
Petya had some tests prepared, but then lost the input part for some of them. He now has a test for a certain value of n$n$, and a sequence i1,…,ik$i_1, \ldots, i_k$ that is supposed to be a longest increasing subsequence. Petya now has to reconstruct a permutation of size n$n$ with this sequence being an answer. Petya doesn't want to take any risks, so he additionally wants this sequence to be the only longest increasing subsequence, that is, all other increasing subsequences have to have strictly smaller length. Help Petya determine if this is possible, and if so, construct any such permutation.

-----Input:-----
The first line contains an integer T$T$, denoting number of test cases.
The first line of every test case contains two integers n$n$ and k−$k-$  the size of the permutation and the length of the longest increasing subsequence (1≤k≤n≤105$1 \leq k \leq n \leq 10^5$).
The second line contains k$k$ integers i1,…,ik−$i_1, \ldots, i_k-$ the longest increasing subsequence (1≤i1<…<ik≤n$1 \leq i_1 < \ldots < i_k \leq n$).

-----Output:-----
If there is no permutation with the sequence i1,…,ik$i_1, \ldots, i_k$ being the only longest increasing subsequence, print NO . Otherwise, print YES on the first line, followed by n$n$ numbers describing any suitable permutation on the second line.

-----Constraints-----
- 1≤T≤10$1 \leq T \leq 10$
- 1≤k≤n≤105$1 \leq k \leq n \leq 10^5$ 
- 1≤i1<…<ik≤n$1 \leq i_1 < \ldots < i_k \leq n$ 

-----Sample Input:-----
2
3 2
1 2
2 1
1

-----Sample Output:-----
YES
2 3 1
NO

Difficulty: VERY_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = [int(c) for c in input().split()]
	a = [int(c) for c in input().split()]
	ls = a
	if n == 1:
		print('YES')
		print(1)
		continue
	if k == 1:
		print('NO')
		continue
	if k == 2 and n > 2:
		if ls[0] != ls[1] - 1:
			print('NO')
			continue
	ans = [0 for i in range(n + 1)]
	count = n
	for i in range(1, a[1]):
		if i != a[0]:
			ans[i] = count
			count -= 1
	for i in a[::-1]:
		ans[i] = count
		count -= 1
	for i in range(1, n + 1):
		if ans[i] == 0:
			ans[i] = count
			count -= 1
	print('YES')
	print(*ans[1:])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	if n == 1:
		print('YES')
		print(1)
		continue
	if k == 1:
		print('NO')
		continue
	if k == 2 and n > 2:
		if ls[0] != ls[1] - 1:
			print('NO')
			continue
	print('YES')
	mx = n
	arr = [0] * n
	for i in range(ls[0] - 1):
		arr[i] = mx
		mx -= 1
	for i in range(ls[0], ls[1] - 1):
		arr[i] = mx
		mx -= 1
	for i in range(k - 1, -1, -1):
		arr[ls[i] - 1] = mx
		mx -= 1
	for i in range(1, n):
		if arr[i] == 0:
			arr[i] = mx
			mx -= 1
	print(*arr)