题目描述

如下定义一个在 Alice 和 Bob 之间进行的数字游戏：选中一个正整数 $n$, 之后 Alice 会在 $1$ 到 $n$ 之间选取一个整数 $x$, 每次 Bob 会选择一些区间并询问 Alice $x$ 是不是在其中的某个区间内，一个特殊的规则就是，Alice 可以撒谎至多一次。

在游戏中，给定一个 $n$, 所有的问题已经由 Bob 提出，并由 Alice 一一回答。请计算 Bob 为了确定整数 $x$ ，最少需要额外问几次。

输入格式

每个测试点最多包含 $10000$ 组测试数据，每组数据包含 $n$, $m$ （Bob 已经问的问题数），用一个空格隔开

下面紧跟 $m$ 行，每行第一个整数 $c$, 之后 $c$ 对 $[s_i, t_i], (1\le s_i \le t_i \le n)$, 表示本次询问中的第 $i$ 个区间，最后一个字符串 yes 或 no 表示 Alice 给出的答案，假设 Alice 十分遵守规则，且 Bob 如果继续进行游戏，一定能确定 $x$ 的值

输出格式

对于每组测试数据，输出一行包含一个整数，表示最少需要额外问的次数

样例

1 0
2 0
2 2
1 1 1 yes
1 1 1 no
2 2
1 1 1 yes
1 1 1 yes
2 3
1 1 1 yes
1 1 1 no
1 1 1 yes

0
3
1
0
0

数据范围与提示

$1 \leq n \leq 10^{16}$, $0 \leq m \leq 10$, 且 $1 \leq c \leq 100$

特别鸣谢楼天城和吉如一提供试题，数据。