Problem
Soit un graphe de n sommets et m arêtes dirigées. Chaque sommet contient une lettre latine minuscule.
Définissons la longueur d'un chemin comme le plus grand nombre de fois qu'une lettre a été rencontrée le long de ce chemin. Par exemple, si les lettres du chemin forment la chaîne "abaca", alors la valeur de ce chemin est 3.
Votre tâche — trouver le chemin avec la plus grande valeur.
Saisie :
La première ligne contient deux entiers n, m (1 ≤ n, m ≤ 200000), ce qui signifie que le graphe a n sommets et m arêtes orientées.
La deuxième ligne contient la chaîne s, composée uniquement de lettres latines minuscules. Numéro de symbole i — c'est la lettre écrite en haut du chiffre i.
Puis m lignes suivent. Chacune de ces lignes contient deux entiers x, y (1 ≤ x, y ≤ n) décrivant une arête dirigée de x vers y. Notez que x peut être égal à y et qu'il peut y avoir plusieurs arêtes entre x et y.
De plus, le graphique peut être déconnecté.
Sortie :
Imprimer un numéro — la longueur maximale du trajet. S'il existe des chemins avec une valeur arbitrairement grande, imprimez -1.
Exemples :
| Entrée |
Sortie |
5 4
abaque
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 |