У Евгения есть n карточек, на каждой из которых написано ровно одно целое число. Евгений хочет поменяться с Николаем некоторыми карточками так, чтобы количество четных чисел на его карточках стало равно количеству нечетных чисел на его карточках, при этом все числа стали различными.
У Николая есть m карточек, на которых написаны различные числа от 1 до m, то есть у Николая есть ровно одна карточка, на которой написано число 1, ровно одна карточка, на которой написано число 2 и так далее.
Назовем обменом процесс, в котором Евгений отдает одну из своих карт Николаю, и берет у него одну другую карту. Перед вами стоит задача найти минимальное количество обменов карт, а также определить какие на какие карточки нужно обменивать Евгению.
Выходные данные
Если ответа не существует, выведите -1.
В противном случае, в первую строку выведите минимальное количество обменов. Во вторую строку выведите n чисел — карточки Евгения после обмена с Николаем. Порядок карточек должен совпадать с порядком карт из входных данных. Если i-я карточка не обменивалась, то i-е число должно совпадать с числом из входных данных. В противном случае, будет считаться, что эта карточка была поменяна, и i-е число должно равняться числу на карточке, на которую она была поменяна.
Если ответов несколько, разрешается вывести любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
5 6 7 9 4 5
|
1
5 6 7 9 4 2
|
|
2
|
8 6
7 7 7 7 8 8 8 8
|
6
7 2 4 6 8 1 3 5
|
|
3
|
4 1
4 2 1 10
|
-1
|