Define number game (between Alice and Bob) as follows: they agree on a positive number n, then Alice will pick a number x from 1 to n. Each time, Bob will select some intervals and ask Alice whether x is in any of the intervals. To be clear, it's a yes/no question. One special rule about this game is that, Alice can lie once (more precisely at most once).
We're in the middle of the Game. Given n, all questions already been asked by Bob and the answers by Alice respectively. Please compute the minimum number of additional questions that Bob needs to ask to uniquely determine the value of x.
输入描述:
There are at most 10000 test cases. Each case consists of n and m (the number of questions always been asked by Bob), separated by a space. For the following m lines, the first number is c, then the line is followed by c pairs [si, ti] (1 ≤ si ≤ ti ≤ n, 1 ≤ i ≤ c) denoting the i-th interval in this question, then a string "yes" or "no" denoting the answer. You may assume that Alice is strictly obeying the rule and it's always possible to find the answer x if Bob continues to play the game.
1 ≤ n ≤ 1016, 0 ≤ m ≤ 10, and 1 ≤ c ≤ 100
输出描述:
For each test case, print a single line containing one integer -- the minimum number of additional questions required.
示例1
输入
复制
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