Problem
n 꼭짓점과 m 방향 모서리의 그래프가 주어집니다. 각 정점에는 소문자 라틴 문자가 포함되어 있습니다.
경로의 길이를 이 경로를 따라 어떤 문자가 발견된 최대 횟수로 정의해 봅시다. 예를 들어 경로의 문자가 문자열 "abaca"를 형성하는 경우 이 경로의 값은 3입니다.
귀하의 작업 – 값이 가장 큰 경로를 찾습니다.
입력:
첫 번째 줄에는 두 개의 정수 n, m(1 ≤ n, m ≤ 200000)이 포함되며, 이는 그래프에 n개의 정점과 m개의 방향 모서리가 있음을 의미합니다.
두 번째 줄에는 소문자 라틴 문자로만 구성된 문자열 s가 포함됩니다. 기호 번호 i – 맨 위 숫자 i에 적힌 글자입니다.
그런 다음 m 줄이 이어집니다. 각 행에는 x에서 y로 향하는 가장자리를 설명하는 두 개의 정수 x, y(1 ≤ x, y ≤ n)가 포함되어 있습니다. x는 y와 같을 수 있으며 x와 y 사이에 여러 개의 에지가 있을 수 있습니다.
또한 그래프 연결이 끊어질 수 있습니다.
출력:
하나의 숫자 인쇄 – 최대 경로 길이. 임의로 큰 값을 가진 경로가 있으면 -1을 인쇄합니다.
예:
<몸>
| 입력 |
출력 |
5 4
아바카
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 |