У Евгения есть n карточек, на каждой из которых написано ровно одно целое число. Евгений хочет поменяться с Николаем некоторыми карточками так, чтобы количество четных чисел на его карточках стало равно количеству нечетных чисел на его карточках, при этом все числа стали различными.
У Николая есть m карточек, на которых написаны различные числа от 1 до m, то есть у Николая есть ровно одна карточка, на которой написано число 1, ровно одна карточка, на которой написано число 2 и так далее.
Назовем обменом процесс, в котором Евгений отдает одну из своих карт Николаю, и берет у него одну другую карту. Перед вами стоит задача найти минимальное количество обменов карт, а также определить какие на какие карточки нужно обменивать Евгению.
В первой строке следуют два целых числа n и m (2 ≤ n ≤ 2·105, 1 ≤ m ≤ 109) — количество карточек у Евгения и количество карточек у Николая. Гарантируется, что n четно.
Во второй строке следует последовательность из n целых положительных чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — числа на карточках Евгения.
Если ответа не существует, выведите -1.
В противном случае, в первую строку выведите минимальное количество обменов. Во вторую строку выведите n чисел — карточки Евгения после обмена с Николаем. Порядок карточек должен совпадать с порядком карт из входных данных. Если i-я карточка не обменивалась, то i-е число должно совпадать с числом из входных данных. В противном случае, будет считаться, что эта карточка была поменяна, и i-е число должно равняться числу на карточке, на которую она была поменяна.
Если ответов несколько, разрешается вывести любой из них.
6 2
5 6 7 9 4 5
1
5 6 7 9 4 2
8 6
7 7 7 7 8 8 8 8
6
7 2 4 6 8 1 3 5
4 1
4 2 1 10
-1
| Codeforces Round 386 (Div. 2) |
|---|
| Закончено |
