Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef and his friend Chefu decided to go on a trip. The trip takes place over the next $N$ days (numbered 1 through $N$). There are $K$ different places Chef and Chefu could visit (numbered 1 through $K$). They have written a sequence $A_{1}, A_{2}, \ldots, A_{N}$ which denotes the plan of the trip during these $N$ days; however, the plan is not completed yet. For each valid $i$, they want to visit the place $A_{i}$ on the $i$-th day, but if $A_{i} = -1$, then they haven't decided which place to visit on that day.

Chef and his friend do not want to visit the same place two days in a row, but they can visit a place more than once in total. It is not necessary to visit all the places during the trip. Determine whether it is possible to complete the plan in such a way that this condition is satisfied. If it is possible, find one way of completing the plan.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a line containing the string "YES" if it's possible the complete the plan or "NO" otherwise.

If it's possible to complete the plan, print a second line containing $N$ space-separated integers denoting the sequence $A_{1}, A_{2}, \ldots, A_{N}$ after completing the plan. If there is more than one solution, you may print any one.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 10^{5}$
$2 ≤ K ≤ 10^{5}$
$1 ≤ A_{i} ≤ K$ or $A_{i} = -1$ for each valid $i$
if $A_{i} \neq -1$ and $A_{i+1} \neq -1$, then $A_{i} \neq A_{i+1}$, for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (30 points):
$N ≤ 1,000$
$K = 2$
the sum of $N$ over all test cases does not exceed $10,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
5
5 3
-1 -1 -1 -1 -1
4 5
1 2 3 5
3 2
1 -1 2
4 2
1 -1 -1 1
6 4
-1 -1 4 -1 2 -1
----- Sample Output 1 ------ 
YES
1 2 1 2 1
YES
1 2 3 5
NO
NO
YES
1 2 4 1 2 1

Source: codechef | Difficulty: HARD
Tags: Constructive algorithms


Solutions:
def func(arr, l, r, k):
	n = len(arr)
	if l == -1 and r == n:
		if k <= 1 and n != k:
			return False
		for i in range(n):
			arr[i] = i % 2 + 1
		return True
	elif r == n:
		tbf = r - l - 1
		if k <= 1 and tbf != 0:
			return False
		for i in range(l + 1, n):
			if (i - l) % 2 != 0:
				arr[i] = 1 if arr[l] != 1 else 2
			else:
				arr[i] = arr[l]
		return True
	elif l == -1:
		tbf = r
		if k <= 1 and tbf != 0:
			return False
		for i in range(r - 1, -1, -1):
			if (r - i) % 2 != 0:
				arr[i] = 1 if arr[r] != 1 else 2
			else:
				arr[i] = arr[r]
		return True
	else:
		if r == l + 1 and arr[l] == arr[r]:
			return False
		if arr[l] == arr[r]:
			tbf = r - l - 1
			if tbf != 0 and k == 1:
				return False
			arr[l + 1] = 1 if arr[l] != 1 else 2
			return func(arr, l + 1, r, k)
		else:
			tbf = r - l - 1
			if tbf % 2 != 0 and k <= 2:
				return False
			for i in range(l + 1, r):
				arr[i] = arr[l] if (i - l) % 2 == 0 else arr[r]
			if arr[r - 1] == arr[r]:
				for x in [1, 2, 3]:
					if arr[l] != x and arr[r] != x:
						arr[r - 1] = x
						break
			return True
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	l = -1
	flag = 0
	for r in range(n):
		if arr[r] != -1:
			bla = func(arr, l, r, k)
			if bla == False:
				flag = 1
				break
			l = r
	bla = func(arr, l, r + 1, k)
	if bla == False:
		flag = 1
	if flag == 1:
		print('NO')
	else:
		print('YES')
		ans = ''
		for x in arr:
			ans += str(x) + ' '
		print(ans)


def solution():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	if K == 2:
		even1 = False
		odd1 = False
		even2 = False
		odd2 = False
		for i in range(N):
			if A[i] == 1:
				if i % 2 == 0:
					even1 = True
				else:
					odd1 = True
			elif A[i] == 2:
				if i % 2 == 0:
					even2 = True
				else:
					odd2 = True
		if even1 and odd1 or (even2 and odd2) or (even1 and even2) or (odd1 and odd2):
			print('NO')
		elif even1 or odd2:
			print('YES')
			ans = [str(i % 2 + 1) for i in range(N)]
			print(' '.join(ans))
		else:
			print('YES')
			ans = [str(2 - i % 2) for i in range(N)]
			print(' '.join(ans))
		return
	print('YES')
	for i in range(N):
		if A[i] != -1:
			continue
		num = 1
		if i > 0 and A[i - 1] == num or (i < N - 1 and A[i + 1] == num):
			num += 1
		if i > 0 and A[i - 1] == num or (i < N - 1 and A[i + 1] == num):
			num += 1
		A[i] = num
	print(' '.join(map(str, A)))
T = int(input())
while T > 0:
	T = T - 1
	solution()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, k) = mp()
	l = li()
	if k == 2:
		seq1 = [1, 2] * n
		seq2 = [2, 1] * n
		flag1 = flag2 = 0
		for j in range(n):
			if l[j] != -1 and l[j] != seq1[j]:
				flag1 = 1
				break
		for j in range(n):
			if l[j] != -1 and l[j] != seq2[j]:
				flag2 = 1
				break
		if flag1 == 1 and flag2 == 1:
			pr('NO')
		elif flag1 == 0:
			pr('YES')
			print(*seq1[:n])
		else:
			pr('YES')
			print(*seq2[:n])
		return
	for i in range(n):
		if l[i] == -1:
			for j in range(1, k + 1):
				if i == 0:
					if l[i + 1] != j:
						l[i] = j
						break
				elif i == n - 1:
					if l[i - 1] != j:
						l[i] = j
						break
				elif l[i + 1] != j and l[i - 1] != j:
					l[i] = j
					break
			else:
				pr('NO')
				return
	pr('YES')
	print(*l)
for _ in range(inp()):
	solve()


