solution

#include <bits/stdc++.h>

using namespace std;

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")

#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"

#define sz(a) ((int)(a).size())
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define tr(c, it) for (auto it = (c).begin(); (it) != (c).end(); it++)
#define pres(c, val) ((c).find(val) != (c).end())      //
#define cpres(c, val) (find(all(c), val) != (c).end()) //

#define pb push_back
#define mp make_pair
#define F first
#define S second

#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define forb(i, a, b) for (int i = (b); i >= (a); i--)
#define fo(i, n) forf(i, 0, n)
#define fob(i, n) forb(i, 0, n - 1)

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;

const int INF = 9e18;
// const int N = 1e9 + 7;
const int N = 998244353;
const double eps = 1e-9;

const auto start_time = std::chrono::high_resolution_clock::now();

void zark() {
    #ifdef ZARK
        auto end_time = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> diff = end_time - start_time;
        cerr << "Time Taken: " << diff.count() << "s\n";
    #endif
}

#ifdef ZARK
  #include "/home/aranjan/Desktop/CP/header.h"
  #else
  #define debug(args...) 42
#endif

/* ------------------ Actual Coding Starts ------------------ */

map<int, int> par;
map<int, int> s;

void mset(int v) {
    par[v] = v;
    s[v] = 1;
}

int fset(int v) {
    if(v == par[v]) return v;
    return par[v] = fset(par[v]);
}

void uset(int a, int b) {
    a = fset(a);
    b = fset(b);
    if(a != b) {
        if(s[a] < s[b]) swap(a, b);
        s[a] += s[b];
        par[b] = a;
    }
}

int off = 1e18;

void solve() {
    int n,m;
    cin >> n >> m;
    bool f = false;
    vector<pair<pii, int>> e;
    int cnt = 0;
    fo(i, m) {
        int u, v;
        string inp;
        cin >> u >> v >> inp;
        int c = inp == "even";
        mset(u-1);
        mset(v);
        mset(u-1+off);
        mset(v+off);
        e.pb({{u, v}, c});
    }
    fo(i, m) {
        int u=e[cnt].F.F, v=e[cnt].F.S, c=e[cnt].S;
        if(u <= 0 || u > n || v <= 0 || v > n || u > v) {cout << cnt << endl; f = true; break;}
        u--;
        if(c) {
            if(fset(u) == fset(off+v) || fset(u+off) == fset(v)) {cout << cnt << endl; f = true; break;}
            else {uset(u, v); uset(off+u, off+v);}
        }
        else {
            if(fset(u) == fset(v) || fset(u+off) == fset(v+off)) {cout << cnt << endl; f = true; break;}
            else {uset(u, v+off); uset(u+off, v);}
        }
        cnt++;
    }
    if(!f) cout << cnt << endl;
    int _;
    cin >> _;
}

int32_t main() {
    fastio;
    #ifdef ZARK
        freopen("input.in", "r", stdin);
    #endif

    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
    // cout << fixed << setprecision(10);

    solve();
    zark();
    return 0;
}