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 Main {
	public static void main(String args[]) {new Main().run();}

	FastReader in = new FastReader();
	PrintWriter out = new PrintWriter(System.out);
	void run(){
		out.println(work());
		out.flush();
	}
	long mod=1000000007;
	long gcd(long a,long b) {
		return b==0?a:gcd(b,a%b);
	}
	int[][] rec;
	int[] A;
	ArrayList<Integer>[] graph;
	int work() {
		int n=in.nextInt();
		int m=in.nextInt();
		rec=new int[n][26];
		String str=in.next();
		A=new int[n];
		for(int i=0;i<n;i++) {
			A[i]=str.charAt(i)-'a';
		}
		graph=(ArrayList<Integer>[])new ArrayList[n];
		for(int i=0;i<n;i++)graph[i]=new ArrayList<>();
		for(int i=0;i<m;i++) {
			int n1=in.nextInt()-1;
			int n2=in.nextInt()-1;
			graph[n1].add(n2);
		}
		int[] col=new int[n];
		for(int i=0;i<n;i++) {
			if(col[i]==0&&!dfs(i,col)) {
				return -1;
			}
		}
		int ret=0;
		for(int node=0;node<n;node++) {
			for(int i=0;i<26;i++) {
				ret=Math.max(rec[node][i], ret);
			}
		}
		return ret;
	}
	private boolean dfs(int node, int[] col) {
		col[node]=1;
		for(int nn:graph[node]) {
			if(col[nn]==1)return false;
			if(col[nn]==0&&!dfs(nn,col)) {
				return false;
			}
			for(int i=0;i<26;i++) {
				rec[node][i]=Math.max(rec[node][i], rec[nn][i]);
			}
		}
		col[node]=2;
		rec[node][A[node]]++;
		return true;
	}
}



class FastReader
{
	BufferedReader br;
	StringTokenizer st;

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

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

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

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