題干：

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·105,?1?≤?m?≤?109)?— 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?a1,?a2,?...,?an?(1?≤?ai?≤?109)?— 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

題目大意：

尤金有?n?張卡片。每張卡片上都有一個(gè)整數(shù)。 尤金希望與尼古拉交換一些卡片，使得他的偶數(shù)卡片上的數(shù)量等于奇數(shù)卡片的數(shù)量，并且所有這些數(shù)字不同的。

尼古拉有?m?張卡，上面的數(shù)字為?1?到?m?，也就是每種數(shù)字的卡各一張。

每次兩人可以交換一張卡，問(wèn)最少交換幾次可以滿足尤金的要求。

Input

第一行包含兩個(gè)整數(shù)?n?和?m?(2?≤?n?≤?2·105,?1?≤?m?≤?109)?— 分別表示兩人擁有的卡片數(shù)。 保證?n?是偶數(shù)。

第二行包含一個(gè)由?n?個(gè)正整數(shù)組成的數(shù)列?a1,?a2,?...,?an?(1?≤?ai?≤?109)?— 表示尤金的卡。

Output

如果沒有答案，輸出?-1.

否則，在第一行輸出最小需要換的卡片數(shù)。在第二行輸出?n?個(gè)整數(shù)?— 交換后尤金的卡牌。 卡牌的順序要和讀入時(shí)一樣，如果有多種方案，輸出任意一種。

解題報(bào)告：

先預(yù)處理出來(lái)在<=m的前提下有多少奇數(shù)和偶數(shù)可以使用，然后先保證能不變的先不變（打個(gè)ok標(biāo)記），剩下的貪心填。注意一下貪心的順序，并且時(shí)刻注意填的數(shù)要<=m這個(gè)限制就好。

注意一定要先保證能不變的就不變，不然的話你不確定后面已經(jīng)有多少奇數(shù)偶數(shù)了，那么就不能確定這一位優(yōu)先填奇數(shù)還是偶數(shù)，所有有可能操作次數(shù)不是最少的。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 6e5 + 5; ll n,m,ji,ou,resji,resou,needji,needou; ll a[MAX]; set<ll> sji,sou,ans; bool vis[MAX],ok[MAX]; vector<int> o,j; int main() {cin>>n>>m;if(m&1) resou=m/2,resji=resou+1;else resou=resji=m/2;for(int i = 1; i<=n; i++) { scanf("%lld",a+i);if(a[i] < MAX) vis[a[i]]=1;if(a[i]&1) {ji++;if(a[i] <= m && sji.find(a[i]) == sji.end()) resji--;sji.insert(a[i]);}else {ou++;if(a[i] <= m && sou.find(a[i]) == sou.end()) resou--;sou.insert(a[i]);}}ll bij = n/2-sji.size();//必須要去掉的奇數(shù)，準(zhǔn)確的說(shuō)，是還需要換上的奇數(shù)，還缺少的奇數(shù)ll bio = n/2-sou.size();//必須要去掉的偶數(shù)if(resji < bij || resou < bio) return 0,puts("-1");ll tmp = max(bij,0LL)+max(bio,0LL);printf("%lld\n",tmp);for(int i = 2; i<=min(m,1LL*MAX-1); i+=2) {if(vis[i]) continue;o.pb(i);}for(int i = 1; i<=min(m,1LL*MAX-1); i+=2) {if(vis[i]) continue;j.pb(i);}ll curji=0,curou=0;for(int i = 1; i<=n; i++) {if(ans.count(a[i])) continue;ans.insert(a[i]);if((a[i]&1) && curji < n/2) curji++,ok[i]=1;else if((a[i]&1)==0 && curou<n/2)curou++,ok[i]=1;}for(int i = 1; i<=n; i++) {if(ok[i]) {continue;}if(a[i]&1) {//如果是奇數(shù)if(ans.count(a[i])) {if(curji < n/2) a[i]=j.back(),j.pop_back(),curji++;else if(curou < n/2) a[i] = o.back(),o.pop_back(),curou++;}else {if(curji < n/2) ans.insert(a[i]),curji++;else a[i] = o.back(),o.pop_back(),curou++;}}else {if(ans.count(a[i])) {if(curji < n/2) a[i]=j.back(),j.pop_back(),curji++;else if(curou < n/2) a[i] = o.back(),o.pop_back(),curou++;}else {if(curou < n/2) ans.insert(a[i]),curou++;else a[i] = j.back(),j.pop_back(),curji++;}}}for(int i = 1; i<=n; i++) printf("%lld ",a[i]);return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 746E】Numbers Exchange（贪心构造）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。