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.*;

import static java.lang.Math.*;


public class Main {
    BufferedReader br;
    StringTokenizer in;
    PrintWriter pw;
    Random r;
    ArrayList<Integer> g[];
    Stack<Integer> ts;
    boolean used[];
    int us[];
    int[][] d;
    String s;
    void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        s = nextToken();
        ts = new Stack<>();
        used = new boolean[n];
        us = new int[n];
        d = new int[n][];
        g = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            g[nextInt() - 1].add(nextInt() - 1);
        }
        for (int i = 0; i < n; i++) {
            if (us[i] == 0) dfs2(i);
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                dfs(i);
            }
        }
        used = new boolean[n];
        used = new boolean[n];
        int maxans = 0;
        while (ts.size() > 0) {
            if (!used[ts.peek()]) {
                int ans[] = dfs3(ts.peek());
                for (int i = 0; i < 26; i++) {
                    maxans = max(maxans, ans[i]);
                }
            }
            ts.pop();
        }
        pw.print(maxans);
    }


    int[] dfs3(int v) {
        if (used[v]) return d[v];
        int ans[] = new int[26];
        used[v] = true;
        for (int i = 0; i < g[v].size(); i++) {
            int to = g[v].get(i);
            int[] z = dfs3(to);
            for (int j = 0; j < 26; j++) {
                ans[j] = max(ans[j], z[j]);
            }
        }
        d[v] = ans;
        d[v][s.charAt(v) - 'a']++;

        return ans;
    }

    void dfs2(int v) {
        us[v] = 1;
        for (int i = 0; i < g[v].size(); i++) {
            int to = g[v].get(i);
            if (us[to] == 0) dfs2(to);
            else if (us[to] == 1){
                pw.print(-1);
                pw.close();
                System.exit(0);
            }
        }
        us[v] = 2;
    }

    void dfs(int v) {
        used[v] = true;
        for (int i = 0; i < g[v].size(); i++) {
            if (!used[g[v].get(i)]) {
                dfs(g[v].get(i));
            }
        }
        ts.add(v);
    }

    boolean good(long z) {
        long zz = z;
        long sum = 0;
        while (zz > 0) {
            sum += zz % 10;
            zz /= 10;
        }
        if (sum == 10) return true;
        return false;
    }

    //***************************************
    class road {
        int to;

        int w;

        public road(int tto, int ww) {
            to = tto;
            w = ww;
        }
    }

    class pair {
        int a;

        int b;

        public pair(int aa, int bb) {
            a = aa;
            b = bb;
        }

    }

    Comparator<pair> bya = new Comparator<pair>() {
        @Override
        public int compare(pair o1, pair o2) {
            if (o1.a != o2.a) return Integer.compare(o1.a, o2.a);
            return Integer.compare(o1.b, o2.b);
        }
    };
    Comparator<pair> byb = new Comparator<pair>() {
        @Override
        public int compare(pair o1, pair o2) {
            if (o1.b != o2.b) return Integer.compare(o1.b, o2.b);
            return Integer.compare(o1.a, o2.a);
        }
    };
    Comparator<road> byw = new Comparator<road>() {
        @Override
        public int compare(road o1, road o2) {
            if (o1.w != o2.w) return Integer.compare(o1.w, o2.w);
            return Integer.compare(o1.to, o2.to);
        }
    };
    Comparator<road> byto = new Comparator<road>() {
        @Override
        public int compare(road o1, road o2) {
            return Integer.compare(o1.to, o2.to);
        }
    };

    class node {
        int sz;
        int val;
        //        long sum;
        node L;
        node R;
        int prior;

        public node(int val) {
            this.val = val;
            prior = r.nextInt();
            L = null;
            R = null;
            sz = 1;
//            sum = (long)val * val;
        }

        void add(int z) {
            val = val + z;
//            sum = (long)val * val;
        }
    }

    void relax(node c) {
        if (c == null) return;
        c.sz = sfsz(c.L) + sfsz(c.R) + 1;
//        c.sum = sfsum(c.L) + sfsum(c.R) + c.val * c.val;
    }

    int sfsz(node c) {
        if (c == null) return 0;
        return c.sz;
    }

    node merge(node a, node b) {
        if (a == null) return b;
        if (b == null) return a;
        if (a.prior > b.prior) {
            a.R = merge(a.R, b);
            relax(a);
            return a;
        } else {
            b.L = merge(a, b.L);
            relax(b);
            return b;
        }
    }

    pairn split(node c, int s) {
        if (c == null) return new pairn(null, null);
        if (sfsz(c.L) >= s) {
            pairn p = split(c.L, s);
            c.L = p.b;
            relax(c);
//            relax(p.a);
            return new pairn(p.a, c);
        } else {
            pairn p = split(c.R, s - sfsz(c.L) - 1);
            c.R = p.a;
            relax(c);
//            relax(p.b);
            return new pairn(c, p.b);
        }
    }

    class pairn {
        node a;
        node b;

        public pairn(node a, node b) {
            this.a = a;
            this.b = b;
        }
    }

    String nextToken() throws IOException {
        while (in == null || !in.hasMoreTokens()) {
            in = new StringTokenizer(br.readLine());
        }
        return in.nextToken();
    }

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

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

    //    boolean check()
    public void run() throws IOException {
        r = new Random(5);
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new OutputStreamWriter(System.out));
//        br = new BufferedReader(new FileReader("input.txt"));
//        pw = new PrintWriter(new FileWriter("output.txt"));
//        br = new BufferedReader(new FileReader("river.in"));
//        pw = new PrintWriter(new FileWriter("river.out"));
        solve();
        pw.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}