题目描述

Farmer HH 培养了一种十分奇特的奶牛，它有两个头，$a$ 头和 $b$ 头（为了区分方便）。一个头在前面，另外一个在后面，对称分布。问题是：这头牛的两个头具有不同的性格，例如 $1$ 号就的 $a$ 都可能很喜欢 $2$ 号牛的 $a$ 头可是 $1$ 号牛的 $b$ 头却可能不是这样认为的。

(__)     (__)

(oo)     (oo)

 \/-------\/

  ||     ||

  ||-----||

  ~~     ~~

每天早晨他的 $n$ 头牛都会 $1$ 到 $n$ 排成一队。

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

由于每头牛都有两个头，如果这两个头互相关系不错的话呢，吃起草来就会比较愉快，否则没有食欲。但是如果这两头牛不在同一个槽里吃草那就无所谓了。在牛的对列 $1$ 到 $n$ 的顺序不调整的情况下，可以通过调整单个牛的方向（这头牛转 $180$ 度）。这样一定程度下可以减少没有食欲的情况。另外吃草时使用的饲料槽，其长度可以按照需要加到足够长。你的工作是：对于给定的 $n$ 头牛和 $m$ 个互不喜欢的头的情况，求最少需要多少对这样的槽呢？

输入格式

第一行有两个整数，$n$ 和 $m$。下面 $m$ 行，每一行有一对互不喜欢的头的情况。如 4 a 3 b，表示 $4$ 号牛的 $a$ 头不喜欢 $3$ 号牛的 $b$ 头。

输出格式

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

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

2

提示

样例中，$1,2,3$ 在一槽里。$4$ 单独一个槽。

数据规模与约定

对于 $100\%$ 的数据，$n \le 2.5\times 10^4$。