You are given a graph with n nodes and m directed edges. One lowercase letter is assigned to each node. We define a path's value as the number of the most frequently occurring letter. For example, if letters on a path are "abaca", then the value of that path is 3. Your task is find a path whose value is the largest.

Input

The first line contains two positive integers n, m (1 ≤ n, m ≤ 300 000), denoting that the graph has n nodes and m directed edges.

The second line contains a string s with only lowercase English letters. The i-th character is the letter assigned to the i-th node.

Then m lines follow. Each line contains two integers x, y (1 ≤ x, y ≤ n), describing a directed edge from x to y. Note that x can be equal to y and there can be multiple edges between x and y. Also the graph can be not connected.

Output

Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output -1 instead.

Examples

Input

5 4
abaca
1 2
1 3
3 4
4 5


Output

3


Input

6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4


Output

-1


Input

10 14
xzyzyzyzqx
1 2
2 4
3 5
4 5
2 6
6 8
6 5
2 10
3 9
10 9
4 6
1 10
2 8
3 7


Output

4

Note

In the first sample, the path with largest value is 1 → 3 → 4 → 5. The value is 3 because the letter 'a' appears 3 times.
import java.util.*;
import java.io.*;

public class Substring {

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}

	public static void shuffle(int[] a) {
		Random r = new Random();

		for (int i = 0; i <= a.length - 2; i++) {
			int j = i + r.nextInt(a.length - i);

			swap(a, i, j);
		}

		Arrays.sort(a);
	}

	public static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		FastReader t = new FastReader();
		PrintWriter o = new PrintWriter(System.out);
		int n = t.nextInt();
		int m = t.nextInt();
		String colors = t.next();
		List<Integer>[] graph = new ArrayList[n];
		int[] inDegree = new int[n];

		for (int i = 0; i < n; ++i)
			graph[i] = new ArrayList<>();

		for (int i = 0; i < m; ++i) {
			int x = t.nextInt() - 1;
			int y = t.nextInt() - 1;
			++inDegree[y];

			graph[x].add(y);
		}

		o.println(largestPathValue(colors, graph, inDegree));
		o.flush();
		o.close();
	}

	private static int largestPathValue(String colors, List<Integer>[] graph, int[] inDegree) {
		int n = colors.length();
		Queue<Integer> queue = new LinkedList<>();
		int loopsDone = 0;
		int[][] maxColor = new int[n][26];
		int max = 0;

		for (int i = 0; i < n; ++i)
			if (inDegree[i] == 0)
				queue.add(i);

		while (!queue.isEmpty()) {
			++loopsDone;
			int idx = queue.remove();

			if (loopsDone >= n && !queue.isEmpty())
				return -1;

			++maxColor[idx][colors.charAt(idx) - 'a'];

			for (int val : graph[idx]) {
				--inDegree[val];

				if (inDegree[val] == 0)
					queue.add(val);

				for (int i = 0; i < 26; ++i)
					maxColor[val][i] = Math.max(maxColor[val][i], maxColor[idx][i]);
			}
		}

		if (loopsDone < n)
			return -1;

		for (int i = 0; i < n; ++i)
			for (int j = 0; j < 26; ++j)
				max = Math.max(max, maxColor[i][j]);

		return max;
	}
}