부분 문자열

n개의 노드와 m개의 유향 간선으로 이루어진 그래프가 주어진다. 각 노드에는 영문 소문자 하나가 할당되어 있다. 경로의 값은 그 경로에서 가장 자주 등장하는 문자의 등장 횟수로 정의한다. 예를 들어, 경로 위의 문자들이 "abaca"라면 그 경로의 값은 3이다. 값이 가장 큰 경로를 찾는 것이 과제이다.

첫 번째 줄에는 두 양의 정수 n, m (1 ≤ n, m ≤ 300 000)가 주어지며, 이는 그래프에 n개의 노드와 m개의 유향 간선이 있음을 나타낸다.

두 번째 줄에는 영문 소문자로만 이루어진 문자열 s가 주어진다. i-th 문자는 i-th 노드에 할당된 문자이다.

이어서 m개의 줄이 주어진다. 각 줄에는 두 정수 x, y (1 ≤ x, y ≤ n)가 주어지며, x에서 y로 향하는 유향 간선을 나타낸다. x는 y와 같을 수 있으며, x와 y 사이에 여러 간선이 있을 수 있음에 유의한다. 또한 그래프는 연결되어 있지 않을 수도 있다.

가장 큰 값을 나타내는 정수 하나를 한 줄에 출력한다. 값이 임의로 커질 수 있다면 대신 -1을 출력한다.

첫 번째 예제에서 값이 가장 큰 경로는 1 → 3 → 4 → 5이다. 문자 'a'가 3번 등장하므로 값은 3이다.