Masala E
Yo'l xaritasi
Yilning ikkinchi yarmida akademiyadagi mashg'ulotlar oddiy dars bo'lib qolmadi. O'quvchilar uchun to'liq yo'l xaritasi tuzildi: qaysi darsdan keyin qaysi kontestga kirish, qaysi kontestdan keyin qaysi tahlilni ko'rish kerakligi oldindan belgilab qo'yilardi. Bu tartib buzilsa, o'quvchi ko'p material ko'radi, lekin ularni kerakli paytda bog'lay olmaydi.
\(n\) ta modul bor. Har bir modulning turi D, K yoki T:
D- dars;K- contest;T- tahlil.
Shuningdek, \(m\) ta yo'naltirilgan o'tish berilgan. Har bir o'tish \(u \to v\) ko'rinishida va doim \(u < v\), ya'ni yo'l xaritasida orqaga qaytish yo'q.
Yo'l deb har bir qo'shni juftligi berilgan o'tishlar bilan bog'langan modullar ketma-ketligi \(v_1 \to v_2 \to \cdots \to v_t\) ga aytamiz. Bitta moduldan iborat ketma-ketlik \((t=1)\) ham yo'l hisoblanadi.
Yo'l yaxshi deyiladi, agar undagi ketma-ket kelgan har ikki modulning turi turlicha bo'lsa. Yo'l boshlanishidan oldin ustoz shu yo'ldagi ko'pi bilan bitta modulning turini istalgan boshqa turga almashtirib berishi mumkin. Masalan, bitta D modulini K yoki T qilish mumkin.
Eng uzun yaxshi yo'l nechta moduldan iborat bo'lishi mumkin?
Birinchi qatorda ikkita butun son \(n\) va \(m\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 0 \le m \le 2 \cdot 10^5)\).
Ikkinchi qatorda uzunligi \(n\) ga teng \(s\) satri beriladi. Har bir belgi D, K yoki T bo'ladi va mos modulning turini bildiradi.
Keyingi \(m\) qatorda ikkitadan butun son \(u\) va \(v\) beriladi \((1 \le u < v \le n)\). Bu \(u\)-moduldan \(v\)-modulga o'tish mumkinligini bildiradi.
Ko'pi bilan bitta modul turini almashtirishdan keyin olinishi mumkin bo'lgan eng uzun yaxshi yo'ldagi modullar sonini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 4 DDKTT 1 2 2 3 3 4 4 5 |
4 |
| 2 |
4 3 DDDD 1 2 2 3 3 4 |
3 |
| 3 |
3 0 DKT |
1 |
Birinchi namunada \(2 \to 3 \to 4 \to 5\) yo'lini olish mumkin. Bu yo'ldagi turlar D, K, T, T. Oxirgi modulning turi D ga almashtirilsa, turlar D, K, T, D bo'ladi va har bir qo'shni juftlikda turlar farqli bo'ladi. Demak, \(4\) ta moduldan iborat yaxshi yo'l bor.
Ikkinchi namunada, masalan, \(1 \to 2 \to 3\) yo'lini olib, \(2\)-modulning turini K ga almashtirish mumkin. Shunda turlar D, K, D bo'ladi. \(4\) ta modulli yo'lda esa bitta almashtirish yetmaydi.
Uchinchi namunada hech qanday o'tish yo'q, shuning uchun har qanday yo'l bitta moduldan iborat.
Telegram kanalimizga obuna bo'ling