给您一个包含 $$$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
输出 #1
3
输入 #2
6 6 xzyabc 1 2 3 1 2 3 5 4 4 3 6 4
输出 #2
-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
输出 #3
4
注意
在第一个示例中,具有最大值的路径是 $$$1 \to 3 \to 4 \to 5$$$。该值为 $$$3$$$ 因为字母“a”出现了 $$$3$$$ 次。