#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int kMaxN = 60;
const int64 kInf = 1LL << 62;
const int kSigma = 10 + 26 + 26;

int64 memo[kMaxN][kMaxN][kMaxN];

int Order(const char ch) {
    if (ch <= '9') {
        return ch - '0';
    } else if (ch <= 'Z') {
        return ch - 'A' + 10;
    } else {
        return ch - 'a' + 36;
    }
}

int main() {
    int num_non_terminals, num_productions;
    cin >> num_non_terminals >> num_productions;

    vector<vector<pair<int, int>>> productions(num_non_terminals);  // for x -> yz productions
    vector<int64> terminals(num_non_terminals);                     // for x -> ch productions
    // Input     Result
    // 0 x y z   x -> yz
    // 1 x a     x -> a
    // 2 x       x -> eps
    for (int i = 0; i < num_productions; ++i) {
        int production_type; cin >> production_type;
        if (production_type == 0) {
            int x, y, z; cin >> x >> y >> z;
            productions[x].emplace_back(y, z);
        } else if (production_type == 1) {
            int x; char ch; cin >> x >> ch;
            terminals[x] |= 1LL << Order(ch);
        } else {
            int x; cin >> x;
            terminals[x] |= 1LL << kSigma;  // eps is kSigma
        }
    }

    int start_symbol; cin >> start_symbol;
    string word; cin >> word;
    int word_length = static_cast<int>(word.length());

    memset(memo, -1, sizeof memo);

    function<int64(int, int, int)> Recurse;
    Recurse = [&](int lend, int rend, int nt) {  // min number of operations to transform word[lend..rend] in non-terminal nt
        if (lend > rend) {  // empty substrings can degenerate, but they
            lend = 1;       // are all normalized in the same state
            rend = 0;       // which is (1, 0)
        }

        if (memo[lend][rend][nt] != -1) return memo[lend][rend][nt];
    
        // In the recurrence cycles may occur
        // but you never gain anything by taking them into account
        // so we don't do that
        int64& ans = memo[lend][rend][nt];
        ans = kInf;

        if (lend > rend) {  // (empty, X) may call (empty, Y) + (empty, Z)
            if (terminals[nt] >> kSigma & 1) {  // empty -> eps
                return ans = 0;
            }
        }

        if (lend == rend and (terminals[nt] >> Order(word[lend]) & 1)) {  // nt -> current char
            return ans = 0;
        }

        if (terminals[nt] != 0) {  // nt has a terminal production
            if (lend > rend) {     // delete [lend + 1, rend] and replace lend with the terminal
                ans = 1;           // or if it's empty we add a character
            } else {
                ans = rend - lend + 1;
            }
        }

        for (int k = lend - 1; k <= rend; ++k) {  // Also treat cases with empty to the left and empty to the right
            for (auto p : productions[nt]) {
                int from0, from1; tie(from0, from1) = p;
                ans = min(ans, Recurse(lend, k, from0)
                          + Recurse(k + 1, rend, from1));
            }
        }

        return ans;
    };

    cout << Recurse(0, word_length - 1, start_symbol) << endl;
}