i拆i和i+n两个点，按奇偶性联通即可，记得之前需要离散化
#define _CRT_SECURE_NO_WARNINGS
#pragma _attribute_((optimize("-O2")))
#pragma comment(linker, "/STACK:102400000,102400000")

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <cstdio>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <string>
#include <sstream>
#include <ctime>
#include <complex>
#include <iomanip>
#define Endl endl
#define int long long

//#define Local

using namespace std;

#define N 20010
int s[N], R[N];
void init(int n)
{
	for (int i = 0; i <= n; i++)
		s[i] = i, R[i] = 0;
}
int find(int p)
{
	return p = p == s[p] ? p : find(s[p]);
}
void uni(int p, int q)
{
	int fp = find(p), fq = find(q);
	if (fp == fq)
		return;
	if (R[fp] > R[fq])
		s[fq] = s[fp];
	else
	{
		s[fp] = s[fq];
		if (R[fp] == R[fq])
			R[fq]++;
	}
}

bool isame(int p, int q)
{
	if (find(p) == find(q))
		return 1;
	return 0;
}


vector<int> v;
int getid(int x)
{
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

signed main(int argc, char *argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	

	int n, m;
	cin >> n >> m;
	vector<pair<int, pair<int, int> > > all(m);

	for (int i = 0; i < m; i++)
	{
		string tmp;
		cin >> all[i].second.first >> all[i].second.second >> tmp;
		if (tmp == "even")
			all[i].first = 1;
		else
			all[i].first = 0;
		all[i].second.first--;
		v.push_back(all[i].second.first);
		v.push_back(all[i].second.second);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());

	n = v.size();
	init(2 * n);
	for (int i = 0; i < m; i++)
	{
		if (all[i].first)
		{
			if (isame(getid(all[i].second.first), getid(all[i].second.second) + n) || isame(getid(all[i].second.first) + n, getid(all[i].second.second)))
			{
				cout << i << endl;
				return 0;
			}
			uni(getid(all[i].second.first), getid(all[i].second.second));
			uni(getid(all[i].second.first) + n, getid(all[i].second.second) + n);
		}
		else
		{
			if (isame(getid(all[i].second.first), getid(all[i].second.second)) || isame(getid(all[i].second.first) + n, getid(all[i].second.second) + n))
			{
				cout << i << endl;
				return 0;
			}
			uni(getid(all[i].second.first), getid(all[i].second.second) + n);
			uni(getid(all[i].second.first) + n, getid(all[i].second.second));
		}
	}
	cout << m << endl;

#ifdef Local
	cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
#endif
	return 0;
}