题目描述

给定一个包含 $n$ 个节点和 $m$ 条有向边的图。每个节点上都标有一个小写字母。定义一条路径的权值为该路径上出现次数最多的字母的出现次数。例如，若一条路径上的字母序列为 "abaca"，则该路径的权值为 $3$。你的任务是找出一条权值最大的路径。

输入

第一行包含两个正整数 $n, m$（$1 \leq n, m \leq 300\,000$），表示图中有 $n$ 个节点和 $m$ 条有向边。

第二行包含一个仅由小写英文字母组成的字符串 $s$，其中第 $i$ 个字符表示第 $i$ 个节点上所标的字母。

接下来 $m$ 行，每行包含两个整数 $x, y$（$1 \leq x, y \leq n$），描述一条从 $x$ 到 $y$ 的有向边。注意可能存在 $x = y$（自环），也可能在 $x$ 和 $y$ 之间存在多条重边。图不一定连通。

输出

输出一行一个整数，表示最大的权值。如果该权值可以任意大（即可以无限增大），则输出 $-1$。

样例

样例 1

输入：

5 4
abaca
1 2
1 3
3 4
4 5

输出：

3

样例 2

输入：

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

输出：

-1

样例 3

输入：

10 14
xzyzyzyzqx
1 2
2 4
3 5
4 5
2 6
6 8
6 5
2 10
3 9
10 9
4 6
1 10
2 8
3 7

输出：

4

样例解释

第一个样例中，权值最大的路径为 $1 \to 3 \to 4 \to 5$，该路径上字母 'a' 出现了 $3$ 次，因此权值为 $3$。