Hasarın rənglənməsi#2344
Bir hasar var və bu hasar taxtadan ibarətdir, onların hər biri müəyyən bir rəngə boyanıb. Bəzi rəng cütlükləri bir-biri ilə uyğun gəlmir. Əgər hər hansı iki qonşu taxta uyğun gəlməyən rənglərə boyanıbsa, hasar gözəl sayılmır. Hasar yalnız o halda gözəl sayılır ki, belə uyğunsuzluq olmasın. Bu problemi həll etmək üçün bəzi taxtaları yenidən boyamağa icazə verilir, amma yalnız həmin taxtanın indiki rəngi ilə uyğun gələn bir rənglə boyamaq olar.
Hasarı gözəl etmək üçün bir proqram yazın.
Birinci sətirdə hasardakı taxtaların sayı və uyğunsuz rəng cütlərinin sayı olan iki tam ədəd və verilir, 1 \leq N \leq 10^5, 0 \leq K \leq 1000.
Sonrakı sətrin hər birində uyğun gəlməyən iki rəngin cütlüyü verilir. Bu cütlükdə olan bütün rəng müxtəlifdir.
Sonuncu sətirdə hasardakı taxtaların ilkin rənglərini əks etdirən tam ədəd verilir. Rənglər -dən -ə qədər olan tam ədədlərlə ifadə olunub.
Birinci sətirdə hasarı gözəl etmək üçün lazım olan minimal yenidən boyama sayını çıxışa verin. İkinci sətirdə isə hasar üçün sonuncu rəng düzülüşünü göstərən tam ədəd çıxışa verin.
Nümunə 1