Hành Trình Mạng

Cho một đồ thị gồm $n$ đỉnh và $m$ cạnh có hướng. Mỗi đỉnh được gán một ký tự tiếng Anh viết thường. Giá trị của một đường đi được định nghĩa là số lần xuất hiện nhiều nhất của cùng một ký tự trên đường đi đó.

Ví dụ, nếu các ký tự trên một đường đi tạo thành chuỗi "abaca", thì giá trị của đường đi đó bằng $3$.

Yêu cầu của bạn là tìm một đường đi có giá trị lớn nhất. Nếu giá trị của đường đi có thể đạt tới vô hạn, hãy in ra -1.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $n$ và $m$ ($1 ≤ n, m ≤ 300\,000$), lần lượt là số đỉnh và số cạnh có hướng của đồ thị.

Dòng thứ hai chứa chuỗi $s$ gồm $n$ ký tự tiếng Anh viết thường. Ký tự thứ $i$ tương ứng với ký tự được gán cho đỉnh thứ $i$.

Tiếp theo là $m$ dòng, mỗi dòng chứa hai số nguyên $x$ và $y$ ($1 ≤ x, y ≤ n$), mô tả một cạnh có hướng từ đỉnh $x$ đến đỉnh $y$. Lưu ý rằng $x$ có thể bằng $y$ và có thể có nhiều cạnh giữa cùng một cặp đỉnh. Đồ thị không nhất thiết phải liên thông.

Kết quả

In ra một số nguyên duy nhất là giá trị lớn nhất tìm được. Nếu giá trị có thể lớn tùy ý, in ra -1.

Chấm điểm

Subtask 1 (30 points). $n, m ≤ 15$

Subtask 2 (70 points). $1 ≤ n, m ≤ 300$\,000

Ví dụ

Input

4 3
abca
1 2
2 3
3 4

Output

2

Ghi chú

Trong ví dụ mẫu, đường đi đi qua các đỉnh $1 \to 2 \to 3 \to 4$ nhận chuỗi ký tự "abca". Ký tự 'a' xuất hiện $2$ lần, nên giá trị lớn nhất của đường đi là $2$.