A11484. Substring

You are given a graph with $n$ nodes and $m$ directed edges. One lowercase letter is assigned to each node. We define a path's value as the number of the most frequently occurring letter. For example, if letters on a path are "abaca", then the value of that path is $3$ . Your task is find a path whose value is the largest.

The first line contains two positive integers $n,m$ ( $1<=n,m<=300000$ ), denoting that the graph has $n$ nodes and $m$ directed edges.

The second line contains a string $s$ with only lowercase English letters. The $i$ -th character is the letter assigned to the $i$ -th node.

Then $m$ lines follow. Each line contains two integers $x,y$ ( $1<=x,y<=n$ ), describing a directed edge from $x$ to $y$ . Note that $x$ can be equal to $y$ and there can be multiple edges between $x$ and $y$ . Also the graph can be not connected.

Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output -1 instead.

In the first sample, the path with largest value is $1→3→4→5$ . The value is $3$ because the letter 'a' appears $3$ times.