17455번 - kdh9949

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

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

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

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

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

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

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

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

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

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

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

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