for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = [0]
	a.extend(list(map(int, input().split())))
	a.append(0)
	check = [i for i in range(1, k + 1)]
	flag = True
	if k == 2:
		(i, c) = (1, 0)
		while a[i] == -1 and i < len(a) - 1:
			c += 1
			i += 1
		if i != len(a) - 1:
			if c & 1 == 0:
				a[1] = a[i]
			else:
				a[1] = 1 * (a[i] == 2) + 2 * (a[i] == 1)
	for i in range(1, len(a) - 1):
		if a[i] == -1:
			val = 0
			while val < len(check):
				if check[val] != a[i - 1] and check[val] != a[i + 1]:
					a[i] = check[val]
					break
				val += 1
			if val == len(check):
				flag = False
				break
	if flag == True:
		print('YES')
		print(*a[1:n + 1])
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	if k == 2:
		t1 = []
		for i in range(0, n, 2):
			t1.append(1)
			t1.append(2)
		t2 = []
		for i in range(0, n, 2):
			t2.append(2)
			t2.append(1)
		c1 = 0
		c2 = 0
		for i in range(n):
			if li[i] == -1:
				c1 += 1
				c2 += 1
			elif li[i] == t1[i]:
				c1 += 1
			elif li[i] == t2[i]:
				c2 += 1
		if c1 == n:
			print('YES')
			for i in range(n):
				print(t1[i], end=' ')
			print(' ')
		elif c2 == n:
			print('YES')
			for i in range(n):
				print(t2[i], end=' ')
			print(' ')
		else:
			print('NO')
	else:
		for i in range(n):
			if i == 0 and li[i] == -1:
				if li[i + 1] != 1:
					li[i] = 1
				else:
					li[i] = 2
			elif i == n - 1 and li[i] == -1:
				if li[i - 1] != 1:
					li[i] = 1
				else:
					li[i] = 2
			elif li[i] == -1:
				if li[i - 1] != 1 and li[i + 1] != 1:
					li[i] = 1
				elif li[i - 1] != 2 and li[i + 1] != 2:
					li[i] = 2
				else:
					li[i] = 3
		print('YES')
		for i in range(n):
			print(li[i], end=' ')
		print(' ')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if a.count(-1) == n:
		print('YES')
		check = 1
		for i in range(n):
			if check == 1:
				print(1, end=' ')
				check *= -1
			else:
				print(2, end=' ')
				check *= -1
		print()
	elif -1 in a:
		if k == 2:
			flag = True
			if 1 in a:
				find = a.index(1)
				comp = find % 2
				for i in range(0, n):
					if i % 2 == comp:
						if a[i] == 2:
							print('NO')
							flag = False
							break
						else:
							a[i] = 1
					elif a[i] == 1:
						print('NO')
						flag = False
						break
					else:
						a[i] = 2
			else:
				find = a.index(2)
				comp = find % 2
				for i in range(0, n):
					if i % 2 == comp:
						if a[i] == 1:
							print('NO')
							flag = False
							break
						else:
							a[i] = 2
					elif a[i] == 2:
						print('NO')
						flag = False
						break
					else:
						a[i] = 1
			if flag:
				print('YES')
				for i in range(n):
					print(a[i], end=' ')
				print()
		else:
			for i in range(n):
				if a[i] == -1:
					if i == 0:
						if a[i + 1] == 1:
							a[i] = 2
						else:
							a[i] = 1
					elif i == n - 1:
						if a[i - 1] == 1:
							a[i] = 2
						else:
							a[i] = 1
					elif a[i - 1] != 1 and a[i + 1] != 1:
						a[i] = 1
					elif a[i - 1] != 2 and a[i + 1] != 2:
						a[i] = 2
					else:
						a[i] = 3
			print('YES')
			for i in range(n):
				print(a[i], end=' ')
			print()
	else:
		print('YES')
		for i in range(n):
			print(a[i], end=' ')
		print()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(range(1, k + 1))
	res = ''
	if n == 1:
		print('YES')
		print(1)
		continue
	if k > 2:
		print('YES')
		for i in range(n):
			if a[i] == -1:
				if i == 0:
					if a[1] == 1:
						a[i] = 2
					else:
						a[i] = 1
				elif i == n - 1:
					if a[n - 2] == 1:
						a[i] = 2
					else:
						a[i] = 1
				elif a[i - 1] == 1 or a[i + 1] == 1:
					if a[i - 1] == 2 or a[i + 1] == 2:
						a[i] = 3
					else:
						a[i] = 2
				else:
					a[i] = 1
			print(a[i], end=' ')
		print()
	else:
		t = 0
		if n % 2 == 0:
			t1 = '12' * (n // 2)
			t2 = '21' * (n // 2)
		else:
			t1 = ('12' * ((n + 1) // 2))[:-1]
			t2 = ('21' * ((n + 1) // 2))[:-1]
		for f in range(n):
			if t == 0:
				if a[f] != -1:
					if a[f] == int(t1[f]):
						t = 1
					else:
						t = 2
			elif a[f] != -1:
				if t == 1:
					if a[f] != int(t1[f]):
						print('NO')
						break
				elif a[f] != int(t2[f]):
					print('NO')
					break
			else:
				pass
		else:
			if t == 1 or t == 0:
				res = list(t1)
				res = ' '.join(res)
			if t == 2:
				res = list(t2)
				res = ' '.join(res)
			print('YES')
			print(res)


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	res = []
	flag1 = 0
	flag2 = 0
	if k == 2:
		seq1 = [1, 2] * n
		seq2 = [2, 1] * n
		for j in range(n):
			if arr[j] != -1 and arr[j] != seq1[j]:
				flag1 = 1
				break
		for j in range(n):
			if arr[j] != -1 and arr[j] != seq2[j]:
				flag2 = 1
				break
		if flag1 == 1 and flag2 == 1:
			print('NO')
		elif flag1 == 0:
			print('YES')
			print(' '.join([str(x) for x in seq1[:n]]))
		else:
			print('YES')
			print(' '.join([str(x) for x in seq2[:n]]))
	else:
		res = []
		for j in range(n):
			tmp = [1, 2, 3]
			if arr[j] == -1:
				if j - 1 >= 0 and arr[j - 1] in tmp:
					tmp.remove(arr[j - 1])
				if j + 1 < n and arr[j + 1] in tmp:
					tmp.remove(arr[j + 1])
				res.append(tmp[0])
				arr[j] = tmp[0]
			else:
				res.append(arr[j])
		print('YES')
		print(' '.join([str(x) for x in res]))


def pri(A, B):
	var = []
	t = ''
	for i in range(len(A)):
		if A[i] == -1:
			val = 0
			for j in range(len(B)):
				if i == 0 and A[i + 1] != B[j]:
					A[i] = B[j]
					val = 1
					break
				elif i == len(A) - 1 and A[i - 1] != B[j]:
					A[i] = B[j]
					val = 1
					break
				elif A[i - 1] != B[j] and A[i + 1] != B[j]:
					A[i] = B[j]
					val = 1
					break
			if val == 0:
				var.append('NO')
				t = 'NO'
				break
	if t == '':
		var.append('YES')
		var.append([*A])
	return var
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	C = list(A)
	B = []
	for i in range(1, K + 1):
		B.append(i)
	var = pri(A, B)
	if var[0] == 'YES':
		print(var[0])
		print(*var[1])
	elif var[0] == 'NO' and K == 2:
		B = B[::-1]
		var = pri(C, B)
		if len(var) == 1:
			print(var[0])
		else:
			print(var[0])
			print(*var[1])
	else:
		print(var[0])


t = int(input())
for ii in range(t):
	(n, k) = map(int, input().split())
	a = []
	a = list(map(int, input().split()))
	if n == 1:
		print('YES')
		if a[0] == -1:
			a[0] = 1
		print(a[0])
		continue
	if k == 2:
		flag = 0
		x = 0
		y = 0
		inn = 0
		for j in range(n):
			if a[j] != -1:
				x = a[j]
				y = j
				inn = 1
				break
		if x == 1 and j % 2 == 0 or (x == 2 and y % 2 != 0):
			for m in range(n):
				if a[m] != -1:
					if m % 2 == 0 and a[m] != 1 or (m % 2 != 0 and a[m] != 2):
						flag = 1
						break
		elif x == 1 and j % 2 != 0 or (x == 2 and y % 2 == 0):
			for m in range(n):
				if a[m] != -1:
					if m % 2 == 0 and a[m] != 2 or (m % 2 != 0 and a[m] != 1):
						flag = 1
						break
		if flag == 1:
			print('NO')
		elif inn == 0:
			for m in range(n):
				if m % 2 == 0 and a[m] == -1:
					a[m] = 1
				else:
					a[m] = 2
			print('YES')
			print(*a)
		else:
			if x == 1 and y % 2 == 0 or (x == 2 and y % 2 != 0):
				for m in range(n):
					if m % 2 == 0 and a[m] == -1:
						a[m] = 1
					elif m % 2 != 0 and a[m] == -1:
						a[m] = 2
			elif x == 2 and y % 2 == 0 or (x == 1 and y % 2 != 0):
				for m in range(n):
					if m % 2 == 0 and a[m] == -1:
						a[m] = 2
					elif m % 2 != 0 and a[m] == -1:
						a[m] = 1
			print('YES')
			print(*a)
	if k >= 3:
		for i in range(n):
			if a[i] == -1 and i == 0:
				if a[i + 1] != 1 or a[i + 1] == -1:
					a[i] = 1
				elif a[i + 1] != 2 or a[i + 1] == -1:
					a[i] = 2
			elif a[i] == -1 and i == n - 1:
				if a[i - 1] != 2:
					a[i] = 2
				elif a[i - 1] != 1:
					a[i] = 1
			elif a[i] == -1:
				if a[i - 1] != 1 and a[i + 1] != 1:
					a[i] = 1
				elif a[i - 1] != 2 and a[i + 1] != 2:
					a[i] = 2
				elif a[i - 1] != 2 and a[i - 1] != 1 and (a[i + 1] != 2):
					a[i] = 2
				elif a[i - 1] != 2 and a[i - 1] != 1 and (a[i + 1] != 1):
					a[i] = 1
				elif a[i - 1] == 1 and a[i + 1] == 2 or (a[i - 1] == 2 and a[i + 1] == 1):
					a[i] = 3
		print('YES')
		print(*a)


def take(a):
	c = 0
	if a == 0:
		b = 0
	else:
		b = fek[a - 1]
	if a == n - 1:
		c = 0
	elif fek[a + 1] == -1:
		c = 0
	else:
		c = fek[a + 1]
	for i in v:
		if i != b and i != c:
			return i
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	fek = [int(o) for o in input().split()]
	fekarr = fek[:]
	fekarr.sort()
	v = []
	fekarr[0] = 1
	if k != 2:
		fekarr = fekarr[::-1]
		for i in range(1, k + 1):
			v.append(i)
			fekarr[0] = 1
		for i in range(n):
			if fek[i] == -1:
				fekarr[0] = 1
				fek[i] = take(i)
		uyff = 0
		fekarr[0] = 1
		for i in range(n - 1):
			if fek[i] == fek[i + 1]:
				fekarr[0] = 1
				uyff = 1
				break
		if uyff == 1:
			fekarr[0] = 1
			print('NO')
		else:
			print('YES')
			fekarr[0] = 1
			print(*fek)
	elif k == 2:
		x = 0
		fek1 = [0] * n
		fekarr[0] = 1
		fek2 = [0] * n
		fekarr[0] = 1
		for i in range(n):
			if x == 0:
				fekarr[0] = 1
				fek1[i] = 1
			else:
				fekarr[0] = 1
				fek1[i] = 2
			x ^= 1
		uihiu = 0
		fekarr[0] = 1
		opop = 0
		for i in range(n):
			if fek[i] != -1 and fek[i] != fek1[i]:
				fekarr[0] = 1
				uihiu += 1
				break
		x = 0
		for i in range(n):
			if x == 0:
				fekarr[0] = 1
				fek2[i] = 2
			else:
				fek2[i] = 1
				fekarr[0] = 1
			x = x ^ 1
			fekarr[0] = 1
		for i in range(n):
			if fek[i] != -1 and fek[i] != fek2[i]:
				opop += 1
				fekarr[0] = 1
				break
		if uihiu == 1 and opop == 1:
			fekarr[0] = 1
			print('NO')
			fekarr[0] = 1
		elif uihiu == 0:
			print('YES')
			fekarr[0] = 1
			print(*fek1)
		else:
			fekarr[0] = 1
			print('YES')
			fekarr[0] = 1
			print(*fek2)


T = int(input())
for t in range(T):
	(N, K) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if K == 2:
		res = True
		curind = 0
		item = 1
		while curind < N and a[curind] == -1:
			a[curind] = item
			if item == 1:
				item = 2
			else:
				item = 1
			curind += 1
		if curind != 0 and curind < N and (a[curind] == a[curind - 1]):
			a.insert(curind, item)
			a.pop(0)
		for i in range(curind + 1, N):
			if a[i] == -1:
				if a[i - 1] == 1:
					a[i] = 2
				else:
					a[i] = 1
				if i != N - 1 and a[i] == a[i + 1]:
					res = False
					break
		if res:
			print('YES')
			print(' '.join(list(map(str, a))))
		else:
			print('NO')
	else:
		for i in range(N):
			if a[i] == -1:
				ans = 1
				if i != 0 and a[i - 1] == ans or (i != N - 1 and a[i + 1] == ans):
					ans += 1
				if i != 0 and a[i - 1] == ans or (i != N - 1 and a[i + 1] == ans):
					ans += 1
				a[i] = ans
		print('YES')
		print(' '.join(list(map(str, a))))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k > 2:
		flag = True
		for i in range(1, n - 1):
			if a[i] == -1:
				for j in range(1, k + 1):
					if j != a[i - 1] and j != a[i + 1]:
						a[i] = j
						break
		if a[0] == -1:
			for j in range(1, k + 1):
				if j != a[1]:
					a[0] = j
					break
		if a[-1] == -1:
			for j in range(1, k + 1):
				if j != a[-2]:
					a[-1] = j
					break
		for i in range(n - 1):
			if a[i] == a[i + 1]:
				print('NO')
				flag = False
				break
		if flag:
			print('YES')
			print(*a, sep=' ')
	elif a[0] == -1:
		flag1 = True
		flag2 = True
		l = [1]
		for i in range(1, n):
			if a[i] == -1:
				if l[i - 1] == 1:
					l.append(2)
				else:
					l.append(1)
			else:
				l.append(a[i])
		l1 = [2]
		for i in range(1, n):
			if a[i] == -1:
				if l1[i - 1] == 1:
					l1.append(2)
				else:
					l1.append(1)
			else:
				l1.append(a[i])
		for i in range(n - 1):
			if l[i] == l[i + 1]:
				flag1 = False
				break
		for i in range(n - 1):
			if l1[i] == l1[i + 1]:
				flag2 = False
				break
		if flag1:
			print('YES')
			print(*l, sep=' ')
		elif flag2:
			print('YES')
			print(*l1, sep=' ')
		else:
			print('NO')
	else:
		flag = True
		l = [a[0]]
		for i in range(1, n):
			if a[i] == -1:
				if l[i - 1] == 1:
					l.append(2)
				else:
					l.append(1)
			else:
				l.append(a[i])
		for i in range(n - 1):
			if l[i] == l[i + 1]:
				print('NO')
				flag = False
				break
		if flag:
			print('YES')
			print(*l, sep=' ')


a = int(input())
for _ in range(a):
	(n, k) = map(int, input().split())
	tp = input().split()
	if n == 1:
		print('YES')
		if tp[0] == '-1':
			tp[0] = '1'
		print(tp[0])
		continue
	if k == 2:
		if tp[0] == '-1':
			for i in range(n):
				if tp[i] != '-1':
					break
			if tp[i] != '-1':
				e = tp[i]
				if e == '1':
					if i % 2 == 1:
						tp[0] = '2'
					else:
						tp[0] = '1'
				elif i % 2 == 0:
					tp[0] = '2'
				else:
					tp[0] = '1'
			else:
				tp[0] = '1'
		for i in range(1, n - 1):
			if tp[i] == '-1':
				if tp[i - 1] == tp[i + 1] or tp[i + 1] == '-1':
					if tp[i - 1] == '1':
						tp[i] = '2'
					else:
						tp[i] = '1'
				else:
					print('NO')
					break
		else:
			i += 1
			print('YES')
			if tp[i] == '-1':
				if tp[i - 1] == '1':
					tp[i] = '2'
				else:
					tp[i] = '1'
			print(' '.join(tp))
	else:
		if tp[0] == '-1':
			if tp[1] == '1':
				tp[0] = '2'
			else:
				tp[0] = '1'
		for i in range(1, n - 1):
			if tp[i] == '-1':
				if tp[i - 1] == '1' or tp[i + 1] == '1':
					if tp[i - 1] == '2' or tp[i + 1] == '2':
						tp[i] = '3'
					else:
						tp[i] = '2'
				else:
					tp[i] = '1'
		else:
			i += 1
			if tp[i] == '-1':
				if tp[i - 1] == '1':
					tp[i] = '2'
				else:
					tp[i] = '1'
			print('YES')
			print(' '.join(tp))


t = int(input())
while t > 0:
	f = 0
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	b = input().split()
	b = [int(x) for x in b]
	c = [1] + b
	for i in range(1, len(c)):
		if c[i] == -1:
			if c[i - 1] == 1:
				c[i] = 2
			else:
				c[i] = 1
		if i + 1 != len(c):
			if c[i + 1] == c[i]:
				f = 1
				c[i] = 3
				if c[i - 1] == 3:
					if c[i + 1] == 1:
						c[i] = 2
					else:
						c[i] = 1
	if k == 2 and f == 1:
		c = [2] + b
		f = 0
		for i in range(1, len(c)):
			if c[i] == -1:
				if c[i - 1] == 1:
					c[i] = 2
				else:
					c[i] = 1
			if i + 1 != len(c):
				if c[i + 1] == c[i]:
					f = 1
		if f == 0:
			print('YES')
			c = ' '.join((str(c[x]) for x in range(1, len(c))))
			print(c)
		else:
			print('NO')
	else:
		print('YES')
		c = ' '.join((str(c[x]) for x in range(1, len(c))))
		print(c)
	t -= 1


for _ in range(int(input().strip())):
	(n, k) = map(int, input().strip().split())
	l = list(map(int, input().strip().split()))
	if n == 1:
		print('YES')
		if l[0] == -1:
			print(1)
		else:
			print(*l)
		continue
	if k == 2:
		arr = [str(i) for i in l]
		if arr[0] == '-1':
			for i in range(n):
				if arr[i] != '-1':
					break
			if arr[i] != '-1':
				e = arr[i]
				if e == '1':
					if i % 2 == 1:
						arr[0] = '2'
					else:
						arr[0] = '1'
				elif i % 2 == 0:
					arr[0] = '2'
				else:
					arr[0] = '1'
			else:
				arr[0] = '1'
		for i in range(1, n - 1):
			if arr[i] == '-1':
				if arr[i - 1] == arr[i + 1] or arr[i + 1] == '-1':
					if arr[i - 1] == '1':
						arr[i] = '2'
					else:
						arr[i] = '1'
				else:
					print('NO')
					break
		else:
			i += 1
			print('YES')
			if arr[i] == '-1':
				if arr[i - 1] == '1':
					arr[i] = '2'
				else:
					arr[i] = '1'
			print(*arr)
		continue
	s = set()
	flag1 = False
	for i in range(1, k + 1):
		s.add(i)
	for i in range(n - 1):
		if l[i] != l[i + 1] and l[i] != -1:
			continue
		else:
			flag = False
			for j in s:
				if i == 0:
					if j != l[i + 1]:
						l[i] = j
						flag = True
						break
				elif j != l[i - 1] and j != l[i + 1]:
					l[i] = j
					flag = True
					break
			if not flag:
				flag1 = True
				print('NO')
				break
	if l[-1] == -1:
		for j in s:
			if j != l[-2]:
				l[-1] = j
				break
	if not flag1:
		print('YES')
		print(*l)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	an = [int(x) for x in input().split()]
	an.insert(0, 0)
	an.append(0)
	flag = 1
	if k > 2:
		for i in range(1, len(an) - 1):
			if an[i] == -1:
				for v in range(1, k + 1):
					if an[i - 1] != v and an[i + 1] != v:
						an[i] = v
						break
				else:
					flag = 0
		if flag == 1:
			print('YES')
			for i in range(1, len(an) - 1):
				print(an[i], end=' ')
			print()
		else:
			print('NO')
	else:
		f = an.index(1) if 1 in an else -2
		l = an.index(2) if 2 in an else -2
		m = an.index(-1) if -1 in an else -2
		if f != -2:
			k = f
			if k % 2 == 0:
				for i in range(2, len(an) - 1, 2):
					if an[i] == 2:
						flag = 0
						break
					else:
						an[i] = 1
				for j in range(1, len(an) - 1, 2):
					if an[j] == 1:
						flag = 0
						break
					else:
						an[j] = 2
			else:
				for i in range(1, len(an) - 1, 2):
					if an[i] == 2:
						flag = 0
						break
					else:
						an[i] = 1
				for j in range(2, len(an) - 1, 2):
					if an[j] == 1:
						flag = 0
						break
					else:
						an[j] = 2
			if flag == 1:
				print('YES')
				for i in range(1, len(an) - 1):
					print(an[i], end=' ')
				print()
			else:
				print('NO')
		elif l != -2:
			k = l
			if k % 2 == 0:
				for i in range(2, len(an) - 1, 2):
					if an[i] == 1:
						flag = 0
						break
					else:
						an[i] = 2
				for j in range(1, len(an) - 1, 2):
					if an[j] == 2:
						flag = 0
						break
					else:
						an[j] = 1
			else:
				for i in range(1, len(an) - 1, 2):
					if an[i] == 1:
						flag = 0
						break
					else:
						an[i] = 2
				for j in range(2, len(an) - 1, 2):
					if an[j] == 2:
						flag = 0
						break
					else:
						an[j] = 1
			if flag == 1:
				print('YES')
				for i in range(1, len(an) - 1):
					print(an[i], end=' ')
				print()
			else:
				print('NO')
		else:
			print('YES')
			for i in range(1, len(an) - 1):
				if i % 2 == 0:
					print(1, end=' ')
				else:
					print(2, end=' ')
			print()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	a.append(0)
	ch = 1
	if k != 2:
		for i in range(1, len(a) - 1):
			if a[i] == -1:
				for j in range(1, k + 1):
					if a[i - 1] != j and a[i + 1] != j:
						a[i] = j
						break
				else:
					ch = 0
	elif k == 2:
		b = list(a)
		c = list(a)
		chb = 1
		for i in range(1, len(b) - 1):
			if b[i] == -1:
				for j in range(1, k + 1):
					if b[i - 1] != j and b[i + 1] != j:
						b[i] = j
						break
				else:
					chb = 0
		chc = 1
		for i in range(1, len(c) - 1):
			if c[i] == -1:
				for j in range(k, 0, -1):
					if c[i - 1] != j and c[i + 1] != j:
						c[i] = j
						break
				else:
					chc = 0
		if chc == 1 or chb == 1:
			ch = 1
			if chc == 1:
				a = list(c)
			else:
				a = list(b)
		else:
			ch = 0
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			ch = 0
	if ch == 1:
		print('YES')
		print(*a[1:len(a) - 1])
	else:
		print('NO')


T = int(input())
for x in range(T):
	(N, K) = [int(k) for k in input().split()]
	A = [int(k) for k in input().split()]
	plan = True
	if K == 2:
		gap = 0
		neg = False
		preassign = False
		prev = -2
		for ele in A:
			if ele < 0:
				neg = True
				gap += 1
			else:
				if neg:
					post = ele
					if preassign and post == pre:
						if gap % 2 == 0:
							plan = False
							break
					if preassign and post != pre:
						if gap % 2 != 0:
							plan = False
							break
					preassign = False
					neg = False
				if not neg:
					pre = ele
					preassign = True
				gap = 0
		if plan:
			print('YES')
			pos = -1
			done = 0
			case = False
			for i in range(N):
				if i == 0 and A[i] == -1:
					case = True
				if case and done == 0:
					if pos == -1 and A[i] == -1:
						i += 1
						continue
					if A[i] != -1:
						pos = i
						done = 1
						i += 1
						continue
				if A[i] == -1:
					if A[i - 1] == 1:
						A[i] = 2
					else:
						A[i] = 1
				i += 1
			if case:
				i = pos - 1
				if pos == -1:
					i = 0
					while i < N - 1:
						A[i] = 2
						A[i + 1] = 1
						i += 2
					if i == N - 1:
						A[i] = 2
						i += 1
					i = -1
				if i == 0:
					if A[pos] == 2:
						A[i] = 1
					else:
						A[i] = 2
					i -= 1
				while i > 0:
					if A[pos] == 1:
						A[i] = 2
						A[i - 1] = 1
						i -= 2
					else:
						A[i] = 1
						A[i - 1] = 2
						i -= 2
				if i == 0:
					if A[1] == 2:
						A[0] = 1
					else:
						A[0] = 2
					i -= 1
			for ele in A:
				print(ele, end=' ')
			print('')
		else:
			print('NO')
	else:
		if N == 1:
			if A[0] == -1:
				A[0] = 1
		else:
			s = [1, 2, 3]
			for i in range(N):
				if A[i] == -1:
					if i == 0:
						for ele in s:
							if A[i + 1] != ele:
								A[i] = ele
								break
					elif i == N - 1:
						for ele in s:
							if A[i - 1] != ele:
								A[i] = ele
								break
					else:
						for ele in s:
							if A[i - 1] != ele and A[i + 1] != ele:
								A[i] = ele
								break
		prev = -2
		prin = True
		for ele in A:
			if ele == prev:
				print('NO')
				prin = False
				break
			prev = ele
		print('YES')
		if prin:
			for ele in A:
				print(ele, end=' ')
			print('')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if k <= 2:
		l1 = list(l)
		l2 = list(l)
		for i in range(n):
			if l1[i] == -1:
				for j in range(1, k + 1):
					try:
						if l1[i - 1] != j and l1[i + 1] != j:
							l1[i] = j
							break
					except:
						pass
		if l1[n - 1] == -1:
			for i in range(1, k + 1):
				if l1[n - 2] != i:
					l1[n - 1] = i
					break
		for i in range(n):
			if l2[i] == -1:
				for j in range(k, 0, -1):
					try:
						if l2[i - 1] != j and l2[i + 1] != j:
							l2[i] = j
							break
					except:
						pass
		if l2[n - 1] == -1:
			for i in range(k, 0, -1):
				if l2[n - 2] != i:
					l2[n - 1] = i
					break
		if -1 in l1 and -1 in l2:
			print('NO')
		else:
			print('YES')
			if -1 in l1:
				print(*l2)
			else:
				print(*l1)
	else:
		for i in range(n):
			if l[i] == -1:
				for j in range(1, k + 1):
					try:
						if l[i - 1] != j and l[i + 1] != j:
							l[i] = j
							break
					except:
						pass
		if l[n - 1] == -1:
			for i in range(1, k + 1):
				if l[n - 2] != i:
					l[n - 1] = i
					break
		if -1 in l:
			print('NO')
		else:
			print('YES')
			print(*l)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if k > 2 and n > 1:
		print('YES')
		for i in range(n - 1):
			if l[i] == -1:
				if l[i - 1] != 1 and l[i + 1] != 1:
					l[i] = 1
				elif l[i - 1] != 2 and l[i + 1] != 2:
					l[i] = 2
				else:
					l[i] = 3
		if l[-1] == -1:
			if l[-2] != 1:
				l[-1] = 1
			else:
				l[-1] = 2
		for i in l:
			print(i, end=' ')
		print()
	elif n == 1:
		print('YES')
		if l[0] == -1:
			print(1)
		else:
			print(l[0])
	else:
		flag1 = flag2 = 1
		for i in range(n):
			if i % 2:
				if l[i] not in [-1, 1]:
					flag1 = 0
			elif l[i] not in [-1, 2]:
				flag1 = 0
		for i in range(n):
			if i % 2:
				if l[i] not in [-1, 2]:
					flag2 = 0
			elif l[i] not in [-1, 1]:
				flag2 = 0
		if flag1:
			l = list((2 - i % 2 for i in range(n)))
			print('YES')
			for i in l:
				print(i, end=' ')
			print()
		elif flag2:
			l = list((i % 2 + 1 for i in range(n)))
			print('YES')
			for i in l:
				print(i, end=' ')
			print()
		else:
			print('NO')


for case in range(int(input())):
	(n, k) = map(int, input().split())
	arr = input().split()
	if n == 1:
		print('YES')
		if arr[0] == '-1':
			arr[0] = '1'
		print(arr[0])
		continue
	if k == 2:
		if arr[0] == '-1':
			for i in range(n):
				if arr[i] != '-1':
					break
			if arr[i] != '-1':
				e = arr[i]
				if e == '1':
					if i % 2 == 1:
						arr[0] = '2'
					else:
						arr[0] = '1'
				elif i % 2 == 0:
					arr[0] = '2'
				else:
					arr[0] = '1'
			else:
				arr[0] = '1'
		for i in range(1, n - 1):
			if arr[i] == '-1':
				if arr[i - 1] == arr[i + 1] or arr[i + 1] == '-1':
					if arr[i - 1] == '1':
						arr[i] = '2'
					else:
						arr[i] = '1'
				else:
					print('NO')
					break
		else:
			i += 1
			print('YES')
			if arr[i] == '-1':
				if arr[i - 1] == '1':
					arr[i] = '2'
				else:
					arr[i] = '1'
			print(*arr, sep=' ')
	else:
		if arr[0] == '-1':
			if arr[1] == '1':
				arr[0] = '2'
			else:
				arr[0] = '1'
		for i in range(1, n - 1):
			if arr[i] == '-1':
				if arr[i - 1] == '1' or arr[i + 1] == '1':
					if arr[i - 1] == '2' or arr[i + 1] == '2':
						arr[i] = '3'
					else:
						arr[i] = '2'
				else:
					arr[i] = '1'
		else:
			i += 1
			if arr[i] == '-1':
				if arr[i - 1] == '1':
					arr[i] = '2'
				else:
					arr[i] = '1'
			print('YES')
			print(*arr, sep=' ')


t = int(input())
while t > 0:
	t -= 1
	f = 0
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if k == 1:
		print('YES')
		if a[0] == -1:
			print('1')
		else:
			print(a[0])
	elif k >= 3:
		for i in range(1, n - 1):
			if l[i] == -1 and l[i - 1] != 1 and (l[i + 1] != 1):
				l[i] = 1
			elif l[i] == -1 and l[i - 1] != 2 and (l[i + 1] != 2):
				l[i] = 2
			elif l[i] == -1 and l[i - 1] != 3 and (l[i + 1] != 3):
				l[i] = 3
		if l[0] == -1 and l[1] != 1:
			l[0] = 1
		elif l[0] == -1 and l[1] != 2:
			l[0] = 2
		if l[n - 1] == -1 and l[n - 2] != 1:
			l[n - 1] = 1
		elif l[n - 1] == -1 and l[n - 2] != 2:
			l[n - 1] = 2
		for i in range(0, n - 1):
			if l[i] == l[i + 1]:
				f = 1
				break
		if f == 0:
			print('YES')
			print(' '.join(map(str, l)))
		else:
			print('NO')
	elif k == 2:
		x = []
		x = l[:]
		for i in range(0, n):
			if l[i] == -1:
				if i % 2 == 0:
					l[i] = 1
				else:
					l[i] = 2
		for i in range(0, n - 1):
			if l[i] == l[i + 1]:
				f = 1
				break
		if f == 1:
			for i in range(0, n):
				if x[i] == -1:
					if i % 2 == 0:
						x[i] = 2
					else:
						x[i] = 1
			for i in range(0, n - 1):
				if x[i] == x[i + 1]:
					f = 2
					break
		if f == 0:
			print('YES')
			print(' '.join(map(str, l)))
		elif f == 1:
			print('YES')
			print(' '.join(map(str, x)))
		else:
			print('NO')


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	value = 1
	if len(arr) == 1:
		if a[0] != -1:
			print('YES')
			print(a[i])
		else:
			print('1')
			print('YES')
		continue
	if len(arr) == 2:
		for i in range(len(arr)):
			if arr[i] != -1:
				continue
			elif i == 0:
				while value <= k:
					if value != arr[i + 1]:
						arr[i] = value
						break
					else:
						value += 1
			else:
				while value <= k:
					if value != arr[i - 1]:
						arr[i] = value
						break
					else:
						value += 1
		if -1 in arr:
			print('NO')
		else:
			print('YES')
			print(*arr)
	elif len(arr) > 2 and k == 2:
		a1 = [0] * n
		a2 = [0] * n
		flag = 0
		for i in range(n):
			if i & 1:
				a1[i] = 1
				a2[i] = 2
			else:
				a1[i] = 2
				a2[i] = 1
		for i in range(n):
			if arr[i] != -1:
				if arr[i] != a1[i]:
					break
		else:
			print('YES')
			print(*a1, sep=' ')
			continue
		for i in range(n):
			if arr[i] != -1:
				if arr[i] != a2[i]:
					break
		else:
			print('YES')
			print(*a2, sep=' ')
			continue
		if flag == 0:
			print('NO')
	else:
		value = 1
		for j in range(0, n, 3):
			if j + 3 <= n:
				z = j + 3
			else:
				z = n
			for i in range(j, z, 1):
				if arr[i] != -1:
					continue
				elif i == 0:
					while value <= k:
						if value != arr[i + 1]:
							arr[i] = value
							value = 1
							break
						else:
							value += 1
				elif i == len(arr) - 1:
					while value <= k:
						if value != arr[i - 1]:
							arr[i] = value
							break
						else:
							value += 1
				else:
					while value <= k:
						if value != arr[i - 1] and value != arr[i + 1]:
							arr[i] = value
							value = 1
							break
						else:
							value += 1
		if -1 in arr:
			print('NO')
		else:
			print('YES')
			print(*arr, sep=' ')


tcase = int(input())
while tcase > 0:
	tcase -= 1
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	result = True
	if n == 1:
		if l[0] == -1:
			l[0] = 1
	elif k == 2:
		index = -1
		for i in range(n):
			if l[i] == 1 or l[i] == 2:
				index = i
				break
		if index == -1:
			for i in range(n):
				if i % 2 == 1:
					l[i] = 1
				else:
					l[i] = 2
		if l[index] == 1:
			if index % 2 == 1:
				for i in range(n):
					if i % 2 == 1 and l[i] == 2:
						result = False
						break
					elif i % 2 == 1:
						l[i] = 1
					if i % 2 == 0 and l[i] == 1:
						result = False
						break
					elif i % 2 == 0:
						l[i] = 2
			if index % 2 == 0:
				for i in range(n):
					if i % 2 == 0 and l[i] == 2:
						result = False
						break
					elif i % 2 == 0:
						l[i] = 1
					if i % 2 == 1 and l[i] == 1:
						result = False
						break
					elif i % 2 == 1:
						l[i] = 2
		if l[index] == 2:
			if index % 2 == 0:
				for i in range(n):
					if i % 2 == 1 and l[i] == 2:
						result = False
						break
					elif i % 2 == 1:
						l[i] = 1
					if i % 2 == 0 and l[i] == 1:
						result = False
						break
					elif i % 2 == 0:
						l[i] = 2
			if index % 2 == 1:
				for i in range(n):
					if i % 2 == 0 and l[i] == 2:
						result = False
						break
					elif i % 2 == 0:
						l[i] = 1
					if i % 2 == 1 and l[i] == 1:
						result = False
						break
					elif i % 2 == 1:
						l[i] = 2
	else:
		for i in range(n):
			if i == 0 and l[i] == -1:
				for j in range(1, k + 1):
					if l[1] != j:
						l[i] = j
						break
				if l[i] == -1:
					result = False
					break
			elif i == n - 1 and l[i] == -1:
				for j in range(1, k + 1):
					if l[n - 2] != j:
						l[i] = j
						break
				if l[i] == -1:
					result = False
			elif l[i] == -1:
				for j in range(1, k + 1):
					if l[i - 1] != j and l[i + 1] != j:
						l[i] = j
						break
				if l[i] == -1:
					result = False
					break
	if result:
		print('YES')
		for i in l:
			print(i, end=' ')
		print()
	else:
		print('NO')


t = int(input())
for j in range(t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if n == 1:
		print('YES')
		if l[0] == -1:
			l[0] = 1
		print(l[0])
	elif k == 2:
		if l[0] == -1:
			for i in range(n):
				if l[i] != -1:
					break
			if l[i] != -1:
				if l[i] == 1:
					if i % 2 == 1:
						l[0] = 2
					else:
						l[0] = 1
				if l[i] == 2:
					if i % 2 == 1:
						l[0] = 1
					else:
						l[0] = 2
			else:
				l[0] = 1
		for i in range(n - 1):
			if l[i] == -1:
				if l[i - 1] == l[i + 1] or l[i + 1] == -1:
					x = l[i - 1]
					if x == 1:
						l[i] = 2
					else:
						l[i] = 1
				else:
					print('NO')
					break
		else:
			i += 1
			if l[i] == -1:
				e = l[i - 1]
				if e == 1:
					l[i] = 2
				else:
					l[i] = 1
			print('YES')
			print(*l)
	else:
		if l[0] == -1:
			if l[1] == 1:
				l[0] = 2
			else:
				l[0] = 1
		for i in range(n - 1):
			if l[i] == -1:
				if l[i - 1] == 1 or l[i + 1] == 1:
					if l[i - 1] == 2 or l[i + 1] == 2:
						l[i] = 3
					else:
						l[i] = 2
				else:
					l[i] = 1
		else:
			i += 1
			if l[i] == -1:
				if l[i - 1] == 1:
					l[i] = 2
				else:
					l[i] = 1
			print('YES')
			print(*l)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	if n == 1:
		print('YES')
		if p[0] == -1:
			p[0] = 1
		print(p[0])
		continue
	if k == 2:
		i = 0
		ans = True
		while i < len(p):
			if p[i] == -1:
				if i == 0:
					x = 0
					for j in p:
						x += 1
						if j != -1:
							break
					if j == 1:
						if x % 2 == 0:
							p[i] = 2
						else:
							p[i] = 1
					elif x % 2 == 0:
						p[i] = 1
					else:
						p[i] = 2
				elif i == len(p) - 1:
					if p[i - 1] == 2:
						p[i] = 1
					else:
						p[i] = 2
				elif p[i - 1] != p[i + 1] and p[i + 1] != -1:
					print('NO')
					ans = False
					break
				elif p[i - 1] == 2:
					p[i] = 1
				else:
					p[i] = 2
			i += 1
		if ans == True:
			print('YES')
			print(*p, sep=' ')
	else:
		print('YES')
		i = 0
		while i < len(p):
			if p[i] == -1:
				if i == 0:
					if p[i + 1] == 2:
						p[i] = 1
					else:
						p[i] = 2
				elif i == len(p) - 1:
					if p[i - 1] == 2:
						p[i] = 1
					else:
						p[i] = 2
				elif p[i - 1] == 1 or p[i + 1] == 1:
					if p[i - 1] == 2 or p[i + 1] == 2:
						p[i] = 3
					else:
						p[i] = 2
				else:
					p[i] = 1
			i += 1
		print(*p, sep=' ')


t = int(input())
for T in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	if n == 1:
		print('YES')
		if a[0] == -1:
			a[0] = 1
		print(a[0])
		continue
	if k == 2:
		if a[0] == -1:
			for i in range(n):
				if a[i] != -1:
					break
			if a[i] != -1:
				if a[i] == 1:
					if i % 2 == 1:
						a[0] = 2
					else:
						a[0] = 1
				elif i % 2 == 0:
					a[0] = 2
				else:
					a[0] = 1
			else:
				a[0] = 1
		for i in range(1, n - 1):
			if a[i] == -1:
				if a[i - 1] == a[i + 1] or a[i + 1] == -1:
					if a[i - 1] == 1:
						a[i] = 2
					else:
						a[i] = 1
				else:
					print('NO')
					break
		else:
			i += 1
			print('YES')
			if a[i] == -1:
				if a[i - 1] == 1:
					a[i] = 2
				else:
					a[i] = 1
			print(*a)
	else:
		if a[0] == -1:
			if a[1] == 1:
				a[0] = 2
			else:
				a[0] = 1
		for i in range(1, n - 1):
			if a[i] == -1:
				if a[i - 1] == 1 or a[i + 1] == 1:
					if a[i - 1] == 2 or a[i + 1] == 2:
						a[i] = 3
					else:
						a[i] = 2
				else:
					a[i] = 1
		else:
			i += 1
			if a[i] == -1:
				if a[i - 1] == 1:
					a[i] = 2
				else:
					a[i] = 1
			print('YES')
			print(*a)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr_c = arr.count(-1)
	if arr_c == n:
		print('YES')
		for i in range(n):
			if i % 2 == 0:
				print(1, end=' ')
			else:
				print(2, end=' ')
		print()
	elif arr_c == 0:
		print('YES')
		print(*arr)
	else:
		for i in range(0, n):
			if i == n - 1:
				if arr[i] == -1:
					if arr[i - 1] != 1:
						arr[i] = 1
						flag = 1
					else:
						arr[i] = 2
						flag = 1
			elif i == 0:
				if arr[0] == -1:
					if k == 2:
						for j in range(1, n):
							if arr[j] != -1:
								l = j
								break
					flag = 0
					if k == 2 and l % 2 == 0:
						if arr[l] == 1:
							arr[0] = 1
							flag = 1
						else:
							arr[0] = 2
							flag = 1
					elif k == 2 and l % 2 != 0:
						if arr[l] == 1:
							arr[0] = 2
							flag = 1
						else:
							arr[0] = 1
							flag = 1
					elif arr[1] == -1 and arr[2] != -1:
						arr[0] = arr[2]
						flag = 1
					else:
						for j in range(1, k + 1):
							if arr[i + 1] != j:
								arr[i] = j
								flag = 1
								break
					if flag == 0:
						print('NO')
						break
			elif arr[i] == -1:
				flag = 0
				if arr[i + 1] == -1:
					if i + 2 < n and arr[i + 2] != -1 and (arr[i - 1] != arr[i + 2]):
						arr[i] = arr[i + 2]
						flag = 1
					else:
						for j in range(1, k + 1):
							if arr[i - 1] != j and arr[i + 1] != j:
								arr[i] = j
								flag = 1
								break
				else:
					for j in range(1, k + 1):
						if arr[i - 1] != j and arr[i + 1] != j:
							arr[i] = j
							flag = 1
							break
				if flag == 0:
					print('NO')
					break
		if flag == 1:
			print('YES')
			print(*arr)
	t -= 1


from random import choice
l1 = []
l2 = []
for x in range(10 ** 5):
	if x % 2 == 0:
		l1.append('1')
		l2.append('2')
	else:
		l2.append('1')
		l1.append('2')
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(str, input().split()))
	bool = True
	c = 0
	if n == 1:
		print('YES')
		print('1')
		continue
	for x in range(n):
		if l1[x] == '1' and l[x] == '2':
			bool = False
			break
		if l1[x] == '2' and l[x] == '1':
			bool = False
			break
	if not bool:
		c = 1
		bool = True
		for x in range(n):
			if l2[x] == '2' and l[x] == '1':
				bool = False
				break
			if l2[x] == '1' and l[x] == '2':
				bool = False
				break
	if bool and k == 2:
		print('YES')
		if c == 0:
			print(' '.join(l1[:n]))
		if c == 1:
			print(' '.join(l2[:n]))
	elif k == 2:
		print('NO')
	else:
		for x in range(1, n - 1):
			if l[x - 1] == '-1':
				if l[x] == '1':
					l[x - 1] = '2'
				else:
					l[x - 1] = '1'
			if l[x] == '-1':
				if l[x - 1] == '2' and l[x + 1] == '3' or (l[x - 1] == '3' and l[x + 1] == '2'):
					l[x] = '1'
				elif l[x - 1] == '1' and l[x + 1] == '2' or (l[x - 1] == '2' and l[x + 1] == '1'):
					l[x] = '3'
				elif l[x - 1] == '2' and l[x + 1] == '3' or (l[x - 1] == '3' and l[x + 1] == '2'):
					l[x] = '1'
				elif l[x - 1] != '1' and l[x + 1] != '1':
					l[x] = '1'
				elif l[x - 1] != '2' and l[x + 1] != '2':
					l[x] = '2'
				elif l[x + 1] != '3' and l[x - 1] != '3':
					l[x] = '3'
		if l[-1] == '-1':
			if l[-2] != '1':
				l[-1] = '1'
			elif l[-2] != '2':
				l[-1] = '2'
		print('YES')
		print(' '.join(l))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 2:
		flag1 = 0
		arr1 = [0] * n
		arr2 = [0] * n
		for i in range(0, n):
			if i & 1:
				arr1[i] = 2
				arr2[i] = 1
			else:
				arr1[i] = 1
				arr2[i] = 2
		for i in range(0, n):
			if arr[i] != -1:
				if arr[i] != arr1[i]:
					flag1 = 1
					break
		if flag1 == 0:
			print('YES')
			print(*arr1)
		else:
			flag1 = 0
			for i in range(0, n):
				if arr[i] != -1:
					if arr[i] != arr2[i]:
						flag1 = 1
						break
			if flag1 == 1:
				print('NO')
			else:
				print('YES')
				print(*arr2)
	else:
		flag = 0
		if arr[0] == -1:
			for i in range(1, k + 1):
				if i != arr[1]:
					arr[0] = i
					got = 1
					break
		for i in range(1, n - 1):
			if arr[i] == -1:
				got = 0
				for j in range(1, k + 1):
					if j != arr[i - 1] and j != arr[i + 1]:
						arr[i] = j
						got = 1
						break
				if got == 0:
					flag = 1
					break
		if arr[n - 1] == -1:
			got = 0
			for f in range(1, k + 1):
				if f != arr[n - 2]:
					arr[n - 1] = f
					got = 1
					break
			if got == 0:
				flag = 1
		if flag == 1:
			print('NO')
		else:
			print('YES')
			print(*arr)


def hi(a, b):
	for i in range(len(a)):
		if a[i] != -1:
			if a[i] != b[i]:
				return 0
	return 1

def valani():
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	ls = list(range(1, K + 1))
	if N < 3:
		print('YES')
		return 'Either you live it Or leave it...'
	if K == 2 and N <= 1000:
		fg = 0
		if A.count(-1) == N:
			for i in range(N):
				A[i] = 1 if i % 2 == 0 else 2
			fg = 2
		else:
			B = [0] * N
			C = [0] * N
			for i in range(N):
				B[i] = 1 if i % 2 == 0 else 2
				C[i] = 1 if B[i] == 2 else 2
			for i in range(N):
				if A[i] != -1:
					fg = 'b' if A[i] == B[i] else 'c'
					break
			dm = B if fg == 'b' else C
			fg = hi(A, dm)
		if fg == 1:
			A = dm
		elif fg == 2:
			pass
		else:
			print('NO')
			return 'Either you live it Or leave it...'
		print('YES')
		for i in A:
			print(i, end=' ')
		print()
		return 'Either you live it Or leave it...'
	for i in range(N):
		nx = i + 1
		pr = i - 1
		if A[i] == -1:
			if i == N - 1:
				t1 = A[pr]
				for j in ls:
					if t1 != j:
						x = j
						A[i] = j
						break
				else:
					print('NO')
					return 'Either you live it Or leave it...'
			elif i == 0:
				t2 = A[nx]
				for j in ls:
					if t2 != j:
						x = j
						A[i] = j
						break
				else:
					print('NO')
					return 'Either you live it Or leave it...'
			else:
				t1 = A[pr]
				t2 = A[nx]
				for j in ls:
					if t1 != j and t2 != j:
						x = j
						A[i] = j
						break
				else:
					print('NO')
					return 'Either you live it Or leave it...'
	print('YES')
	for i in A:
		print(i, end=' ')
	print()
	return 'Either you live it Or leave it...'
t = int(input())
for _ in range(t):
	meet = valani()


T = int(input())
for t in range(T):
	flag = True
	(n, k) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	if k == 2:
		ind = 0
		while ind < n - 1 and l[ind] == -1:
			ind += 1
		prev = l[ind]
		for index in range(ind + 1, n):
			if l[index] == -1:
				if prev == 1:
					l[index] = 2
				else:
					l[index] = 1
			prev = l[index]
		prev = l[ind]
		for index in range(ind - 1, -1, -1):
			if l[index] == -1:
				if prev == 1:
					l[index] = 2
				else:
					l[index] = 1
			prev = l[index]
		if l[0] == l[1] or l[n - 2] == l[n - 1]:
			flag = False
		for i in range(1, n - 1):
			if l[i] == l[i + 1] or l[i - 1] == l[i]:
				flag = False
				break
		if l[n - 1] == -1:
			if l[n - 2] == 1:
				l[n - 1] = 2
			else:
				l[n - 1] = 1
	else:
		for i in range(n):
			if l[i] != -1:
				pass
			elif i != 0 and i != n - 1:
				if l[i - 1] == 1:
					if l[i + 1] == 2:
						if k <= 2:
							flag = False
							break
						else:
							l[i] = 3
					else:
						l[i] = 2
				elif l[i - 1] == 2:
					if l[i + 1] == 1:
						if k <= 2:
							flag = False
							break
						else:
							l[i] = 3
					else:
						l[i] = 1
				elif l[i + 1] == 1:
					l[i] = 2
				else:
					l[i] = 1
			elif i == 0:
				if l[i + 1] == 1:
					l[i] = 2
				else:
					l[i] = 1
			elif l[i - 1] == 1:
				l[i] = 2
			else:
				l[i] = 1
	if flag:
		print('YES')
		print(*l, sep=' ')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = ''
	if N == 1:
		if A[0] == -1:
			A[0] = 1
		ans = 'YES'
	elif K == 2:
		(flag1, flag2) = (0, 0)
		s1 = [a for a in A]
		s2 = [a for a in A]
		cnt = 0
		for i in range(N):
			if s1[i] == -1:
				s1[i] = 1 if cnt % 2 == 0 else 2
				s2[i] = 2 if cnt % 2 == 0 else 1
			cnt += 1
		for i in range(N - 1):
			if s1[i] == s1[i + 1]:
				flag1 = 1
			if s2[i] == s2[i + 1]:
				flag2 = 1
		if flag1 == 0:
			ans = 'YES'
			A = s1
		elif flag2 == 0:
			ans = 'YES'
			A = s2
		else:
			ans = 'NO'
	else:
		ans = 'YES'
		if A[0] == -1:
			if A[1] == 1:
				A[0] = 2
			else:
				A[0] = 1
		if A[-1] == -1:
			if A[-1] == -1:
				if A[-2] == 1:
					A[-1] = 2
				else:
					A[-1] = 1
		for i in range(1, N - 1):
			if A[i] == -1:
				for m in range(1, 4):
					if A[i - 1] != m and A[i + 1] != m:
						A[i] = m
						break
	if ans == 'YES':
		print(ans)
		for a in A:
			print(a, end=' ')
		print()
	else:
		print(ans)


import math
t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	c = 0
	mi = 0
	if k == 2:
		b = []
		b.append(1)
		for i in range(1, n):
			if b[i - 1] == 1:
				b.append(2)
			else:
				b.append(1)
		for i in range(n):
			if a[i] != -1:
				if a[i] != b[i]:
					break
		else:
			print('YES')
			for i in range(n):
				print(b[i], end=' ')
			print()
			continue
		b = []
		b.append(2)
		for i in range(1, n):
			if b[i - 1] == 1:
				b.append(2)
			else:
				b.append(1)
		for i in range(n):
			if a[i] != -1:
				if a[i] != b[i]:
					print('NO')
					break
		else:
			print('YES')
			for i in range(n):
				print(b[i], end=' ')
			print()
	else:
		print('YES')
		for i in range(n):
			if a[i] == -1:
				if i == 0:
					if a[i + 1] == 1:
						a[i] = k
					else:
						a[i] = 1
				elif i == n - 1:
					if a[i - 1] == 1:
						a[i] = k
					else:
						a[i] = 1
				elif a[i - 1] == 1:
					if a[i + 1] == 2:
						a[i] = 3
					else:
						a[i] = 2
				elif a[i - 1] == 2:
					if a[i + 1] == 1:
						a[i] = 3
					else:
						a[i] = 1
				elif a[i + 1] == 2:
					a[i] = 1
				else:
					a[i] = 2
		for i in range(n):
			print(a[i], end=' ')
		print()


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	if n == 1:
		if arr[0] == -1:
			arr[0] = 1
			print('YES')
			print(arr[0])
		else:
			print('YES')
			print(arr[0])
	elif k == 2:
		if arr[0] == -1:
			for i in range(n):
				if arr[i] != -1:
					break
			if arr[i] != -1:
				temp = arr[i]
				if temp == 1:
					if i % 2 == 1:
						arr[0] = 2
					else:
						arr[0] = 1
				elif i % 2 == 0:
					arr[0] = 2
				else:
					arr[0] = 1
			else:
				arr[0] = 1
		for i in range(1, n - 1):
			if arr[i] == -1:
				if arr[i - 1] == arr[i + 1] or arr[i + 1] == -1:
					if arr[i - 1] == 1:
						arr[i] = 2
					else:
						arr[i] = 1
				else:
					print('NO')
					break
		else:
			i += 1
			if arr[i] == -1:
				if arr[i - 1] == 1:
					arr[i] = 2
				else:
					arr[i] = 1
			print('YES')
			print(*arr)
	else:
		if arr[0] == -1:
			if arr[1] == 1:
				arr[0] = 2
			else:
				arr[0] = 1
		for i in range(1, n - 1):
			if arr[i] == -1:
				if arr[i - 1] == 1 or arr[i + 1] == 1:
					if arr[i + 1] == 2 or arr[i - 1] == 2:
						arr[i] = 3
					else:
						arr[i] = 2
				else:
					arr[i] = 1
		else:
			i += 1
			if arr[i] == -1:
				if arr[i - 1] == 1:
					arr[i] = 2
				else:
					arr[i] = 1
			print('YES')
			print(*arr)


import re
import os
import sys
from math import ceil
from fractions import gcd
from queue import Queue
from collections import defaultdict, Counter, deque
from bisect import bisect, insort, bisect_left, bisect_right
mod = int(1000000000.0) + 7
input = sys.stdin.readline

def isValid(arr):
	for i in range(1, len(arr)):
		if arr[i] == arr[i - 1] or arr[i] == -1:
			return False
	return True

def solve2(arr, n):
	(p1, p2) = ([i % 2 + 1 for i in range(n)], [2 - i % 2 for i in range(n)])
	for i in range(n):
		if arr[i] != p1[i] and arr[i] != -1:
			for i in range(n):
				if arr[i] != p2[i] and arr[i] != -1:
					return 'NO'
			return 'YES\n' + ' '.join(list(map(str, p2)))
	return 'YES\n' + ' '.join(list(map(str, p1)))

def solve(arr, n, k):
	arr = [0] + arr + [0]
	for i in range(1, n + 1):
		if arr[i] == -1:
			for j in range(1, min(3, k) + 1):
				if arr[i - 1] != j and arr[i + 1] != j:
					arr[i] = j
					break
	if isValid(arr[1:-1]):
		return 'YES\n' + ' '.join(list(map(str, arr[1:-1])))
	return 'NO'

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		arr = list(map(int, input().split()))
		if k == 2:
			print(solve2(arr, n))
		else:
			print(solve(arr, n, k))
main()


def getf(k, L):
	for i in range(1, k + 1):
		if i not in L:
			return i
t = int(input())
for i in range(t):
	ind1 = ind2 = tem = 0
	(n, k) = map(int, input().split())
	nnn = n
	A = list(map(int, input().split()))
	if k == 2:
		if n == 1:
			print('YES')
			if A[0] == -1:
				print(1)
			else:
				print(A[0])
			continue
		for j in range(n - 1):
			if A[j] == -1:
				pass
			elif A[j] == 1 and (A[j + 1] == 2 or A[j + 1] == -1):
				A[j + 1] = 2
			elif A[j] == 2 and (A[j + 1] == 1 or A[j + 1] == -1):
				A[j + 1] = 1
			else:
				tem = 1
				break
		if 1 in A:
			ind1 = A.index(1) + 1
		if 2 in A:
			ind2 = A.index(2) + 1
		if ind1 == 0 and ind2 == 0:
			for j in range(n):
				if j % 2 == 0:
					A[j] = 1
				else:
					A[j] = 2
		elif ind1 != 0:
			if ind1 % 2 == 0:
				for j in range(n):
					if j % 2 != 0 and A[j] != 2:
						A[j] = 1
					elif j % 2 == 0 and A[j] != 1:
						A[j] = 2
					else:
						tem = 1
						break
			else:
				for j in range(n):
					if j % 2 != 0 and A[j] != 1:
						A[j] = 2
					elif j % 2 == 0 and A[j] != 2:
						A[j] = 1
					else:
						tem = 1
						break
		elif ind2 % 2 == 0:
			for j in range(n):
				if j % 2 == 0 and A[j] != 2:
					A[j] = 1
				elif j % 2 != 0 and A[j] != 1:
					A[j] = 2
				else:
					tem = 1
					break
		else:
			for j in range(n):
				if j % 2 == 0 and A[j] != 1:
					A[j] = 2
				elif j % 2 != 0 and A[j] != 2:
					A[j] = 1
				else:
					tem = 1
					break
		if tem == 1:
			print('NO')
			continue
		print('YES')
		print(*A)
	else:
		if n == 1:
			print('YES')
			if A[0] == -1:
				print(1)
			else:
				print(A[0])
			continue
		if n == 2:
			if A[0] == A[1] and A[0] != -1:
				print('NO')
				continue
			elif A[0] == A[1] and A[0] == -1:
				A[0] = 1
				A[1] = 2
			elif A[0] == -1:
				A[0] = getf(k, [A[1]])
			elif A[1] == -1:
				A[1] = getf(k, [A[0]])
			print('YES')
			print(*A)
			continue
		tem = 0
		for ii in range(1, n - 1):
			if A[ii - 1] == A[ii] and A[ii - 1] != -1 or (A[ii] == A[ii + 1] and A[ii] != -1):
				tem = 1
				break
		if tem == 1:
			print('NO')
			continue
		else:
			for ii in range(nnn):
				if A[ii] == -1 and ii == 0:
					A[ii] = getf(k, [A[ii + 1]])
				elif A[ii] == -1 and ii == n - 1:
					A[ii] = getf(k, [A[ii - 1]])
				elif A[ii] == -1 and ii != 0 and (ii != n - 1):
					A[ii] = getf(k, [A[ii - 1], A[ii + 1]])
			print('YES')
			print(*A)


t = int(input())
while t > 0:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = [int(x) for x in input().split()]
	r = []
	f = 1
	if k == 2:
		z1 = []
		z2 = []
		f1 = 1
		f2 = 1
		for x in range(n):
			z1.append(x % 2 + 1)
			if x % 2 == 0:
				z2.append(2)
			else:
				z2.append(1)
		for x in range(n):
			if a[x] != -1:
				if z1[x] != a[x]:
					f1 = 0
				if z2[x] != a[x]:
					f2 = 0
			if f1 == 0 and f2 == 0:
				f = 0
				break
		if f != 0 and f1 == 1 and (f2 == 0):
			a = z1
		elif f != 0 and f2 == 1 and (f1 == 0):
			a = z2
	for x in range(n):
		if a[x] == -1:
			for z in range(1, k + 1):
				if x == 0:
					if x == n - 1:
						a[x] = z
						break
					if a[x + 1] != z:
						a[x] = z
						break
				elif n - 1 == x:
					if a[x - 1] != z:
						a[x] = z
						break
				else:
					if a[x + 1] != z and a[x - 1] != z:
						a[x] = z
						break
					if z == k:
						f = 0
						break
		if f == 0:
			break
	if f == 0:
		print('NO')
	else:
		print('YES')
		print(*a)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if n == 1:
		print('YES')
		if l[0] == -1:
			print(k)
		else:
			print(l[0])
		continue
	if k == 2:
		i = 0
		m = []
		while i < n:
			if l[i] != -1:
				i += 1
			else:
				c = []
				while i < n and l[i] == -1:
					c.append(i)
					i += 1
				m.append(c)
		flag = True
		for i in m:
			if i[0] == 0:
				if i[-1] == n - 1:
					k = 0
					for j in range(i[0], i[-1] + 1):
						l[j] = k + 1
						k = k ^ 1
				else:
					x = i[-1]
					if l[x + 1] == 1:
						if len(i) % 2 != 0:
							k = 1
						else:
							k = 0
						for j in range(i[0], i[-1] + 1):
							l[j] = k + 1
							k = k ^ 1
					else:
						if len(i) % 2 == 0:
							k = 1
						else:
							k = 0
						for j in range(i[0], i[-1] + 1):
							l[j] = k + 1
							k = k ^ 1
			elif i[-1] == n - 1:
				x = i[0]
				if l[x - 1] == 1:
					k = 1
				else:
					k = 0
				for j in range(i[0], i[-1] + 1):
					l[j] = k + 1
					k = k ^ 1
			else:
				x = i[0] - 1
				y = i[-1] + 1
				if l[x] == l[y]:
					if len(i) % 2 == 0:
						flag = False
						break
					else:
						if l[x] == 1:
							k = 1
						else:
							k = 0
						for j in range(i[0], i[-1] + 1):
							l[j] = k + 1
							k = k ^ 1
				elif len(i) % 2 != 0:
					flag = False
					break
				else:
					if l[x] == 1:
						k = 1
					else:
						k = 0
					for j in range(i[0], i[-1] + 1):
						l[j] = k + 1
						k = k ^ 1
		if flag:
			print('YES')
			print(*l)
		else:
			print('NO')
		continue
	flag = True
	for i in range(n):
		if l[i] == -1:
			if i == 0:
				if l[i + 1] == -1:
					l[i] = 1
				elif l[i + 1] == 1:
					l[i] = 2
				else:
					l[i] = 1
			elif i == n - 1:
				if l[i - 1] == 1:
					l[i] = 2
				else:
					l[i] = 1
			elif l[i + 1] != -1:
				if k == 2:
					if l[i - 1] == 1 and l[i + 1] == 2 or (l[i - 1] == 2 and l[i + 1] == 1):
						flag = False
						break
					elif l[i - 1] == 1:
						l[i] = 2
					else:
						l[i] = 1
				elif l[i - 1] == 1:
					if l[i + 1] == 2:
						l[i] = 3
					else:
						l[i] = 2
				elif l[i + 1] == 1:
					if l[i - 1] == 2:
						l[i] = 3
					else:
						l[i] = 2
				else:
					l[i] = 1
			elif l[i - 1] == 1:
				l[i] = 2
			else:
				l[i] = 1
	if flag:
		print('YES')
		print(*l)
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	days = list(map(int, input().split()))
	if k > 2:
		if days[0] == -1:
			days[0] = 1
			try:
				if days[1] == 1:
					days[0] = 2
			except IndexError:
				pass
		for i in range(1, n - 1):
			if days[i] == -1:
				days[i] = 1
				if days[i - 1] == 1 or days[i + 1] == 1:
					days[i] = 2
					if days[i - 1] == 2 or days[i + 1] == 2:
						days[i] = 3
		if days[n - 1] == -1:
			days[n - 1] = 1
			try:
				if days[n - 2] == 1:
					days[n - 1] = 2
			except IndexError:
				pass
		print('YES')
		print(*days, sep=' ')
	else:
		flag = 0
		for i in range(n):
			if days[i] != -1:
				break
		else:
			days[i] = 1
		for j in range(i + 1, n - 1):
			if days[j] == -1:
				days[j] = 1
				if days[j - 1] == 1 or days[j + 1] == 1:
					days[j] = 2
					if days[j - 1] == 2 or days[j + 1] == 2:
						print('NO')
						flag = 1
						break
		if flag == 0:
			if days[n - 1] == -1:
				days[n - 1] = 1
				if days[n - 2] == 1:
					days[n - 1] = 2
			for j in range(i - 1, -1, -1):
				if days[j] == -1:
					days[j] = 1
					if days[j + 1] == 1:
						days[j] = 2
			print('YES')
			print(*days, sep=' ')


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	Plan = list(map(int, input().split()))
	if K == 2:
		Answer = []
		X = Plan[::2]
		Y = Plan[1::2]
		X = set(X)
		Y = set(Y)
		if len(X) == 3 or len(Y) == 3:
			print('NO')
			continue
		if len(X) > 1 and -1 not in X:
			print('NO')
			continue
		elif len(Y) > 1 and -1 not in Y:
			print('NO')
			continue
		if 1 in X:
			X = 1
		elif 2 in X:
			X = 2
		else:
			X = 0
		if 1 in Y:
			Y = 1
			if X == 1:
				print('NO')
				continue
			elif X == 0:
				X = 2
		elif 2 in Y:
			Y = 2
			if X == 2:
				print('NO')
				continue
			elif X == 0:
				X = 1
		elif X == 2:
			Y = 1
		else:
			X = 1
			Y = 2
		print('YES')
		for i in range(N - 1):
			if i % 2 == 0:
				print(X, end=' ')
			else:
				print(Y, end=' ')
		if (N - 1) % 2 == 0:
			print(X)
		else:
			print(Y)
	else:
		print('YES')
		if -1 not in Plan:
			print(*Plan)
			continue
		elif N == Plan.count(-1):
			X = 1
			Y = 2
			for i in range(N - 1):
				if i % 2 == 0:
					print(X, end=' ')
				else:
					print(Y, end=' ')
			if (N - 1) % 2 == 0:
				print(X)
			else:
				print(Y)
		else:
			if Plan[0] == -1 and Plan[1] != 1:
				Plan[0] = 1
			elif Plan[0] == -1 and Plan[1] == 1:
				Plan[0] = 2
			for i in range(1, N - 1):
				if Plan[i] != -1:
					pass
				elif Plan[i - 1] == 1:
					if Plan[i + 1] == 2:
						Plan[i] = 3
					else:
						Plan[i] = 2
				elif Plan[i - 1] == 2:
					if Plan[i + 1] == 1:
						Plan[i] = 3
					else:
						Plan[i] = 1
				elif Plan[i + 1] == 1:
					Plan[i] = 2
				else:
					Plan[i] = 1
			if Plan[N - 1] == -1:
				if Plan[N - 2] == 1:
					Plan[N - 1] = 2
				else:
					Plan[N - 1] = 1
			else:
				pass
			print(*Plan)


n = int(input())
for x in range(n):
	(a, b) = list(map(int, input().split()))
	rangee = list(range(1, b + 1))
	array = list(map(int, input().split()))
	flag = 5
	if b == 2:
		if array[0] == -1:
			end = -5
			for z in range(1, a):
				if array[z] != -1:
					end = z
					break
			if end < 0:
				pass
			else:
				val = array[end]
				jam = end
				if jam % 2 == 0:
					if val == 1:
						array[0] = 1
					else:
						array[0] = 2
				elif val == 1:
					array[0] = 2
				else:
					array[0] = 1
	for y in range(a):
		if array[y] != -1:
			pass
		elif y != 0 and y != a - 1:
			first = array[y - 1]
			second = array[y + 1]
			if second == -1:
				if first == 1:
					value = 2
				else:
					value = 1
				if value <= b:
					array[y] = value
				else:
					flag = 6
					break
			else:
				arr = [first, second]
				if 1 not in arr:
					value = 1
				elif 2 not in arr:
					value = 2
				else:
					value = 3
				if value <= b:
					array[y] = value
				else:
					flag = 6
					break
		elif y == 0:
			if a == 1:
				if array[y] == -1:
					array[y] = 1
				else:
					pass
			elif array[y + 1] == -1:
				array[y] = 1
			elif array[y + 1] == 1:
				array[y] = 2
			else:
				array[y] == 1
		elif a == 1:
			if array[y] == -1:
				array[y] = 1
			else:
				pass
		elif array[y] == -1:
			if array[y - 1] == 1:
				array[y] = 2
			else:
				array[y] = 1
		else:
			pass
	for y in range(a - 1):
		if array[y] == array[y + 1]:
			flag = 6
			break
	if flag == 6:
		print('NO')
	else:
		print('YES')
		print(*array)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	l = list(map(int, input().split()))
	s = -1
	for i in range(N):
		if l[i] != -1:
			s = i
			break
	flag = 0
	if s == -1:
		a = 1
		for i in range(N):
			l[i] = a
			a = 3 - a
	else:
		if l[s] <= 2:
			a = 3 - l[s]
		else:
			a = 1
		for i in range(s + 1, N):
			if l[i] == -1:
				l[i] = a
				a = 3 - a
			elif l[i] == l[i - 1]:
				if K > 2:
					if i > 1 and l[i - 2] == 3:
						l[i - 1] = 2
					else:
						l[i - 1] = 3
				else:
					flag = 1
					break
			elif l[i] <= 2:
				a = 3 - l[i]
			else:
				a = 1
		if l[s] <= 2:
			a = 3 - l[s]
		else:
			a = 1
		for i in range(s - 1, -1, -1):
			l[i] = a
			a = 3 - a
	for i in range(N - 1):
		if l[i] == l[i + 1]:
			flag = 1
			break
	if flag:
		print('NO')
	else:
		print('YES')
		for i in l:
			print(i, end=' ')
		print()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	temp = -1
	j = 0
	flag = 1
	while j < n:
		if temp == -1 or j > temp:
			temp = -1
			for l in range(j, n):
				if A[l] != -1:
					temp = l
					break
		if temp == -1 or temp == n:
			temp = n
			for l in range(1, k + 1):
				if l != A[j - 1]:
					A[j] = l
					break
			j += 1
		elif A[j] != -1:
			j += 1
			continue
		else:
			if j == 0:
				if (temp - j) % 2 == 0:
					A[j] = A[temp]
				else:
					for l in range(1, k + 1):
						if l != A[temp]:
							A[j] = l
							break
			elif (temp - j) % 2 == 0 and A[j - 1] != A[temp]:
				A[j] = A[temp]
			else:
				for l in range(1, k + 1):
					if l != A[temp] and l != A[j - 1]:
						A[j] = l
						break
			j += 1
		if A[j - 1] == -1:
			flag = 0
			break
	if flag == 1:
		print('YES')
		print(*A)
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	if n <= 1000 and k == 2:
		l1 = [1] * n
		l2 = [2] * n
		for i in range(1, n):
			if l1[i - 1] == 1:
				l1[i] = 2
			else:
				l1[i] = 1
			if l2[i - 1] == 2:
				l2[i] = 1
			else:
				l2[i] = 2
		flag = 0
		for i in range(n):
			if a[i] != -1:
				if a[i] != l1[i]:
					flag = 1
					break
		if flag == 0:
			print('YES')
			print(*l1)
		else:
			flag = 0
			for i in range(n):
				if a[i] != -1:
					if a[i] != l2[i]:
						flag = 1
						break
			if flag == 0:
				print('YES')
				print(*l2)
			else:
				print('NO')
	else:
		check = 0
		for i in range(n):
			if a[i] == -1:
				check = 1
		if check == 0:
			print('YES')
			print(*a)
		else:
			flag = 0
			if a[0] == -1:
				temp = 0
				for j in range(1, k + 1):
					if j != a[1]:
						a[0] = j
						temp = 1
						break
				if temp == 0:
					flag = 1
			for i in range(1, n - 1):
				forward = a[i + 1]
				backward = a[i - 1]
				mid = a[i]
				if mid == -1:
					temp = 0
					for j in range(1, k + 1):
						if j != backward and j != forward:
							a[i] = j
							temp = 1
							break
					if temp == 0:
						flag = 1
						break
			temp = 0
			last = a[n - 1]
			if last == -1:
				for j in range(1, k + 1):
					if j != a[n - 2]:
						a[n - 1] = j
						temp = 1
						break
				if temp == 0:
					flag = 1
			if flag == 0:
				print('YES')
				print(*a)
			else:
				print('NO')


for i in range(int(input())):
	(n, k) = [int(j) for j in input().split()]
	a = [int(j) for j in input().split()]
	if n == 1:
		if a[0] == -1:
			a[0] = 1
		print('YES')
		print(a[0])
	elif n == 2:
		if a[0] == -1:
			if a[1] == 1:
				a[0] = 2
			else:
				a[0] = 1
		if a[1] == -1:
			a[1] = 2
		print('YES')
		print(*a)
	else:
		f = 1
		c = 0
		if a.count(-1) != n:
			if a[0] == -1:
				j = 0
				while a[j] == -1:
					j += 1
				j -= 1
				while j >= 0:
					if a[j + 1] == 1:
						a[j] = 2
					else:
						a[j] = 1
					j -= 1
			if a[-1] == -1:
				j = n - 1
				while a[j] == -1:
					j -= 1
				j += 1
				while j < n:
					if a[j - 1] == 1:
						a[j] = 2
					else:
						a[j] = 1
					j += 1
		else:
			a[0] = 1
		c = a[0]
		for j in range(1, n - 1):
			if a[j] != -1:
				c = a[j]
			else:
				if a[j - 1] != 1 and a[j + 1] != 1:
					a[j] = 1
				elif a[j - 1] != 2 and a[j + 1] != 2:
					a[j] = 2
				elif k > 2:
					a[j] = 3
				else:
					f = 0
					break
				c = a[j]
		if a[-1] == -1:
			if a[-2] == 1:
				a[-1] = 2
			else:
				a[-1] = 1
		for j in range(1, n):
			if a[j - 1] == a[j]:
				f = 0
				break
		if f == 0:
			print('NO')
		else:
			print('YES')
			print(*a)


t = int(input())
for ankit in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * n
	y = 0
	f = 0
	if k == 2:
		for x in range(n):
			if a[x] == -1:
				y += 1
			else:
				if y > 0 and y % 2 == 0 and (x - y > 0) and (a[x - y - 1] == a[x]):
					f = 1
					break
				if y > 0 and y % 2 == 1 and (x - y > 0) and (a[x - y - 1] != a[x]):
					f = 1
					break
				o = a[x] - 1 ^ 1
				for e in range(x - 1, x - y - 1, -1):
					b[e] = o + 1
					o ^= 1
				b[x] = a[x]
				y = 0
		if f == 0 and y > 0:
			if n - y > 0:
				o = a[n - y - 1] - 1 ^ 1
			else:
				o = 0
			for r in range(n - y, n):
				b[r] = o + 1
				o ^= 1
		if f == 0:
			print('YES')
			print(*b)
		else:
			print('NO')
	else:
		c = [1, 2, 3]
		for i in range(n):
			if a[i] == -1:
				if i > 0 and b[i - 1] < 4:
					c.remove(b[i - 1])
				if i < n - 1 and c.count(a[i + 1]) > 0:
					c.remove(a[i + 1])
				b[i] = c[0]
				c = [1, 2, 3]
			else:
				b[i] = a[i]
		print('YES')
		print(*b)


t = int(input())
for _ in range(0, t):
	x = input()
	n = int(x.split(' ')[0])
	k = int(x.split(' ')[1])
	arr = [0]
	arr.extend([int(i) for i in input().split(' ')])
	arr.append(0)
	flag = 1
	j = 0
	if arr[1] == -1:
		for i in range(1, n + 1):
			if arr[i] != -1:
				j = i
				break
		if j != 0:
			for i in range(j - 1, 1, -1):
				if arr[i + 1] != 1:
					arr[i] = 1
				else:
					arr[i] = 2
		if j == 0:
			j = -1
	if j == -1:
		for i in range(1, n + 1):
			if arr[i - 1] == 1:
				arr[i] = 2
			else:
				arr[i] = 1
	else:
		for i in range(1, n + 1):
			if arr[i] == -1:
				if arr[i - 1] != 1 and arr[i + 1] != 1:
					arr[i] = 1
				elif arr[i - 1] == 1 or arr[i + 1] == 1:
					if arr[i - 1] == 2 or arr[i + 1] == 2:
						if k < 3:
							flag = 0
							break
						else:
							arr[i] = 3
					else:
						arr[i] = 2
	if flag:
		print('YES')
		print(' '.join((str(i) for i in arr[1:n + 1])))
	else:
		print('NO')


def give(a, b, k):
	for i in range(1, k + 1):
		if i != a and i != b:
			return i
	return 0
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [0] + list(map(int, input().split())) + [0]
	can = False
	if k == 2:
		bcan = False
		b = a[:]
		for i in range(n, 0, -1):
			if b[i] == -1:
				x = give(b[i - 1], b[i + 1], k)
				if x == 0:
					bcan = True
					break
				b[i] = x
		if not bcan:
			print('YES')
			print(*b[1:n + 1])
			continue
	for i in range(1, n + 1):
		if a[i] == -1:
			x = give(a[i - 1], a[i + 1], k)
			if x == 0:
				print('NO')
				can = True
				break
			a[i] = x
	if not can:
		print('YES')
		print(*a[1:n + 1])


ARRAY = [i for i in range(1, 10 ** 5 + 2)]

def solve(n, arr):
	(flag1, flag2) = (1, 1)
	(a, b) = (1, 2)
	for i in arr:
		if i != -1:
			if i != a:
				flag1 = 0
			if i != b:
				flag2 = 0
		a ^= 3
		b ^= 3
		if not (flag1 or flag2):
			return []
	return [flag1, flag2]
for _ in range(int(input())):
	(n, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	flag = 1
	if K == 2:
		flag = solve(n, arr)
		if not flag:
			print('NO')
		else:
			if flag[0]:
				arr = [1, 2] * (n // 2 + 1)
			else:
				arr = [2, 1] * (n // 2 + 1)
			print('YES')
			print(*arr[:n])
		continue
	for i in range(n):
		if arr[i] == -1:
			if i == 0:
				left = 0
			else:
				left = arr[i - 1]
			if i + 1 == n or (i + 1 < n and arr[i + 1] == -1):
				right = 0
			else:
				right = arr[i + 1]
			if left == right == 0:
				k = 0
			elif left == 0 and right != 0:
				k = 0
				while ARRAY[k] == right:
					k += 1
			else:
				k = 0
				while ARRAY[k] == left or ARRAY[k] == right:
					k += 1
			if k > K - 1:
				flag = 0
				break
			else:
				arr[i] = ARRAY[k]
	if flag == 0:
		print('NO')
	else:
		print('YES')
		print(*arr)


from sys import stdin

def func(arr, a, b=-2):
	cond = False
	for i in range(len(arr)):
		if arr[i] != a and arr[i] != b:
			cond = True
			m = arr[i]
			break
		else:
			pass
	if cond == True:
		return m
	else:
		return -1
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	arr = list(map(int, stdin.readline().split()))
	cond = True
	if n == 1:
		if arr[0] == -1:
			arr[0] = 1
		else:
			pass
	elif k == 2:
		m = {-1: [], 1: [], 2: []}
		for i in range(n):
			m[arr[i]].append(i)
		(a, b, c) = (m[-1], m[1], m[2])
		(l1, l2, l3) = (len(a), len(b), len(c))
		if len(list(filter(lambda x: x % 2 == 0, b))) == l2 and len(list(filter(lambda x: x % 2 == 1, c))) == l3:
			for ele in a:
				if ele % 2 == 0:
					arr[ele] = 1
				else:
					arr[ele] = 2
		elif len(list(filter(lambda x: x % 2 == 1, b))) == l2 and len(list(filter(lambda x: x % 2 == 0, c))) == l3:
			for ele in a:
				if ele % 2 == 0:
					arr[ele] = 2
				else:
					arr[ele] = 1
		else:
			cond = False
	else:
		ans = [i for i in range(1, k + 1)]
		for i in range(n):
			if arr[i] == -1:
				if i == 0:
					if func(ans, arr[1]) == -1:
						cond = False
						break
					else:
						arr[i] = func(ans, arr[1])
				elif i == n - 1:
					if func(ans, arr[n - 2]) == -1:
						cond = False
						break
					else:
						arr[i] = func(ans, arr[n - 2])
				elif func(ans, arr[i - 1], arr[i + 1]) == -1:
					cond = False
					break
				else:
					arr[i] = func(ans, arr[i - 1], arr[i + 1])
			else:
				pass
	if cond == True:
		d = True
		for i in range(n - 1):
			if arr[i] == arr[i + 1]:
				d = False
				break
		if d == True:
			print('YES')
			print(*arr)
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	k = min(k, n)
	A = list(map(int, input().split()))
	if k >= 3:
		if A[0] == -1:
			if A[1] == 1:
				A[0] = 2
			else:
				A[0] = 1
		for i in range(1, n - 1):
			if A[i] == -1:
				A[i] = ({1, 2, 3} - {A[i - 1], A[i + 1]}).pop()
		if A[-1] == -1:
			if A[-2] == 1:
				A[-1] = 2
			else:
				A[-1] = 1
		print('YES')
		print(*A)
	elif k == 1:
		if n == 1:
			print('YES')
			print(1)
		else:
			print('NO')
	else:
		B = [i % 2 + 1 for i in range(n)]
		C = [2 - i % 2 for i in range(n)]
		(f1, f2) = (1, 1)
		for i in range(n):
			if A[i] != -1 and A[i] != B[i]:
				f1 = 0
			if A[i] != -1 and A[i] != C[i]:
				f2 = 0
		if f1:
			print('YES')
			print(*B)
		elif f2:
			print('YES')
			print(*C)
		else:
			print('NO')


import sys
from collections import defaultdict as dd
from itertools import permutations as pp
from itertools import combinations as cc
from collections import Counter as ccd
from random import randint as rd
from bisect import bisect_left as bl
from heapq import heappush as hpush
from heapq import heappop as hpop
mod = 10 ** 9 + 7

def ri(flag=0):
	if flag == 0:
		return [int(i) for i in sys.stdin.readline().split()]
	else:
		return int(sys.stdin.readline())
for _ in range(ri(1)):
	(n, k) = ri()
	a = [0] + ri() + [0]
	b = a[::-1]
	if k == 2:
		start = -1
		for i in range(1, n + 1):
			if a[i] != -1:
				start = i
				break
		for i in range(start - 1, 0, -1):
			if a[i] == -1:
				if a[i + 1] == 2:
					a[i] = 1
				else:
					a[i] = 2
		for i in range(start + 1, n + 1):
			if a[i] == -1:
				if a[i - 1] == 2:
					a[i] = 1
				else:
					a[i] = 2
	else:
		for i in range(1, n + 1):
			if a[i] == -1:
				for j in range(1, k + 1):
					if a[i - 1] != j and a[i + 1] != j:
						a[i] = j
						break
	status = 1
	for i in range(1, n + 1):
		if a[i] == -1 or a[i] == a[i + 1]:
			status = 0
	if status:
		print('YES')
		print(*a[1:-1])
	else:
		print('NO')