← 返回题目列表

Codeforces · 746/E

E. 号码交换

中文机器翻译题面 查看原题

尤金尼有 n 张卡片,每张卡片上都写着一个整数。尤金尼想与尼古拉交换一些卡片,以便他的卡片上偶数整数的数量等于奇数整数的数量,并且所有这些数字都是不同的。

尼古拉有 m 张卡片,上面写着从 1 到 m 的不同数字,每张卡片一张。这意味着尼古拉恰好有一张数字为 1 的牌,也恰好有一张数字为 2 的牌,依此类推。

单次交换是指尤金尼将一张卡片交给尼古拉并从尼古拉拥有的卡片中取出另一张卡片的过程。您的任务是找到最少交换卡片的次数,并确定尤金妮应该交换哪些卡片。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 2·105, 1 ≤ m ≤ 109) - Eugeny 拥有的牌数和 Nikolay 拥有的牌数。保证n是偶数。

第二行包含 n 个正整数 a1, a2, ..., an (1 ≤ ai ≤ 109) 的序列——Eugeny 卡片上的数字。

输出

如果没有答案,则打印-1。

否则,在第一行打印最小交换次数。在第二行中打印 n 个整数——在与 Nikolay 进行所有交换后 Eugeny 的卡片。卡片的顺序应与输入数据中卡片的顺序一致。如果第 i 张卡没有被交换,那么第 i 个号码应该与输入数据中的号码一致。否则,认为这张卡被交换了,第i个数字应该等于被交换的卡上的数字。

如果有多个答案,则可以打印其中任意一个。

示例

输入 #1

6 2
5 6 7 9 4 5

输出 #1

1
5 6 7 9 4 2

输入 #2

8 6
7 7 7 7 8 8 8 8

输出 #2

6
7 2 4 6 8 1 3 5

输入 #3

4 1
4 2 1 10

输出 #3

-1