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