Problem
نموداری از n رأس و m یال جهت دار داده می شود. هر رأس حاوی حروف کوچک لاتین است.
بیایید طول یک مسیر را به عنوان بیشترین تعداد دفعاتی که با حروفی در این مسیر مواجه شده است تعریف کنیم. به عنوان مثال، اگر حروف موجود در مسیر رشته "آباکا" را تشکیل دهند، مقدار این مسیر 3 است.
وظیفه شما — مسیر با بیشترین مقدار را پیدا کنید.
ورودی:
خط اول شامل دو عدد صحیح n, m (1 ≤ n, m ≤ 200000) است، به این معنی که نمودار دارای n راس و m یال جهت دار است.
خط دوم شامل رشته s است که فقط از حروف کوچک لاتین تشکیل شده است. شماره نماد i — این حرفی است که در بالای شماره i نوشته شده است.
سپس خطوط m دنبال می شوند. هر یک از این خطوط شامل دو عدد صحیح x, y (1 ≤ x, y ≤ 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
xzyzyzyzqx
1 2
24
3 5
4 5
26
68
6 5
2 10
39
10 9
46
1 10
28
37 |
4 |