C. Тэд хаа сайгүй

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

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

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

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

Сергей Б. нь Покемоны залуу дасгалжуулагч бөгөөд зүүнээс баруун уруу дугаарлагдсан $n$ хэсгээс бүрдсэн том байшин уруу орох шаардлагатай болжээ. Хэсэг болгон уруу гудамжнаас орох боломжтой бөгөөд хэсэг болгоноос гудамж уруу гарах боломжтой. Үүнээс гадна хэсэг болгон зүүн болон баруун талын 2 хэсэгтэй холбогдсон. $1$ дугаартай хэсэг зөвхөн $2$ хэсэгтэй холбогдсон. $n$ дугаартай хэсэг завхан $n - 1$ дугаартай хэсэгтэй холбогдсон.

Хэсэг болгонд ямар нэг төрлийн зөвхөн нэг покемон байгаа. Сергэй Б. байшингийн оршин суугчдаас покемоныг барихын тулд оруулахыг гуйжээ. Оршин суугчид хэлэлцсэний эцэст Сергей Б.-г гудамжнаас нэг удаа орж хэд хэдэн хэсэгээр зочлон дараа нь аль нэг хэсгээс гарахыг зөвшөөрчээ. Гэвч тэд нэг ижил хэсэг уруу дахин орохыг хоригложээ.

Сергей Б. ихэд баярласан бөгөөд одоо тэрээр бүх төрлийн покемоноос цуглуулж хамгийн цөөн тооны хэсгээр дамжихыг хүсч байгаа. Таны даалгавар бол түүнд туслаж хамгийн багадаа хэдэн хэсгээр дамжих ёстойг хэлж өгөх юм.

Оролт

Эхний мөрөнд байшингийн нийт хэсгийн тоо болох $n$ ($1 ≤ n ≤ 100 000$) бүхэл тоо өгөгдөнө.

Дараагийн мөрөнд $n$ урттай $s$ тэмдэгт мөр байрлана. Энэ мөр нь Англи цагаан толгойн том бөгөөд жижиг хэсгээс бүрдэнэ. $i$ дэхь үсэг нь $i$ дэхь хэсэгт байгаа Покемоны төрлийг заана.

Гаралт

Сергей Б. байшин дахь бүх төрлийн Покемоныг барихын тулд хамгийн багадаа хэдэн хэсгээр зочлох хэрэгтэй вэ? Энэ тоог хэвлэнэ үү.

Орчуулсан: Энхлут

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

Оролт
3
AaA
Гаралт
2
Оролт
7
bcAAcbc
Гаралт
3
Оролт
6
aaBCCe
Гаралт
5

Тэмдэглэл

Эхний жишээнд Сергей Б. $1$ хэсгээс эхлэн $2$ хэсгээс гарч болно.

2 дахь жишээнд Сергей Б. $4$ хэсгээс эхлэн $6$ хэсгээс гарч болно.

3 дахь жишээнд Сергей Б. $2$ хэгсээс эхлэн $6$ хэсгээс гарах ёстой.

Сэтгэгдлүүдийг ачааллаж байна...