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.
/**
 * DA-IICT
 * Author : Savaliya Sagar
 */
import java.io.*;
import java.math.*;
import java.util.*;


public class D919
{
	ArrayList<Integer> a[];
	int w[][],n;
	void solve()
	{
		n = ni();
		int m = ni();
		a = new ArrayList[n + 1];
		w = new int[26][n+1];
		char c[] = next().toCharArray();
		for(int i=1;i<=n;i++) {
			w[c[i-1]-'a'][i]++;
		}
		for (int i = 0; i <= n; i++)
		{
			a[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++)
		{
			int u = ni();
			int v = ni();
			a[u].add(v);
		}
		int tp[] = ts();
		if(tp==null) {
			out.println(-1);
			return;
		}
		int ans = 0;
		int ww[] = new int[n+1];
		for(int i=0;i<26;i++) {
			for(int j=1;j<=n;j++){
				ww[j] = w[i][j];
			}
			for(int j:tp) {
				for(int k:a[j]) {
					ww[k] = Math.max(ww[k], w[i][k]+ww[j]);
				}
			}
			for(int j=1;j<=n;j++)
				ans= Math.max(ww[j],ans);
		}
		out.println(ans);
	}
	int[] ts()
	{
		int[] ec = new int[n+1];
		for(int i = 1;i <=n;i++){
			for(int to : a[i])ec[to]++;
		}
		int[] ret = new int[n];
		int q = 0;
		
		// sources
		for(int i = 1;i <= n;i++){
			if(ec[i] == 0)ret[q++] = i;
		}
		
		for(int p = 0;p < q;p++){
			for(int to : a[ret[p]]){
				if(--ec[to] == 0)ret[q++] = to;
			}
		}
		// loop
		for(int i = 1;i <= n;i++){
			if(ec[i] > 0) return null;
		}
		return ret;
	}

	public int ni()
	{
		return Integer.parseInt(next());
	}
	void run() throws Exception
	{
		out = new PrintWriter(System.out);
		reader = new BufferedReader(new InputStreamReader(System.in), 32768);
		tokenizer = null;
		solve();
		out.flush();
	}
	
	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter out;
	
	public static void main(String[] args) throws Exception
	{
		new D919().run();
	}
	
	public String next()
	{
		while (tokenizer == null || !tokenizer.hasMoreTokens())
		{
			try
			{
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e)
			{
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
}
