Repainting the Fence
There is a fence made up of N 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 incompatible with the current color of the plank.
Write a program to repaint the fence so that it becomes beautiful.
Input
The first line contains two integers, N and K—representing the number of planks in the fence and the number of incompatible color pairs, respectively (1 ≤ N ≤ 10^5, 0 ≤ K ≤ 1000). Each of the following K lines contains a pair of integers indicating incompatible colors. All 2K colors in these K pairs are distinct. The last line contains N integers that specify the initial colors of the planks in the fence. Colors are represented by integers ranging from 1 to 10000.
Output
On the first line, output the minimum number of repaints required to make the fence beautiful. On the second line, output N integers that represent the final colors of the fence.