#include <cassert>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include "optimization.h"

using namespace std;

const int N = 10000;

int p[N], Size[N], w[N];
void get( int &v, int &sum ) {
	while (v != p[v])
		sum ^= w[v], v = p[v];
}

unordered_map<int, int> m(N);
int index( int x ) {
	int &r = m[x];
	if (!r)
		r = m.size(), p[r] = r, Size[r] = 1;
	return r;
}

int main() {
	char s[16];
	while (readInt() != -1) {
		int i, n = readInt(), res = n;
		m.clear();
		for (i = 0; i < n; i++) {
			int sl = 0, l = index(readInt() - 1); 
			int sr = 0, r = index(readInt());
			readWord(s);
			int odd = !strcmp(s, "odd");
			get(l, sl);
			get(r, sr);
			if (l != r) {
				if (Size[l] > Size[r])
					swap(l, r);
				w[l] = odd ^ sl ^ sr, p[l] = r, Size[r] += Size[l];
			} else if (sl ^ sr ^ odd)
				res = min(res, i);
		}
		writeInt(res, '\n');
	}
}
