Problem
n 個の頂点と m 個の有向辺のグラフが与えられます。各頂点には小文字のラテン文字が含まれています。
パスの長さを、このパスに沿ってある文字に遭遇した最大回数として定義しましょう。たとえば、パス内の文字が文字列「abaca」を形成する場合、このパスの値は 3 です。
あなたのタスク —最大の値を持つパスを見つけます。
入力:
最初の行には 2 つの整数 n、m (1 ≤ n, m ≤ 200000) が含まれています。これは、グラフに n 個の頂点と m 個の有向辺があることを意味します。
2 行目には、小文字のラテン文字のみで構成される文字列 s が含まれています。シンボル番号 i —これは一番上の番号 i に書かれた文字です。
次に m 行が続きます。これらの各行には、x から y への有向辺を表す 2 つの整数 x、y (1 ≤ x, y ≤ n) が含まれます。 x は y と同じにすることができ、x と y の間に複数のエッジが存在する可能性があることに注意してください。
また、グラフが途切れる場合があります。
出力:
数字を 1 つ出力します。最大パス長。任意に大きな値を持つパスがある場合は、-1 を出力します。
例:
<本体>
| 入力 |
出力 |
5 4
アバカ
1 2
1 3
34
4 5 |
3 |
6 6
しんたろう
1 2
3 1
23
5 4
4 3
6 4 |
-1 |
10 14
しんしんしんしん
1 2
24
3 5
4 5
26
68
6 5
2 10
39
10 9
46
1 10
28
37号
| 4 |