Problem
Cho một đồ thị gồm n đỉnh và m cạnh có hướng. Mỗi đỉnh chứa một số chữ cái Latinh viết thường.
Hãy xác định độ dài của một đường dẫn là số lần lớn nhất mà một số chữ cái được bắt gặp dọc theo đường dẫn này. Ví dụ: nếu các chữ cái trong đường dẫn tạo thành chuỗi "abaca" thì giá trị của đường dẫn này là 3.
Nhiệm vụ của bạn — tìm đường đi có giá trị lớn nhất.
Đầu vào:
Dòng đầu tiên chứa 2 số nguyên n, m (1 ≤ n, m ≤ 200000), nghĩa là đồ thị có n đỉnh và m cạnh có hướng.
Dòng thứ hai chứa xâu s, chỉ bao gồm các chữ cái Latinh viết thường. Số ký hiệu i — đây là chữ cái được viết ở đầu số i.
Sau đó, m dòng theo sau. Mỗi dòng này chứa hai số nguyên x, y (1 ≤ x, y ≤ n) mô tả một cạnh có hướng từ x đến y. Lưu ý rằng x có thể bằng y và có thể có nhiều cạnh giữa x và y.
Ngoài ra, biểu đồ có thể bị ngắt kết nối.
Đầu ra:
In một số — độ dài đường dẫn tối đa. Nếu có các đường dẫn có giá trị lớn tùy ý, hãy in -1.
Ví dụ:
| Đầu vào |
Đầu ra |
5 4
bàn tính
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 |