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.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    
    public static void main(String[] args) throws UnsupportedEncodingException, IOException {
        Reader.init(System.in);
        StringBuilder out = new StringBuilder();
        int n = Reader.nextInt(), m = Reader.nextInt();
        Vertex[] v = new Vertex[n];
        String str = Reader.next();
        for(int i = 0; i < n; i++)
            v[i] = new Vertex(str.charAt(i));
        int s, dest, cnt = 0;
        while(m-- > 0) {
            s = Reader.nextInt() - 1;
            dest = Reader.nextInt() - 1;
            if(s == dest) {
                System.out.println("-1");
                return;
            }
            v[s].edges.add(v[dest]);
            if(!v[dest].hasParent) {
                v[dest].hasParent = true;
                cnt++;
            }
        }
        if(cnt == n) {
            System.out.println("-1");
            return;
        }
        for(int i = 0; i < n; i++)
            if(!v[i].hasParent && !v[i].preVisited && check(v[i])) {
                System.out.println("-1");
                return;
            }
        int max = 0;
        for(int i = 0, j; i < n; i++)
            if(!v[i].hasParent) {
                calc(v[i]);
                for(j = 0; j < 26; j++)
                    if(max < v[i].f[j])
                        max = v[i].f[j];
            }
        out.append(max).append('\n');
        PrintWriter pw = new PrintWriter(System.out);
        pw.print(out);
        pw.close();
    }
    
    static boolean check(Vertex v) {
        if(v.preVisited)
            return false;
        if(v.visited)
            return true;
        v.visited = true;
        for(Vertex vv : v.edges)
            if(check(vv))
                return true;
        v.visited = false;
        v.preVisited = true;
        return false;
    }
    
    static void calc(Vertex v) {
        if(v.visited)
            return;
        v.visited = true;
        int i;
        for(Vertex vv : v.edges) {
            calc(vv);
            for(i = 0; i < 26; i++)
                if(v.f[i] < vv.f[i])
                    v.f[i] = vv.f[i];
        }
        v.f[v.name - 'a']++;
    }
    
}

class Vertex {
    
    char name;
    boolean hasParent, preVisited, visited;
    int[] f;
    List<Vertex> edges;
    
    public Vertex(char c) {
        name = c;
        f = new int[26];
        edges = new LinkedList<Vertex>();
    }
    
}

class Reader {

    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) throws UnsupportedEncodingException {
        reader = new BufferedReader(
                new InputStreamReader(input, "UTF-8"));
        tokenizer = new StringTokenizer("");
    }
    
    static void init(String url) throws FileNotFoundException {
        reader = new BufferedReader(new FileReader(url));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static String nextLine() throws IOException {
        return reader.readLine();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }
}