题目描述

给定一个 $n$ 个点 $m$ 条边的有向图。

图中可能包含重边和自环，也可能不连通。

给每个点分配一个小写字母。

我们定义一条路径的权值为出现频率最高的字母的出现次数。

例如，如果一条路径上的字母是 abaca，则该路径的权值为 $3$。

请你找到给定图中权值最大的路径，输出这个最大路径权值。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含一个由小写字母构成的字符串 $s$，其中第 $i$ 个字母表示第 $i$ 个点上的字母。

接下来 $m$ 行，每行包含两个整数 $x, y$ 表示存在一条从点 $x$ 到点 $y$ 的边。

所有点的编号为 $1 \sim n$。

输出格式

输出最大路径权值。

如果这个权值是无穷大，则输出 $-1$。

样例

5 4
abaca
1 2
1 3
3 4
4 5

3

6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4

-1

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 300, m \le 1000$
• 对于 $100\%$ 的数据，$1 \le n,m \le 3 \cdot 10^5, 1 \le x,y \le n$