Eugeny has n cards, each of them has exactly one integer written on it. Eugeny wants to exchange some cards with Nikolay so that the number of even integers on his cards would equal the number of odd integers, and that all these numbers would be distinct. 

Nikolay has m cards, distinct numbers from 1 to m are written on them, one per card. It means that Nikolay has exactly one card with number 1, exactly one card with number 2 and so on. 

A single exchange is a process in which Eugeny gives one card to Nikolay and takes another one from those Nikolay has. Your task is to find the minimum number of card exchanges and determine which cards Eugeny should exchange.


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 2·10^5, 1 ≤ m ≤ 10^9) — the number of cards Eugeny has and the number of cards Nikolay has. It is guaranteed that n is even.

The second line contains a sequence of n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the numbers on Eugeny's cards.


-----Output-----

If there is no answer, print -1.

Otherwise, in the first line print the minimum number of exchanges. In the second line print n integers — Eugeny's cards after all the exchanges with Nikolay. The order of cards should coincide with the card's order in the input data. If the i-th card wasn't exchanged then the i-th number should coincide with the number from the input data. Otherwise, it is considered that this card was exchanged, and the i-th number should be equal to the number on the card it was exchanged to.

If there are multiple answers, it is allowed to print any of them.


-----Examples-----
Input
6 2
5 6 7 9 4 5

Output
1
5 6 7 9 4 2 

Input
8 6
7 7 7 7 8 8 8 8

Output
6
7 2 4 6 8 1 3 5 

Input
4 1
4 2 1 10

Output
-1

Difficulty: HARD
Tags: Mathematics

Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
from collections import *
f = lambda : map(int, input().split())
g = lambda : exit(print(-1))
(n, m) = f()
if n & 1:
	g()
t = list(f())
a = [set(), set()]
b = [[], []]
u = []
for q in t:
	if q in a[q & 1]:
		u.append(q)
	a[q & 1].add(q)
for q in range(1, min(m, n) + 1):
	if q not in a[q & 1]:
		b[q & 1].append(q)
d = len(a[0]) < len(a[1])
a = list(a[d])[len(a[not d]):]
(x, y) = (b[not d], b[d])
k = len(a) + len(u) >> 1
if len(a) > len(u):
	(a, u) = (a[:k], u + a[k:])
k = min(len(a), len(x))
(v, x) = (x[:k], x[k:])
u += a[k:]
k = len(u) - len(v) >> 1
if k > min(len(x), len(y)):
	g()
v += x[:k] + y[:k]
c = Counter(u)
print(len(v))
for q in t:
	if c[q]:
		(c[q], q) = (c[q] - 1, v.pop())
	print(q)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
counter = 0
s = set(a)
nech = set()
chet = set()
for elem in a:
	if elem % 2:
		nech.add(elem)
	else:
		chet.add(elem)
while len(nech) > n // 2:
	nech.pop()
while len(chet) > n // 2:
	chet.pop()
l_n = set([i for i in range(1, min(m + 1, 1000000), 2)])
l_ch = set([i for i in range(2, min(m + 1, 1000000), 2)])
l_ch.difference_update(chet)
l_n.difference_update(nech)
if len(l_ch) + len(chet) < n // 2 or len(l_n) + len(nech) < n // 2:
	print(-1)
else:
	n1 = len(chet)
	n2 = len(nech)
	for i in range(n):
		if a[i] in chet:
			chet.remove(a[i])
		elif a[i] in nech:
			nech.remove(a[i])
		else:
			counter += 1
			if n // 2 - n1 > 0:
				a[i] = l_ch.pop()
				n1 += 1
			else:
				a[i] = l_n.pop()
				n2 += 1
	print(counter)
	print(*a)


import sys
import math

