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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Substring {
	
	private static class Edge{
		private int from, to;
		
		Edge(int from, int to){
			this.from = from;
			this.to = to;
		}
		

		int getFrom() {
			return from;
		}

		void setFrom(int from) {
			this.from = from;
		}

		int getTo() {
			return to;
		}

		void setTo(int to) {
			this.to = to;
		}


	}

	private static class Graph{
		private List<List<Edge>> edgeList;
		private int n;
		
		Graph(int n){
			this.n = n;
			edgeList = new ArrayList<List<Edge>>();
			for(int i = 0; i < n; i++)
				edgeList.add(new ArrayList<Edge>());
				
		}
		
		List<Edge> getEdges(int i){
			return edgeList.get(i);
		}
		
		int getSize(){
			return n;
		}
		

		
		void addEdge(int from, int to){
			Edge e = new Edge(from, to);
			edgeList.get(from).add(e);
		}
		
	}
	
	static int charInt(char c){
		return ((int) c) - ((int) 'a');
	}
	public static void main(String[] args) throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] values = in.readLine().split(" ");
		int n = Integer.parseInt(values[0]), m = Integer.parseInt(values[1]);
		
		int[] receiving = new int[n+1];
		int maxDyn = 0;
		int[][] dyn = new int[n+1][26];
		Graph g = new Graph(n+1);
		String s = "$" + in.readLine();
		for(int i = 0; i < m; i++){
			values = in.readLine().split(" ");
			int x = Integer.parseInt(values[0]), y = Integer.parseInt(values[1]);
			g.addEdge(x, y);
			receiving[y]++;
		}
		in.close();
		
		Queue<Integer> q = new LinkedList<>();
		
		for(int i = 1; i<= n; i++){
			if(receiving[i] == 0){
				q.add(i);
				dyn[i][charInt(s.charAt(i))] = 1;
			}
		}
		int remaining = n;
		
		while(!q.isEmpty()){
			int node = q.poll();
			remaining--;
			for(Edge e : g.getEdges(node)){
				
				for(int v = 0; v < 26; v++){
					dyn[e.getTo()][v] = Math.max(dyn[e.getTo()][v], dyn[node][v] + ((charInt(s.charAt(e.getTo())) == v? 1 : 0)));
					maxDyn = Math.max(maxDyn, dyn[e.getTo()][v]);
				}
				receiving[e.getTo()]--;
				if(receiving[e.getTo()] == 0) q.add(e.getTo());
			}
		}
		if(remaining != 0){
			System.out.println(-1);
		}
		else System.out.println(maxDyn);
	}
}