← 返回题目列表

Codeforces · 919/D

D. 子字符串

中文机器翻译题面 查看原题

给您一个包含 $$$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$$$ 次。