مسار السلسلة الفرعية
Problem
إعطاء رسم بياني للرؤوس n والحواف الموجهة m. يحتوي كل رأس على بعض الأحرف اللاتينية الصغيرة. & nbsp؛
دعنا نحدد طول المسار على أنه أكبر عدد من المرات التي تم فيها مواجهة حرف ما على طول هذا المسار. على سبيل المثال ، إذا كانت الأحرف الموجودة في المسار تشكل السلسلة "أباكا" ، فإن قيمة هذا المسار هي 3.
مهمتك و [مدش]. أوجد المسار ذي القيمة الأكبر.
الإدخال:
يحتوي السطر الأول على عددين صحيحين n، m (1 & le؛ n، m & le؛ 200000) ، مما يعني أن الرسم البياني له رؤوس n وحواف m موجهة.
يحتوي السطر الثاني على السلسلة s ، التي تتكون فقط من أحرف لاتينية صغيرة. رقم الرمز i & [مدش] ؛ هذا هو الحرف المكتوب في أعلى رقم ط.
ثم تتبع خطوط م. يحتوي كل سطر من هذه الأسطر على عددين صحيحين x، y (1 & le؛ x، y & le؛ n) يصفان حافة موجهة من x إلى y. لاحظ أن x يمكن أن يساوي y ، ويمكن أن يكون هناك عدة حواف بين x و y.
بالإضافة إلى ذلك ، قد يكون الرسم البياني غير متصل.
الإخراج:
طباعة رقم واحد و [مدش] ؛ أقصى طول للمسار. إذا كانت هناك مسارات ذات قيمة كبيرة بشكل عشوائي ، فقم بطباعة -1.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
5 4
أباكا
1 2
1 3
34
4 5 |
3 |
6 6
xzyabc
1 2
3 1
23
5 4
4 3
6 4 |
-1 |
10 14
زيزيزيزقكس
1 2
24
3 5
4 5
26
68
6 5
2 10
39
10 9
46
1 10
28
37 |
4 |