Problem
Dado um gráfico de n vértices e m arestas direcionadas. Cada vértice contém alguma letra latina minúscula.
Vamos definir o comprimento de um caminho como o maior número de vezes que alguma letra foi encontrada nesse caminho. Por exemplo, se as letras do caminho formam a string "abaca", então o valor desse caminho é 3.
Sua tarefa — encontre o caminho com o maior valor.
Entrada:
A primeira linha contém dois inteiros n, m (1 ≤ n, m ≤ 200000), significando que o grafo tem n vértices e m arestas direcionadas.
A segunda linha contém a string s, consistindo apenas em letras latinas minúsculas. Símbolo número i — esta é a letra escrita no topo do número i.
Em seguida, seguem-se m linhas. Cada uma dessas linhas contém dois inteiros x, y (1 ≤ x, y ≤ n) descrevendo uma aresta direcionada de x para y. Observe que x pode ser igual a y e pode haver várias arestas entre x e y.
Além disso, o grafo pode ser desconectado.
Saída:
Imprima um número — o comprimento máximo do caminho. Se houver caminhos com um valor arbitrariamente grande, imprima -1.
Exemplos:
| Entrada |
Saída |
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 |