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