Repainting the Fence#2344
There is a fence made up of planks, each painted in a specific color. Some color pairs are incompatible with each other. If any two adjacent planks are painted in incompatible colors, the fence is not considered beautiful. A fence is deemed beautiful if no such incompatibilities exist. To resolve these issues, you are allowed to repaint some planks, but only with a color that is not incompatible with the current color of the plank.
Write a program to repaint the fence so that it becomes beautiful.
The first line contains two integers, and , representing the number of planks in the fence and the number of incompatible color pairs, respectively (1 \leq N \leq 10^5, 0 \leq K \leq 1000).
Each of the following lines contains a pair of integers indicating incompatible colors. All colors in these pairs are distinct.
The last line contains integers that specify the initial colors of the planks in the fence. Colors are represented by integers ranging from to .
On the first line, output the minimum number of repaints required to make the fence beautiful. On the second line, output integers that represent the final colors of the fence.
Example 1