time limit: per test3 seconds
memory limit: per test256 megabytes
inputstandard: input
outputstandard: output

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.

## Input

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

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

input

output

input

output

input

output

## Note

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.

## Solve

$dp[i][j]$表示到达节点$i$，字母$’a’+j$出现的最大次数

## Code

-------------本文结束感谢您的阅读-------------
0%