| Codeforces Beta Round 56 |
|---|
| Закончено |
Однажды утром Cereal Guy обнаружил, что все его хлопья пропали. Вместо них он нашел записку. Оказывается, его хитроумный сосед спрятал хлопья в одном из n ящиков. Ящики стоят в один ряд, они пронумерованы от 1 до n слева направо. Сосед оставил подсказки вида: «Спрятано левее i-го ящика» ("To the left of i"), «Спрятано правее i-го ящика» ("To the right of i"). Такие подсказки означают, что в i-ом ящике так же нет хлопьев. Cereal Guy хочет узнать минимальное количество ящиков, которые ему нужно обязательно проверить, чтобы найти хлопья с учетом всех подсказок, либо выяснить, что подсказки противоречат и сосед его обманул, то есть ни в одном из ящиков нет хлопьев.
В первой строчке находятся два целых числа n и m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000) — количество ящиков и количество подсказок соответственно. В следующих m строках находятся подсказки вида "To the left of i" и "To the right of i", где i — целое число (1 ≤ i ≤ n). Подсказки могут совпадать.
В ответе должно содержаться ровно одно число — количество ящиков, которые обязательно нужно проверить, или "-1", если подсказки противоречивы.
2 1
To the left of 2
1
3 2
To the right of 1
To the right of 2
1
3 1
To the left of 3
2
3 2
To the left of 2
To the right of 1
-1
