#include <iostream>
#include <string>
#include <map>
#include <cassert>

using namespace std;

#define EVEN 0
#define ODD 1
#define NCONSTRAINT_MAX 5000

class Constraint {
public:

	int begin, end;
	int parity;

};

class Node {
public:

	Node *child, *sibling;
	int degree;
	int key, parity, noddcut;

};

class Cluster {
public:

	Cluster() : head(NULL) {}

	void insert( const Constraint &c ) {
		// binomial-heap-insert(c.end, c.parity)
		Node *one = new Node;
		one->child = NULL;
		one->sibling = head;
		one->degree = 0;
		one->key = c.end;
		one->parity = c.parity;
		one->noddcut = 0;
		head = one;
		regularize();
	}

	void unify( Cluster *c ) {
		// binomial-heap-unify-modified-parity
		head = merge(head, c->head);
		delete c;
		regularize();
	}

	Constraint peek() const {
		// binomial-heap-min
		assert( head != NULL );
		Node *curr = head, *minNode = head;
		while ( curr != NULL ) {
			if ( curr->key < minNode->key ) minNode = curr;
			curr = curr->sibling;
		}

		Constraint result;
		result.end = minNode->key;
		result.parity = (minNode->noddcut%2 == 0)? minNode->parity : !minNode->parity;
		return result;
	}

	Constraint extract() {
		// binomial-heap-extract
		assert( head != NULL );

		Node *prev = NULL, *curr = head, *minNode = head, *minPrev = NULL;
		while ( curr != NULL ) {
			if ( curr->key < minNode->key ) minNode = curr, minPrev = prev;
			prev = curr;
			curr = curr->sibling;
		}

		Node *removing = (minPrev == NULL)? head : minPrev->sibling;

		if ( minPrev == NULL )
			head = head->sibling;
		else
			minPrev->sibling = minPrev->sibling->sibling;

		const int noddcut = minNode->noddcut;
		Constraint result;
		result.end = minNode->key;
		result.parity = (minNode->noddcut%2 == 0)? minNode->parity : !minNode->parity;

		Node *children = removing->child;
		delete removing;

		if ( children == NULL ) return result;

		curr = children;
		while ( curr != NULL ) curr->noddcut += noddcut, curr = curr->sibling;
		head = merge(reverse(head), children);
		regularize();
		return result;
	}

	bool empty() const {
		// binomial-heap-empty
		return (head == NULL);
	}

	void cutOdd() const {
		// modified-binomial-heap
		Node *curr = head;
		while ( curr != NULL )
			curr->noddcut++, curr = curr->sibling;
	}

private:
	Node *head;


	Node *merge( Node *L, Node *R ) {
		Node sentinel, *tail, *curr;

		sentinel.sibling = NULL;
		tail = &sentinel;

		while ( L != NULL && R != NULL ) {
			if ( L->degree < R->degree )
				curr = L, L = L->sibling;
			else
				curr = R, R = R->sibling;
			tail->sibling = curr;
			tail = curr;
		}

		if ( L != NULL )
			tail->sibling = L;
		else
			tail->sibling = R;
	
		return sentinel.sibling;
	}

	Node *reverse( Node *head ) {
		Node *prev = NULL, *curr = head, *next;
		while ( curr != NULL )
			next = curr->sibling, curr->sibling = prev, prev = curr, curr = next;
		return prev;
	}

	void regularize() {
		if ( head == NULL ) return;

		Node *prev, *curr, *next;
		prev = NULL;
		curr = head;
		next = curr->sibling;

		while ( next != NULL ) {
			if ( curr->degree != next->degree || next->sibling != NULL && next->sibling->degree == next->degree ) {
				prev = curr, curr = next, next = next->sibling;
				continue;
			}

			if ( curr->key < next->key )
				curr->sibling = next->sibling, next->sibling = curr->child,
				curr->child = next, next->noddcut -= curr->noddcut, next = curr->sibling, curr->degree++;
			else {
				curr->sibling = next->child, next->child = curr, curr->noddcut -= next->noddcut, next->degree++;
				if ( prev == NULL )
					head = next;
				else
					prev->sibling = next;
				curr = next, 	next = curr->sibling;
			}
		}
	}

};

bool isFeasible( int bound, Constraint C[] ) {
	map<int, Cluster*> M;

	for ( int i = 0; i <= bound; i++ ) {
		if ( M.find(C[i].begin) == M.end() ) M[C[i].begin] = new Cluster();
		M[C[i].begin]->insert(C[i]);
	}

	map<int, Cluster*>::iterator it;
	bool feasible = true;
	for ( it = M.begin(); it != M.end(); it++ ) {
		Cluster *cluster = it->second;

		int end = cluster->peek().end;
		bool even = false, odd = false;
		while ( !cluster->empty() && cluster->peek().end == end )
			if ( cluster->extract().parity == EVEN )
				even = true;
			else
				odd = true;

		if ( even && odd ) {
			feasible = false;
			break;
		}

		// 空の場合は解放する.
		if ( cluster->empty() ) {
			delete cluster;
			continue;
		}

		// 残りのもののパリティを調整して次の位置に追加またはマージ.
		if ( odd ) cluster->cutOdd();

		if ( M.find(end+1) == M.end() )
			M[end+1] = cluster;
		else
			M[end+1]->unify(cluster);
	}

	return feasible;
}

int main() {
	int length, nconstraint;
	string tmp;

	Constraint C[NCONSTRAINT_MAX];

	while ( cin >> length >> nconstraint, length != -1 ) {
		for ( int i = 0; i < nconstraint; i++ )
			cin >> C[i].begin >> C[i].end >> tmp, C[i].parity = (tmp[0] == 'e')? EVEN : ODD;

		int feasibleBound = 0, upperBound = nconstraint - 1;
		while ( upperBound - feasibleBound > 1 ) {
			const int mid = feasibleBound + 4*(upperBound-feasibleBound)/5;

			if ( isFeasible(mid, C) )
				feasibleBound = mid;
			else
				upperBound = mid - 1;
		}
		if ( isFeasible(upperBound, C) ) feasibleBound = upperBound;

		cout << feasibleBound+1 << endl;
	}

	return 0;
}