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.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class D919{

	void solve()
	{
		int n = ni(), m = ni();
		char[] s = ca();
		int[] v1 = new int[m];
		int[] v2 = new int[m];
		for(int i=0;i<m;i++)
		{
			v1[i] = ni() - 1;
			v2[i] = ni() - 1;
		}
		int[][] g = buildDG(n, v1, v2);
		int[][] f = new int[n][26];
		boolean[] vis = new boolean[n];
		int[] ord = topologicalSort(g);
		if(ord == null)
		{
			out.println(-1);
			return;
		}
		int max = 1 << 31;
		for(int x : ord)
			if(!vis[x])
			{
				dfs(g, vis, f, x, s);
				for(int i=0;i<26;i++)
					max = Math.max(max, f[x][i]);
			}
		out.println(max);
		
	}
	
	int[] topologicalSort(int[][] g)
	{
		int n = g.length;
		int[] q = new int[n];
		int[] f = new int[n];
		for(int[] adj : g)
			for(int x : adj)
				f[x]++;
		int r = 0;
		for(int i=0;i<n;i++)
			if(f[i] == 0)
				q[r++] = i;
		for(int p=0;p<r;p++)
			for(int x : g[q[p]])
				if(--f[x] == 0)
					q[r++] = x;
		for(int x : f) 
			if(x != 0) 
				return null;
		return q;
	}
	
	void dfs(int[][] g, boolean[] vis, int[][] f, int cur, char[] s)
	{
		vis[cur] = true;
		for(int nex : g[cur]) 
			if(!vis[nex])
				dfs(g, vis, f, nex, s);

		for(int nex : g[cur]) 
			for(int i=0;i<26;i++)
				f[cur][i] = Math.max(f[cur][i], f[nex][i]);
		
		f[cur][s[cur]-'a']++;
	}
	
	public int[][] buildDG(int n,int[] v1,int[] v2)
	{
		int[][] graph = new int[n][];
		int[] cn = new int[graph.length];
		for(int i=0;i<v1.length;i++)
			cn[v1[i]]++;
		for(int i=0;i<graph.length;i++)
			graph[i] = new int[cn[i]];
		for(int i=0;i<v1.length;i++)
			graph[v1[i]][--cn[v1[i]]] = v2[i];
		return graph;
	}
	
	public static void main(String[] args){new D919().run();}
	
	private byte[] bufferArray = new byte[1024];
	private int bufLength = 0;
	private int bufCurrent = 0;
	InputStream inputStream;
	PrintWriter out;
	
	public void run()
	{
		inputStream = System.in;
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}
	
	int nextByte()
	{
		if(bufLength == -1)
			throw new InputMismatchException();
		if(bufCurrent >= bufLength)
		{
			bufCurrent = 0;
			try
			{bufLength = inputStream.read(bufferArray);}
			catch(IOException e)
			{ throw new InputMismatchException();}
			if(bufLength <= 0)
				return -1;
		}
		return bufferArray[bufCurrent++];
	}
	
	boolean isSpaceChar(int x)	{return (x < 33 || x > 126);}
	
	boolean isDigit(int x)	{return (x >= '0' && x <= '9');}
	
	int nextNonSpace()
	{
		int x;
		while((x=nextByte()) != -1 && isSpaceChar(x));
		return x;
	}
	
	int ni()
	{
		long ans = nl();
		if (ans >= Integer.MIN_VALUE && ans <= Integer.MAX_VALUE)
			return (int)ans;
		throw new InputMismatchException();
	}
	
	long nl()
	{
		long ans = 0;
		boolean neg = false;
		int x = nextNonSpace();
		if(x == '-') 
		{
			neg = true;
			x = nextByte();
		}
		while(!isSpaceChar(x))
		{
			if(isDigit(x))
			{
				ans = ans * 10 + x -'0';
				x = nextByte();
			}
			else
				throw new InputMismatchException();
		}
		return neg ? -ans : ans;
	}
	
	String ns()
	{
		StringBuilder sb = new StringBuilder();
		int x = nextNonSpace();
		while(!isSpaceChar(x))
		{
			sb.append((char)x);
			x = nextByte();
		}
		return sb.toString();
	}
	
	char nc()	{ return (char)nextNonSpace();}
	
	double nd()	{ return (double)Double.parseDouble(ns()); }
	
	char[] ca()	{ return ns().toCharArray();}
	
	char[][] ca(int n)
	{
		char[][] ans = new char[n][];
		for(int i=0;i<n;i++)
			ans[i] = ca();
		return ans;
	}
	
	int[] ia(int n)
	{
		int[] ans = new int[n];
		for(int i=0;i<n;i++)
			ans[i] = ni();
		return ans;
	}
	
	void db(Object... o) {System.out.println(Arrays.deepToString(o));}
	
}
