Hasarın rənglənməsi
Є bir hasar var ki, N taxtadan ibarətdir və hər biri müəyyən bir rəngə boyanıb. Bəzi rəng cütləri bir-biri ilə uyğunsuzdur. Əgər hasarın hər hansı bir qonşu taxtası uyğunsuz rənglərə boyanarsa (yəni bu taxtaların boyandığı rəng cütü uyğunsuzdursa), o zaman hasar gözəl hesab edilə bilməz. Əgər heç bir yerdə uyğunsuzluq müşahidə olunmazsa, hasar gözəl hesab olunur. Uyğunsuzluqları aradan qaldırmaq üçün bəzi taxtaları yenidən boyamaq icazəlidir, lakin yalnız əks rəngə (yəni taxtanın verilmiş rənginə uyğunsuz olan rəngə) boyamaq olar.
Hasarı gözəl etmək üçün yenidən boyama işini yerinə yetirən bir proqram yazın.
Giriş verilənləri
Birinci sətirdə hasarın taxtalarının sayı və uyğunsuz rəng cütlərinin sayı olan iki tam ədəd N və K verilir (1 ≤ N ≤ 10^5, 0 ≤ K ≤ 1000). Növbəti K sətirdə uyğunsuz rəngləri müəyyən edən cüt tam ədədlər var. Bu K cütlükdəki bütün 2K rəng fərqlidir. Sonuncu sətirdə hasarın müvafiq taxtalarının əvvəlcə boyandığı rəngləri müəyyən edən N tam ədəd var. Rənglər 1 ilə 10000 arasında olan tam ədədlərlə verilir.
Çıxış verilənləri
Birinci sətirdə hasarın gözəl olması üçün lazım olan minimum yenidən boyama sayını çıxarın. İkinci sətirdə hasarın son boyanmasını müəyyən edən N tam ədəd çıxarın.