CF746E Numbers Exchange

Eugeny 有 $ n $ 张卡牌，每张卡牌上恰好写有一个整数。Eugeny 想与 Nikolay 交换一些卡牌，使得他手中的卡牌上偶数和奇数的数量相等，并且这些数字互不相同。 Nikolay 有 $ m $ 张卡牌，每张卡片上写有从 $ 1 $ 到 $ m $ 的不同数字，每个数字恰好一张卡牌。也就是说，Nikolay 恰好有一张编号为 $ 1 $ 的卡，一张编号为 $ 2 $ 的卡，依此类推。 一次交换的过程是，Eugeny 给 Nikolay 一张卡，然后从 Nikolay 手中拿一张他还没有的卡。你的任务是求出最少需要交换多少次，并确定 Eugeny 应该交换哪几张卡牌。

第一行包含两个整数 $ n $ 和 $ m $（$ 2 \leq n \leq 2 \cdot 10^{5} $，$ 1 \leq m \leq 10^{9} $）——Eugeny 和 Nikolay 各自拥有的卡牌数量。保证 $ n $ 是偶数。 第二行包含 $ n $ 个正整数 $ a_{1},a_{2},...,a_{n} $（$ 1 \leq a_{i} \leq 10^{9} $）——表示 Eugeny 卡牌上的数字。

如果无解，输出 $-1$。 否则，第一行输出最少交换的次数。 第二行输出 $ n $ 个整数，表示经过交换后 Eugeny 手中的 $ n $ 张卡的数字。卡牌顺序应与输入中卡牌的顺序一致。如果第 $ i $ 张卡未被交换，则第 $ i $ 个数应与输入数据中的数字相同；如果第 $ i $ 张卡被交换，则第 $ i $ 个数应为交换得到的数字。 如果有多组答案，可以输出其中任意一组。

由 ChatGPT 5 翻译