D. Федор ба эссе

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

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

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

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

Чи Федор ба түүний найзуудад «Call of Soldiers 3» тоглоомыг олоход нь тусалснаас хойш тэр хичээл хийхээ нэг мөсөн больсон. Өнөөдөр англи хэлний багш нь түүнийг эссе бэлдэж ир гэсэн. Федор эссе бэлдэхийг хүсэхгүй байсан учраас Алексаас тусламж хүссэн. Алекс туслахаар болж Федорт эссе бичиж өгсөн боловч энэ эссе нь тэр чигээрээ Федорт таалагдсангүй. Одоо Федор Англи хэлний ойролцоо үгийн толь ашиглаж эссег өөрчлөх гэж байна.

Федор эссений утгыг өөрчлөхийг хүссэнгүй. Тиймээс тэр эссений зөвхөн ойролцоо утгатай үгүүдийг толь бичгийн үг орлуулах дүрэмд суурилж үгнүүдийг өөрчилсөн. Федор энэ үйлдлийг хэдэн ч удаа хийж болно.

Үр дүнд Федор аль болох «$R$» (шалтгаан нь чухал биш) жижиг үсэгнүүд агуулсан эссе авахыг хүсэж байна. Хэрвээ олон эссенд «$R$»-н хамгийн бага тоо байгаа бол тэр хамгийн бага урттайг нь авна (эссений урт гэдэг нь бүх үгнүүдийн уртын нийлбэр). Шаардсан эссег олоход нь тусал.

Энэ асуудалд үсэгнүүдийн нөхцөл нь чухал биш болохыг анхаарна уу. Жишээлбэл хэрвээ ойролцоо үгийн толь бичигт $cat$ гэдэг үгийг $DOG$ гэж сольж болно, дараа нь $doG$ гэсэн үгийг $Cat$ үг болгож солих эрхтэй.

Оролт

Эхний мөрөнд анхны эссений үгийн тоо болох нэг бүхэл тоо $m$ $(1 ≤ m ≤ 10^{5})$ агуулагдана. Дараагийн мөрөнд эссений үгнүүд байна. Үгнүүд нь нэг зайгаар тусгаарлагдсан байна. Үгийн урт нь $10^{5}$ тэмдэгтээс хэтрэхгүй байх ёстой.

Дараагийн мөрөнд ойролцоо үгийн толь бичгийн хос үгийн тоо $n$ $(0 ≤ n ≤ 10^{5})$ тоо байна. Дараагийн $n$ мөрийн $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $x_{i}$ ба $y_{i}$ байна. Энэ нь $x_{i}$ үгийг $y_{i}$ үгээр сольж болно гэсэн утгатай (эсрэгээрээ болохгүй). Ойролцоо бүх хосуудын уртын нийлбэр нь $5*10^{5}$ тэмдэгтээс хэтрэхгүй.

Оролтын бүх үгнүүд нь Англи хэлний цагаан толгойн том ба жижиг үсэгнүүд агуулна.

Гаралт

Хоёр бүхэл тоо хэвлэнэ. Оновчтой эссений «$R$» үсэгний хамгийн бага тоо ба оновчтой эссений хамгийн бага урт.

Орчуулсан: Даариймаа

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

Оролт
3
AbRb r Zz
4
xR abRb
aA xr
zz Z
xr y
Гаралт
2 6
Оролт
2
RuruRu fedya
1
ruruRU fedor
Гаралт
1 10
Сэтгэгдлүүдийг ачааллаж байна...