import java.util.*;
import java.io.*; 
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
    //SOLUTION BEGIN
    int emp = 62;
    int pos(char c){
        if('0'<=c && c<='9')return c-'0';
        else if('a'<=c && c<='z')return c-'a'+10;
        else if('A'<=c && c<='Z')return c-'A'+36;
        return -1;
    }
    TreeSet<int[]>[] non_terminal;
    TreeSet<Integer>[] terminal;
    void solve(int TC) throws Exception{
        int num = ni(), numProductions = ni();
        non_terminal = new TreeSet[num];
        terminal = new TreeSet[num];
        for(int i = 0; i< num; i++){
            non_terminal[i] = new TreeSet<>((int[] i1, int[] i2) -> {
                if(i1[0]!=i2[0])return Integer.compare(i1[0], i2[0]);
                return Integer.compare(i1[1], i2[1]);
            });
            terminal[i] = new TreeSet<>();
        }
        for(int i = 0; i< numProductions; i++){
            int ty = ni();
            if(ty==0)non_terminal[ni()].add(new int[]{ni(), ni()});
            else if(ty==1)terminal[ni()].add(pos(n().charAt(0)));
            else terminal[ni()].add(emp);
        }
        int start = ni();
        string = n();S = string.length();
        long[][][] dp = new long[S][S][num];
        for(int i = 0; i< S; i++)
            for(int j = 0; j< S; j++)
                for(int k = 0; k< num; k++)
                    dp[i][j][k] = IINF;
        pn(calc(dp, 0, string.length()-1, start));
    }
    String string;
    long calc(long[][][] dp, int l, int r, int nt){
        if(l>r){
            //l>r here represent empty strings, which may be valid, because of type 2 production
            l = 1;r = 0;
        }
        if(dp[l][r][nt]!=IINF)return dp[l][r][nt];
        //Empty string, terminal also allow empty string.
        if(l>r && terminal[nt].contains(emp))return dp[l][r][nt] = 0;
        //Single character which is present in terminal representation
        if(l==r && terminal[nt].contains(pos(string.charAt(l))))return dp[l][r][nt] = 0;
        if(!terminal[nt].isEmpty()){
            //This character may terminate here, having a character not present in string[l..r]
            //If character is present in string[l..r], it is already handles in previous if condition
            if(l>r)dp[l][r][nt] = Math.min(dp[l][r][nt], 1);
            else dp[l][r][nt] = r-l+1;
        }
        for(int k = l-1; k<= r; k++)
            for(int[] i:non_terminal[nt])
                //We try all possible productions, for all positions. l = l-1, because we try empty strings for left and right productions too.
                dp[l][r][nt] = Math.min(dp[l][r][nt], calc(dp, l,k,i[0])+calc(dp, k+1,r,i[1]));
        return dp[l][r][nt];
    }
    int S = 60;
    //SOLUTION END
    long mod = (long)1e9+7, IINF = Long.MAX_VALUE;
    final int INF = (int)2e9, MAX = (int)2e5+1;
    DecimalFormat df = new DecimalFormat("0.000000000");
    double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
    static boolean multipleTC = false, memory = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        int T = (multipleTC)?ni():1;
        //Solution Credits: Taranpreet Singh
        for(int i = 1; i<= T; i++)solve(i);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n(){return in.next();}
    String nln(){return in.nextLine();}
    int ni(){return Integer.parseInt(in.next());}
    long nl(){return Long.parseLong(in.next());}
    double nd(){return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine(){
            String str = "";
            try{    
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }   
            return str;
        }
    }
}