// input code here
```#include<iostream>
using namespace std;
int n,qq,x,y,f[1000001],cnt[1000001],t,a,b,s[1000001];
struct re
{
    int x,y;
    string st;
};
re q[1000001];
int hash(int x)
{
    int t;
    t=x%999999;
    if (s[t]==0)
    {
        s[t]=x;
        f[t]=t;
        return t;
    }
    if (s[t]==x)
    {
        f[t]=t;
     return t;
    }
    for (int i=1;i<=1000000;i++) 
    if (s[i]==0) 
    {
        s[i]=x;
        f[i]=i;
        return i;
    } 
}
int find(int x)
{
    if (f[x]==x) return x;
    int fa=f[x];
    f[x]=find(f[x]);
    cnt[x]=(cnt[fa]+cnt[x])%2;
    return f[x];
}
bool judge(int x,int y,int t)
{
    if ((cnt[x]+cnt[y])%2==1&&t==0) return false;
    if ((cnt[x]+cnt[y])%2==0&&t==1) return false;
    return true; 
}
int main()
{
    cin>>n;
    cin>>qq;
    for(int i=1;i<=qq;i++)
    {
        cin>>q[i].x>>q[i].y>>q[i].st;
        q[i].x--;
        q[i].x=hash(q[i].x);
        q[i].y=hash(q[i].y);    
    }
    for (int i=1;i<=qq;i++)
    {
         if (q[i].st=="even") t=0;
        if (q[i].st=="odd") t=1;
        x=q[i].x; y=q[i].y;
        a=find(x); b=find(y);
        if (a==b) 
        {
                if (!judge(x,y,t)) 
                {
                    cout<<i-1;
                    return 0;
                }
        } 
        if (a!=b) 
        {
            f[a]=b;
            cnt[a]=(cnt[x]+cnt[y]+t)%2;
        } 
    }
    cout<<qq;
    return 0;
}