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
{
	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;
        }
    }

	static Graph[] city;
	static char[] color;
	static String orig;
	static boolean cycle = false;

	public static void main (String[] args)
	{
		FastReader reader = new FastReader();
		int totalNodes = reader.nextInt();
		int totalEdges = reader.nextInt();
		orig = reader.nextLine();

		city = new Graph[totalNodes];
		color = new char[totalNodes];
		for (int i=0; i<totalNodes; i++)
		{
			city[i] = new Graph();
			color[i] = 'w';
		}

		for (int j=0; j<totalEdges; j++)
		{
			int u = reader.nextInt()-1;
			int v = reader.nextInt()-1;

			city[u].list.add (v);
		}

		for (int i=0; i<totalNodes; i++)
		{
			if (color[i] == 'w')
				checkCycle (i);
		}

		if (cycle)
		{
			System.out.println (-1);
			return;
		}

		for (int i=0; i<totalNodes; i++)
			color[i] = 'w';

		int answer = 0;
		for (int i=0; i<totalNodes; i++)
		{
			if (color[i] == 'w')
				makeDfs (i);

			for (int j=0; j<26; j++)
				answer = Math.max (answer, city[i].length[j]);
		}

		System.out.println (answer);
	}

	static void makeDfs (int node)
	{
		color[node] = 'g';
		for (int i=0; i<city[node].list.size(); i++)
		{
			int current = city[node].list.get(i);

			if (color[current] == 'w')
				makeDfs (current);

			for (int j=0; j<26; j++)
				city[node].length[j] = Math.max (city[node].length[j], city[current].length[j]);
		}

		color[node] = 'b';
		city[node].length[(int)orig.charAt(node) - (int)'a'] += 1;
	}

	static boolean checkCycle (int node)
	{
		color[node] = 'g';
		for (int i=0; i<city[node].list.size(); i++)
		{
			int current = city[node].list.get(i);

			if (color[current] == 'w')
				checkCycle (current);
			else if (color[current] == 'g')
			{
				cycle = true;
				return false;
			}
		}

		color[node] = 'b';
		return true;
	}
}

class Graph
{
	int[] length = new int[26];
	ArrayList<Integer> list = new ArrayList<Integer>();
}