def main():
	(n, m) = map(int, sys.stdin.readline().split())
	x = list(map(int, sys.stdin.readline().split()))
	c = []
	nc = []
	d = {}
	for i in range(n):
		xi = x[i]
		if xi in d:
			continue
		d[xi] = True
		if xi % 2 == 0:
			c.append((xi, i))
		else:
			nc.append((xi, i))
	(a, b) = (-1, 0)
	if len(nc) > len(c):
		(c, nc) = (nc, c)
		(a, b) = (b, a)
	c = sorted(c, key=lambda x: -x[0])
	d = {}
	r = [0] * n
	for i in range(len(nc)):
		(xi, j) = nc[i]
		r[j] = xi
		d[xi] = True
	for i in range(min(n // 2, len(c))):
		(xi, j) = c[i]
		r[j] = xi
		d[xi] = True
	j = 0
	ans = 0
	for i in range(len(c), n // 2):
		b += 2
		while b in d:
			b += 2
		while r[j] != 0:
			j += 1
		r[j] = b
		ans += 1
	for i in range(len(nc), n // 2):
		a += 2
		while a in d:
			a += 2
		while r[j] != 0:
			j += 1
		r[j] = a
		ans += 1
	if a > m or b > m:
		print(-1)
		return
	print(ans)
	print(' '.join(map(str, r)))
main()


class CantException(Exception):
	pass

def odd_v(value):
	return 1 if value % 2 == 1 else -1
change_idx = 1
acceptable = {-1: set(), 1: set()}

def change(card_values, oddv, m):
	global change_idx
	if acceptable[oddv]:
		res = acceptable[oddv].pop()
		card_values.add(res)
		return res
	change_idx_start = change_idx
	while change_idx in card_values or odd_v(change_idx) != oddv:
		if change_idx not in card_values:
			acceptable[odd_v(change_idx)].add(change_idx)
		change_idx += 1
		if change_idx > m:
			change_idx = 1
		if change_idx == change_idx_start:
			raise CantException()
	res = change_idx
	card_values.add(res)
	change_idx += 1
	if change_idx > m:
		change_idx = 1
	return res

def solve():
	(n, m) = map(int, input().split())
	cards = list(map(int, input().split()))
	odd_balance = 0
	card_values = set()
	indices_to_be_changed = set()
	for (i, c) in enumerate(cards):
		odd_balance += odd_v(c)
		if c in card_values:
			indices_to_be_changed.add(i)
		card_values.add(c)
	change_count = len(indices_to_be_changed)
	for i in indices_to_be_changed:
		if odd_v(cards[i]) * odd_balance <= 0:
			cards[i] = change(card_values, odd_v(cards[i]), m)
		else:
			odd_balance -= 2 * odd_v(cards[i])
			cards[i] = change(card_values, -odd_v(cards[i]), m)
	for i in range(len(cards)):
		if odd_balance == 0:
			break
		if odd_v(cards[i]) * odd_balance > 0:
			change_count += 1
			odd_balance -= 2 * odd_v(cards[i])
			cards[i] = change(card_values, -odd_v(cards[i]), m)
	odd_balance = 0
	for (i, c) in enumerate(cards):
		odd_balance += odd_v(c)
	if odd_balance != 0:
		print(odd_balance)
		print('WTFFFFF')
	return (change_count, cards)
try:
	(change_cnt, cards) = solve()
	print(change_cnt)
	print(' '.join(map(str, cards)))
except CantException:
	print('-1')


(n, m) = map(int, input().split())
c = list(map(int, input().split()))
odd_numbs = set()
nodd_numbs = set()
curr_odd = 2
r = 0
curr_nodd = 1
for i in range(len(c)):
	if c[i] % 2 == 0:
		if len(odd_numbs) >= n // 2:
			while curr_nodd in nodd_numbs and curr_nodd <= m:
				curr_nodd += 2
			if curr_nodd > m:
				print(-1)
				exit()
			c[i] = curr_nodd
			r += 1
			nodd_numbs.add(c[i])
		elif c[i] in odd_numbs:
			while curr_odd in odd_numbs and curr_odd <= m:
				curr_odd += 2
			if curr_odd > m:
				print(-1)
				exit()
			c[i] = curr_odd
			r += 1
			odd_numbs.add(c[i])
		else:
			odd_numbs.add(c[i])
	elif len(nodd_numbs) >= n // 2:
		while curr_odd in odd_numbs and curr_odd <= m:
			curr_odd += 2
		if curr_odd > m:
			print(-1)
			exit()
		c[i] = curr_odd
		r += 1
		odd_numbs.add(c[i])
	elif c[i] in nodd_numbs:
		while curr_nodd in nodd_numbs and curr_nodd <= m:
			curr_nodd += 2
		if curr_nodd > m:
			print(-1)
			exit()
		c[i] = curr_nodd
		r += 1
		nodd_numbs.add(c[i])
	else:
		nodd_numbs.add(c[i])
print(r)
print(*c)


def solve(A, n, m):
	uniq = set(A)
	odd = list([x for x in uniq if x % 2])
	even = list([x for x in uniq if x % 2 == 0])
	if len(odd) > n // 2:
		odd.sort()
		odd = odd[-n // 2:]
	if len(even) > n // 2:
		even.sort()
		even = even[-n // 2:]
	odd_needed = n // 2 - len(odd)
	changes = n - len(odd) - len(even)
	k = 1 if odd_needed else 2
	D = {x: True for x in odd + even}
	A1 = A[:]
	for (i, a) in enumerate(A):
		if a in D and D[a]:
			D[a] = False
		else:
			while k in D:
				k += 2
			if k > m:
				return None
			A1[i] = k
			k += 2
			if odd_needed == 1:
				k = 2
			if odd_needed >= 1:
				odd_needed -= 1
	return (A1, changes)
(n, m) = list(map(int, input().split()))
A = [int(x) for x in input().split()]
p = solve(A, n, m)
if p is None:
	print(-1)
else:
	print(p[1])
	print(' '.join(map(str, p[0])))


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=-10 ** 6, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(200001)]
pp = [0] * 200001

def SieveOfEratosthenes(n=200000):
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
so = set()
se = set()
s = set()
(odd, even) = (0, 0)
for i in range(1, min(n, m) + 1):
	if i % 2:
		so.add(i)
	else:
		se.add(i)
for num in a:
	if num % 2:
		odd += 1
		if num in so:
			so.remove(num)
	else:
		even += 1
		if num in se:
			se.remove(num)
ch = 1
c = a.copy()
for i in range(n):
	if a[i] in s:
		if a[i] % 2:
			if odd > even:
				if len(se) == 0:
					ch = 0
					break
				odd -= 1
				even += 1
				a[i] = se.pop()
				s.add(a[i])
			else:
				if len(so) == 0:
					ch = 0
					break
				a[i] = so.pop()
				s.add(a[i])
		elif even > odd:
			if len(so) == 0:
				ch = 0
				break
			odd += 1
			even -= 1
			a[i] = so.pop()
			s.add(a[i])
		else:
			if len(se) == 0:
				ch = 0
				break
			a[i] = se.pop()
			s.add(a[i])
	else:
		s.add(a[i])
if odd > even:
	ct = (odd - even) // 2
	if len(se) < ct:
		ch = 0
	else:
		for i in range(n):
			if a[i] % 2 and ct > 0:
				ct -= 1
				a[i] = se.pop()
else:
	ct = (even - odd) // 2
	if len(so) < ct:
		ch = 0
	else:
		for i in range(n):
			if a[i] % 2 == 0 and ct > 0:
				ct -= 1
				a[i] = so.pop()
if ch:
	res = 0
	for i in range(n):
		if a[i] != c[i]:
			res += 1
	print(res)
	print(*a)
else:
	print(-1)