#include <cstdio>
#include <algorithm>
#include <stack>

using namespace std;
int n, k, size, from, to;
stack<int> S[4];

int main()
{
    FILE *in = fopen("/var/www/bbs/prob/1337/input.txt","r");
    FILE *in2 = fopen("/var/www/bbs/prob/1337/output.txt","r");
    fscanf(in, "%d", &size);
    fscanf(in2, "%d", &n);
    for(int i = size ; i >= 1 ; i-- ) S[0].push(i);
    for(int i = 0 ; i < n ; i++ )
    {
        int a;
        char b, c; 
        fscanf(in2, "%d : %c->%c",&a,&b,&c); 
        from=b-'A', to = c-'A'; 
        if( !S[from].empty() && (S[to].empty() || S[to].top() > S[from].top() ) )
        {
            S[to].push(S[from].top());
            S[from].pop();
        }
        else { printf("0"); return 0; }

    }
    for(int i = 1 ; i <= size ; i++ )
    {
        if( S[3].top() == i ) S[3].pop();
        else { printf("0"); return 0; }
    }
    printf("1");
}