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.*;
import java.util.*;
 
public class D {
    FastScanner in;
    PrintWriter out;
    boolean systemIO = true;
 
    int graph[][];
    int label[];
    int n;
    int color[];
    int memo[][];
    
    public void solve() throws IOException {
    	n = in.nextInt();
    	int m = in.nextInt();
    	int cnt[] = new int[n];
    	label = new int[n];
    	color = new int[n];
    	memo = new int[n][26];
    	graph = new int[n][];
    	int x[] = new int[m];
    	int y[] = new int[m];
    	String s = in.next();
    	for (int i = 0; i < n; ++i) {
    		label[i] = s.charAt(i) - 'a';
    	}
    	for (int i = 0; i < n; ++i) {
    		Arrays.fill(memo[i], -1);
    	}
    	for (int i = 0; i < m; ++i) {
    		int a = in.nextInt();
    		int b = in.nextInt();
    		x[i] = a - 1;
    		y[i] = b - 1;
    		++cnt[a - 1];
    	}
    	for (int i = 0; i < n; ++i) {
    		graph[i] = new int[cnt[i]];
    	}
    	int cnt1[] = new int[n];
    	for (int i = 0; i < m; ++i) {
    		graph[x[i]][cnt1[x[i]]++] = y[i];
    	}
    	if (hasCycles()) {
    		out.println(-1);
    		return;
    	}
    	int max = 0;
    	for (int let = 0; let < 26; ++let) {
    		for (int i = 0; i < n; ++i) {
    			max = Math.max(max, get(i, let));
    		}
    	}
    	out.println(max);
    }
    
    private int get(int i, int let) {
    	if (memo[i][let] != -1) return memo[i][let];
    	int ans = 0;
    	for (int x: graph[i]) {
    		ans = Math.max(ans, get(x, let));
		}
    	if (label[i] == let) ++ans;
    	return memo[i][let] = ans;
	}

	private boolean hasCycles() {
		for (int i = 0; i < n; ++i) {
			if (dfsCycles(i)) {
				return true;
			}
		}
		return false;
	}

	private boolean dfsCycles(int v) {
		color[v] = 1;
		for (int u: graph[v]) {
			if (color[u] == 0) {
				if (dfsCycles(u)) return true;
			}
			if (color[u] == 1) return true;
		}
		color[v] = 2;
		return false;
	}

	public void run() {
        try {
            if (systemIO) {
                in = new FastScanner(System.in);
                out = new PrintWriter(System.out);
            } else {
                in = new FastScanner(new File("input.txt"));
                out = new PrintWriter(new File("output.txt"));
            }
            solve();
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
 
    class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
 
        FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }
 
        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }
 
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                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());
        }
 
    }
 
    public static void main(String[] arg) {
        new D().run();
    }
}