Problem
Dado un gráfico de n vértices y m aristas dirigidas. Cada vértice contiene alguna letra latina minúscula.
Definamos la longitud de un camino como el mayor número de veces que se encontró alguna letra a lo largo de este camino. Por ejemplo, si las letras en la ruta forman la cadena "abaca", entonces el valor de esta ruta es 3.
Tu tarea: encuentre la ruta con el valor más grande.
Entrada:
La primera línea contiene dos números enteros n, m (1 ≤ n, m ≤ 200000), lo que significa que el gráfico tiene n vértices y m aristas dirigidas.
La segunda línea contiene la cadena s, que consta solo de letras latinas en minúsculas. Símbolo número i — esta es la letra escrita en la parte superior del número i.
Luego siguen m líneas. Cada una de estas líneas contiene dos números enteros x, y (1 ≤ x, y ≤ n) que describen un borde dirigido de x a y. Tenga en cuenta que x puede ser igual a y, y puede haber varios bordes entre x e y.
Además, el gráfico puede estar desconectado.
Salida:
Imprimir un número — la longitud máxima del camino. Si hay rutas con un valor arbitrariamente grande, imprima -1.
Ejemplos:
| Entrada |
Salida |
5 4
abacá
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 |