Problem
Given a graph of n vertices and m directed edges. Each vertex contains some lowercase Latin letter.
Let's define the length of a path as the largest number of times that some letter was encountered along this path. For example, if the letters in the path form the string "abaca", then the value of this path is 3.
Your task — find the path with the largest value.
Input:
The first line contains two integers n, m (1 ≤ n, m ≤ 200000), meaning that the graph has n vertices and m directed edges.
The second line contains the string s, consisting only of lowercase Latin letters. Symbol number i — this is the letter written at the top number i.
Then m lines follow. Each of these lines contains two integers x, y (1 ≤ x, y ≤ n) describing a directed edge from x to y. Note that x can be equal to y, and there can be multiple edges between x and y.
In addition, the graph may be disconnected.
Output:
Print one number — the maximum path length. If there are paths with an arbitrarily large value, print -1.
Examples:
| Input |
Output |
5 4
abaca
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 |