C. Өнгөт зураас

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Өнгөт зураас гэдэг нь $k$ өнгөний аль нэгээр нь будагдсан нийт $n$ ширхэг дараалсан будагдсан нүд юм. Таны даалгавар бол аль ч хоёр хөрш нүдний өнгө ялгаатай байхаар хамгийн цөөн дахин будалт хийх юм. Та будалт хийхдээ $1$-c $k$-н хоорондох өнгийг ашиглаж болно.

Оролт

Эхний мөрөнд $n$, $k$ ($1 ≤ n ≤ 5·10^5$; $2 ≤ k ≤ 26$) тоо өгөгдөнө. Дараагийн мөрөнд нийт $n$ ширхэг латин цагаан толгойн том үсэг өгөгдөнө. Энд "A" үсэг эхний өнгийг, "B" үсэг дараагийн өнгийг гэх мэтээр өнгүүдийг илэрхийлнэ. Энд эхний $k$ үсэг л хэрэглэгдсэн байх юм. Үсэг бүр харгалзах нүднийхээ өнгийг илэрхийлнэ.

Гаралт

Эхний мөрөнд хамгийн цөөн дахин будалтын тоог, дараагийн мөрөнд ямар ч хамаагүй боломжит будалтыг хэвлэ.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
6 3
ABBACC
Гаралт
2
ABCACA
Оролт
3 2
BBB
Гаралт
1
BAB
Сэтгэгдлүүдийг ачааллаж байна...