시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 74 30 28 48.276%

문제

SNUPS 회장 동현이가 쓰는 ID인 kdh9949는 도대체 무슨 뜻일까? 바로 동현이의 생일이 199949일이라는 뜻이다!

어느덧 4월 9일이 다가왔고, 동현이는 생일 선물로 각 정점에 알파벳 K, D, 또는 H가 적힌 정점 N개, 간선 M개짜리 양방향 그래프를 받았다. 정성 가득한 선물에 감동을 받은 동현이는 이 그래프에 특별한 의미를 부여하고 싶어졌다.

그래서, 동현이는 이 그래프에서 자신의 이니셜인 KDH가 연속적으로 나타나는 가장 긴 경로가 찾고 싶어졌다. 즉, 다음과 같이 정의된 경로 중 길이가 최대인 것을 찾고 싶어졌다.

  • Ci : i번 정점에 적힌 글자, Xj : 경로에서 j번째로 나타나는 정점의 번호라 하자.
  • 경로의 길이 P는 3의 배수이다.
  • 모든 정수 1 ≤ iP-1에 대해, Xi번 정점과 Xi+1번 정점은 간선으로 직접 연결되어 있다.
  • 모든 정수 1 ≤ kP/3에 대해, CX3k-2 = K, CX3k-1 = D, CX3k = H 를 만족한다.

위 조건을 만족하는 가장 긴 경로의 길이를 출력하라. 단, 무한히 긴 경로가 존재하는 등의 이유로 그런 경로가 존재하지 않으면 -1을 출력한다.

입력

첫 줄에 동현이가 받은 그래프의 정점 개수 N과 간선 개수 M이 주어진다. (2 ≤ N ≤ 200,000, 1 ≤ M ≤ 300,000)

두 번째 줄에 길이 N의 문자열이 주어지는데, 이 문자열의 i번째 글자가 그래프의 i번 정점에 적힌 글자이다. 문자열의 각 문자는 K 또는 D 또는 H임이 보장된다.

다음 M개의 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 U, V가 주어진다. 루프나 중복 간선이 없음이 보장된다. (1 ≤ UN, 1 ≤ VN, UV)

출력

동현이가 조건을 만족하며 만들 수 있는 가장 긴 경로의 길이를 출력한다. 단, 무한히 긴 경로가 존재하는 등의 이유로 그런 경로가 존재하지 않으면 -1을 출력한다.

예제 입력 1

7 9
DKHDHDK
1 3
1 4
2 4
2 6
3 5
3 6
4 5
5 7
6 7

예제 출력 1

6

예제 입력 2

4 5
KHDH
1 2
1 4
2 3
2 4
3 4

예제 출력 2

-1

예제 입력 3

5 6
HDDHK
1 2
1 4
2 3
3 4
3 5
4 5

예제 출력 3

-1

노트

첫 번째 예제의 경우, 2 - 4 - 5 - 7 - 6 - 3 순으로 경로를 잡으면 KDHKDH가 되므로 문제의 조건을 만족하며 잡을 수 있는 가장 긴 경로가 된다.

두 번째 예제의 경우, KD가 이어져 있지 않아서 KDH를 만들 수 없다.

세 번째 예제의 경우, 5 - 3 - 4 - 5 - 3 - 4 - ... 와 같은 경로를 잡으면 무한히 길게 KDHKDH...가 나타나는 경로를 찾을 수 있으므로 "가장 긴" 경로는 존재하지 않는다.