सबस्ट्रिंग पथ
Problem
n शीर्षों और m निर्देशित किनारों का ग्राफ़ दिया गया है। प्रत्येक शीर्ष में कुछ लोअरकेस लैटिन अक्षर होते हैं।
आइए किसी पथ की लंबाई को उस सबसे बड़ी संख्या के रूप में परिभाषित करें, जब इस पथ पर किसी अक्षर का सामना हुआ हो। उदाहरण के लिए, यदि पथ के अक्षर स्ट्रिंग "अबका" बनाते हैं, तो इस पथ का मान 3 है।
आपका कार्य — सबसे बड़े मान वाला पथ खोजें।
इनपुट:
पहली पंक्ति में दो पूर्णांक n, m (1 ≤ n, m ≤ 200000) हैं, जिसका अर्थ है कि ग्राफ़ में n कोने और m निर्देशित किनारे हैं।
दूसरी पंक्ति में स्ट्रिंग एस है, जिसमें केवल लोअरकेस लैटिन अक्षर हैं। प्रतीक संख्या i — यह सबसे ऊपर वाले नंबर i.
पर लिखा हुआ अक्षर है
फिर एम लाइन का पालन करें। इन पंक्तियों में से प्रत्येक में दो पूर्णांक x, y (1 ≤ x, y ≤ n) हैं जो x से y तक एक निर्देशित किनारे का वर्णन करते हैं। ध्यान दें कि x, y के बराबर हो सकता है, और x और y के बीच कई किनारे हो सकते हैं।
इसके अलावा, ग्राफ़ डिस्कनेक्ट हो सकता है।
आउटपुट:
एक नंबर प्रिंट करें — अधिकतम पथ लंबाई। यदि मनमाने ढंग से बड़े मान वाले पथ हैं, तो -1 प्रिंट करें।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
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
xzyzyzyzqx
1 2
24
3 5
4 5
26
68
6 5
2 10
39
10 9
46
1 10
28
37 |
4 |