kdh9949
Time limit1sMemory limit1024 MB
Find the longest path in an undirected graph whose vertex labels spell repeated KDH blocks, or report -1 if such a path can be infinite.
- Level
Hard8 of 10
- Topics
- Graph, Dynamic programming, DFS, Implementation
- Solved
- No attempts yet
Statement
What could kdh9949, the ID used by SNUPS president Donghyeon, possibly mean? It means his birthday is April 9, 1999!
April 9 has come around again, and Donghyeon received an undirected graph with N vertices and M edges as a birthday present, where each vertex is labeled with the letter K, D, or H. Moved by the thoughtful gift, Donghyeon wants to give the graph a special meaning.
So Donghyeon wants to find the longest path in this graph where his initials KDH appear consecutively. That is, he wants to find the path of maximum length among those defined as follows.
- Let Ci be the letter written on vertex i, and Xj be the number of the j-th vertex appearing in the path.
- The length P of the path is a multiple of 3.
- For every integer 1 ≤ i ≤ P-1, the vertices Xi and Xi+1 are directly connected by an edge.
- For every integer 1 ≤ k ≤ P/3, CX3k-2 =
K, CX3k-1 =D, and CX3k =Hhold.
Output the length of the longest path satisfying the conditions above. However, if no such path exists, for example because an infinitely long path exists, output -1.
Input
The first line gives the number of vertices N and the number of edges M of the graph Donghyeon received. (2 ≤ N ≤ 200,000, 1 ≤ M ≤ 300,000)
The second line gives a string of length N; the i-th character of this string is the letter written on vertex i of the graph. Each character of the string is guaranteed to be K, D, or H.
The next M lines give the numbers U, V of the two vertices connected by each edge. No loops or multiple edges are guaranteed. (1 ≤ U ≤ N, 1 ≤ V ≤ N, U ≠ V)
Output
Output the length of the longest path Donghyeon can form that satisfies the conditions. However, if no such path exists, for example because an infinitely long path exists, output -1.
Hint
In the first sample, taking the path 2 - 4 - 5 - 7 - 6 - 3 gives KDHKDH, which is the longest path satisfying the conditions.
In the second sample, K and D are not adjacent, so KDH cannot be formed.
In the third sample, taking a path such as 5 - 3 - 4 - 5 - 3 - 4 - ... gives a path where KDHKDH... appears infinitely long, so no "longest" path exists.