题目描述

$\red{Farmer HH}$培育了一种十分奇特的奶牛，它有两个头，$\red{A}$头和$\red{B}$ 头（为了区分方便）。一个头在前面，另外一个在后面，对称分布。 问题是:这头牛的两个头具有不同的性格，例如$\red{1}$号牛的$\red{A}$都可能很 喜欢$\red{2}$号牛的$\red{A}$头可是$\red{1}$号牛的$\red{B}$头却可能不是这样认为的。每天早晨他的$\red{N(1<=N<=25000)}$头生都会$\red{1}$到$\red{N}$排成一队等以 通过调整单个牛的方向（这头生转$\red{180}$度）。

这样一定程度下可以减少没有食欲的情况。另外吃草时使用的饲料槽，其长度可以按照需要加到足够长。你的工作是:对于给定的$\red{N}$头牛和$\red{M(1<=M<=50,000)}$ 个互不喜欢的头的情况，求最少需要多少对这样的槽呢?

一对等长度的饲料槽分为前后两个，可以使连续的若干头牛有草 吃，而且在吃草的过程中不会出现某头牛的一个头在第$\red{i}$对饲料槽中 吃草而另外一个头在第$\red{i+1}$对饲料槽中吃草的情况。

由于每头牛都有两个头，如果这两个头互相关系不错的话呢吃起草来就会比较愉快，否则没有食欲。

但是如果这两头牛不再同一个槽吃草而另外一个头在第$\red{i+1}$对饲料槽中吃草的情况。

由于每头牛都有两个头，如果这两个头互相关系不错的话呢吃起草来就会比较愉快，否则没有食欲。但是如果这两头牛不再同一个槽里吃草那就无所谓了。在牛的队列$\red{1}$到$\red{N}$的顺序不调整的情况下，口以通过调整单个生的方向（这头牛转$\red{180}$度）。

这样一定程度下可以减少没有食欲的情况。另外吃草时使用的饲料槽，其长度可以按照需要加到足够长。你的工作是:对于给定的$\red{N}$头牛和$\red{M(1<=M<=50,000)}$ 个互不喜欢的头的情况，求最少需要多少对这样的槽呢?

输入格式

第一行有两个整数，$\red{N}$和$\red{M}$。

下面$\red{M}$行，每一行有一对互不喜欢的头的情况。

如$\red{4 A 3 B，}$表示$\red{4}$号牛的$\red{A}$头不喜欢$\red{3}$号牛的$\red{B}$头。

输出格式

输出一个整数，最少的槽数。

样例

输入样例

4 5
3 B 1 B
4 A 3 A
2 B 1 B
4 B 2 A
3 A 2 B

输出样例

2

Hint

提示

样例中，$\red{1}$、$\red{2}$、$\red{3}$在一槽里。$\red{4}$单独一个槽。 数据规模对于$\red{100\%}$的数据，$\red{N <= 25000}$