Problem
Diberi graf bagi n bucu dan m tepi terarah. Setiap bucu mengandungi beberapa huruf Latin huruf kecil.
Mari kita tentukan panjang laluan sebagai bilangan kali terbesar beberapa huruf ditemui di sepanjang laluan ini. Contohnya, jika huruf dalam laluan membentuk rentetan "abaca", maka nilai laluan ini ialah 3.
Tugas anda — cari laluan dengan nilai terbesar.
Input:
Baris pertama mengandungi dua integer n, m (1 ≤ n, m ≤ 200000), bermakna graf mempunyai n bucu dan m tepi terarah.
Baris kedua mengandungi rentetan s, hanya terdiri daripada huruf Latin huruf kecil. Simbol nombor i — ini ialah huruf yang ditulis di bahagian atas nombor i.
Kemudian m baris mengikuti. Setiap baris ini mengandungi dua integer x, y (1 ≤ x, y ≤ n) menerangkan tepi terarah dari x ke y. Ambil perhatian bahawa x boleh sama dengan y, dan boleh terdapat berbilang tepi antara x dan y.
Selain itu, graf mungkin terputus sambungan.
Output:
Cetak satu nombor — panjang laluan maksimum. Jika terdapat laluan dengan nilai yang besar secara sewenang-wenangnya, cetak -1.
Contoh:
| Input |
Output |
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 |