解説は、以下のスライドを参考にしてください。

https://docs.google.com/presentation/d/1guiB42ETF2H9ftp6xYJd3oYF-MkFghegmc12IZHjpZc/edit?usp=sharing

コード (Python)

T = int(input())
for _ in range(T):
    N, K = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    if N == 1:
        print(1)
    else:
        ans = [3]
        for a in (0, 1):
            for b in (0, 1):
                seq = [0] * N
                for i in range(N):
                    if A[i] % 2:
                        seq[i] = 1
                if seq[0] and seq[0] != a + 1:
                    continue
                seq[0] = a + 1
                if a:
                    if seq[1] == 2:
                        continue
                    seq[1] = 1
                if seq[-1] and seq[-1] != b + 1:
                    continue
                seq[-1] = b + 1
                if b:
                    if seq[-2] == 2:
                        continue
                    seq[-2] = 1
                l = N - 1 - K - a - b
                for i in range(a, N - b)[::-1]:
                    if seq[i] == 0 and seq[i + 1] == 1 and l > 1:
                        seq[i] = 2
                        l -= 2
                    else:
                        seq[i] = 1
                if l == 0:
                    ans = min(ans, seq)
        if ans == [3]:
            print(-1)
        else:
            for a in ans:
                print(a)