Problem
Dato un grafico di n vertici e m archi orientati. Ogni vertice contiene una lettera latina minuscola.
Definiamo la lunghezza di un percorso come il maggior numero di volte in cui una lettera è stata incontrata lungo questo percorso. Ad esempio, se le lettere nel percorso formano la stringa "abaca", il valore di questo percorso è 3.
Il tuo compito — trova il percorso con il valore più grande.
Inserimento:
La prima riga contiene due numeri interi n, m (1 ≤ n, m ≤ 200000), il che significa che il grafo ha n vertici e m archi orientati.
La seconda riga contiene la stringa s, composta solo da lettere latine minuscole. Simbolo numero i — questa è la lettera scritta in alto numero i.
Quindi seguono m linee. Ognuna di queste righe contiene due numeri interi x, y (1 ≤ x, y ≤ n) che descrivono un arco orientato da xa y. Nota che x può essere uguale a y e possono esserci più archi tra x e y.
Inoltre, il grafico potrebbe essere disconnesso.
Uscita:
Stampa un numero — la lunghezza massima del percorso. Se ci sono percorsi con un valore arbitrariamente grande, print -1.
Esempi:
| Input |
Uscita |
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 |