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.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Stack;

public class Substrings {
	static ArrayList<Integer> adj[], adj1[], top;
	static int n;
	static Stack<Integer> st = new Stack<>();

	public static void main(String[] args) {
		top = new ArrayList<>();
		adj = new ArrayList[300005];
		adj1 = new ArrayList[300005];
		Scanner s = new Scanner(System.in);
		n = s.nextInt();
		int m = s.nextInt();
		String str = s.next();
		char[] strr = str.toCharArray();
		for (int i = 0; i <= 300000; i++) {
			adj[i] = new ArrayList<>();
			adj1[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			int u = s.nextInt() - 1, v = s.nextInt() - 1;
			adj[u].add(v);
			adj1[v].add(u);
		}
		boolean cyc = isCyclic();
		if (cyc) {
			System.out.println(-1);
			return;
		}
		topologicalSort();
		long[][] dp = new long[300005][26];
		dp[top.get(0)][strr[top.get(0)] - 'a']++;
		for (int i = 1; i < top.size(); i++) {
			long curr = top.get(i);
			dp[(int) curr][strr[(int) curr] - 'a']++;
			for (int j = 0; j < adj1[(int) curr].size(); j++) {
				for (int k = 0; k < 26; k++) {
					int eq = 0;
					if ((strr[(int) curr] - 'a') == k)
						eq = 1;
					dp[(int) curr][k] = Math.max(dp[(int) curr][k], dp[adj1[(int) curr].get(j)][k] + eq);
				}
			}
		}
		long ans = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 26; j++) {
				ans = Math.max(ans, dp[i][j]);
			}
		}
		System.out.println(ans);
	}

	static void topologicalSortUtil(int v, boolean visited[], Stack stack) {
		// Mark the current node as visited.
		visited[v] = true;
		Integer i;

		// Recur for all the vertices adjacent to this
		// vertex
		Iterator<Integer> it = adj[v].iterator();
		while (it.hasNext()) {
			i = it.next();
			if (!visited[i])
				topologicalSortUtil(i, visited, stack);
		}

		// Push current vertex to stack which stores result
		stack.push(new Integer(v));
	}

	// The function to do Topological Sort. It uses
	// recursive topologicalSortUtil()
	static void topologicalSort() {
		// Stack stack = new Stack();

		// Mark all the vertices as not visited
		boolean visited[] = new boolean[300005];

		// Call the recursive helper function to store
		// Topological Sort starting from all vertices
		// one by one
		for (int i = 0; i < n; i++)
			if (visited[i] == false)
				topologicalSortUtil(i, visited, st);

		// Print contents of stack
		while (st.empty() == false) {
			top.add(st.pop());
		}
		// System.out.print(stack.pop() + " ");
	}

	static boolean isCyclicUtil(int v, boolean visited1[], boolean recStack[]) {
		if (visited1[v] == false) {
			// Mark the current node as visited and part of recursion stack
			visited1[v] = true;
			recStack[v] = true;

			// Recur for all the vertices adjacent to this vertex
			for (int i = 0; i < adj[v].size(); ++i) {
				if (!visited1[adj[v].get(i)] && isCyclicUtil(adj[v].get(i), visited1, recStack))
					return true;
				else if (recStack[adj[v].get(i)])
					return true;
			}

		}
		recStack[v] = false; // remove the vertex from recursion stack
		return false;
	}

	static boolean isCyclic() {
		// Mark all the vertices as not visited and not part of recursion
		// stack
		boolean[] visited1 = new boolean[300005];
		boolean[] recStack = new boolean[300005];
		// Call the recursive helper function to detect cycle in different
		// DFS trees
		for (int i = 0; i < n; i++) {
			visited1[i] = false;
			recStack[i] = false;
		}
		for (int i = 0; i < n; i++)
			if (isCyclicUtil(i, visited1, recStack))
				return true;

		return false;
	}
}