#include<cstdio>
#include<cstdlib>
#include<stack>

void wa(){ puts("0");exit(0);}
void ac(){ puts("1");exit(0);}

void as(bool f){ if(!f) wa(); }

std::stack<int> S[4];

int main()
{
    FILE *fi = fopen("/var/www/bbs/prob/1337/input.txt", "r"); // Input file
    FILE *fo = fopen("/var/www/bbs/prob/1337/output.txt", "r"); // Output File
    FILE *fs; // Solution File
    
    int i,n;
    fscanf(fi,"%d\n",&n);
    
    int out,ans;
    fscanf(fo,"%d\n",&out);
   // fscanf(fs,"%d\n",&ans);
    
  //  as(out==ans);
    
    for(i=n-1;i>=0;i--)S[0].push(i);
    
    for(i=0;i<out;i++)
    {
        int m;
        char s,e;
        fscanf(fo,"%d : %c->%c\n",&m,&s,&e);
        
        as(m>=1&&m<=n&&s>=65&&s<=68&&e>=65&&e<=68);
        
        m--;
        s-=65;
        e-=65;
        
        as(!S[s].empty()&&S[s].top()==m);
        S[s].pop();
        as(S[e].empty()||S[e].top()>m);
        S[e].push(m);
    }
    
    as(S[0].empty()&&S[1].empty()&&S[2].empty());
    
    for(i=0;i<n;i++)
    {
        as(!S[3].empty()&&S[3].top()==i);
        S[3].pop();
    }
    
    ac();
}