Перефарбовування паркану#2344
Є паркан з дощок, кожна з яких пофарбована у певний колір. Деякі пари кольорів є несумісними. Якщо дві сусідні дошки пофарбовані у несумісні кольори, такий паркан не вважається гарним. Паркан вважається гарним, якщо жодної такої несумісності немає. Щоб виправити ситуацію, дозволяється перефарбовувати деякі дошки, але лише в такий колір, який не несумісний з поточним кольором цієї дошки.
Напишіть програму для перефарбовування паркану так, щоб він став гарним.
Перший рядок містить два цілі числа та — кількість дощок у паркані та кількість пар несумісних кольорів відповідно (1 \leq N \leq 10^5, 0 \leq K \leq 1000).
Кожен із наступних рядків містить пару цілих чисел, що означає несумісні кольори. Усі кольорів у цих парах різні.
Останній рядок містить цілих чисел, які задають початкові кольори дощок у паркані. Кольори представлені цілими числами від до .
У першому рядку виведіть мінімальну кількість перефарбувань, потрібних для створення гарного паркану. У другому рядку виведіть цілих чисел — фінальні кольори паркану.
Приклад 1