Problem
n köşe ve m yönlendirilmiş kenardan oluşan bir grafik verildi. Her tepe noktası bazı küçük Latin harfleri içerir.
Bir yolun uzunluğunu, bu yol boyunca bir harfle en fazla karşılaşılma sayısı olarak tanımlayalım. Örneğin yoldaki harfler "abaca" dizgesini oluşturuyorsa bu yolun değeri 3'tür.
Göreviniz — en büyük değere sahip yolu bulun.
Giriş:
İlk satır iki tamsayı n, m (1 ≤ n, m ≤ 200000) içerir, yani grafiğin n köşesi ve m yönlendirilmiş kenarı vardır.
İkinci satır, yalnızca küçük Latin harflerinden oluşan s dizisini içerir. Sembol numarası i — i rakamının en üstüne yazılan harftir.
Sonra m satırları takip eder. Bu satırların her biri, x'ten y'ye yönlendirilmiş bir kenarı tanımlayan iki tamsayı x, y (1 ≤ x, y ≤n) içerir. x'in y'ye eşit olabileceğini ve x ile y arasında birden çok kenar olabileceğini unutmayın.
Ayrıca grafiğin bağlantısı kesilebilir.
Çıktı:
Bir sayı yazdır — maksimum yol uzunluğu. İsteğe bağlı olarak büyük bir değere sahip yollar varsa, -1 yazdırın.
Örnekler:
| Giriş |
Çıktı |
5 4
abaka
1 2
1 3
34
4 5 |
3 |
6 6
xzyabc
1 2
3 1
23
5 4
4 3
6 4 |
-1 |
10 14
xzyzyzyzqx
1 2
24
3 5
4 5
26
68
6 5
2 10
39
10 9
46
1 10
28
37 |
4 |