Имеется забор, состоящий из \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} целых чисел, определяющих окончательную покраску забора.