Длительная засуха оставила без травы \(N\) пастбищ фермера Джона.
Поскольку приближается сезон дождей, время восстанавливать траву высевая её.
В сарае у ФД имеется два ведра, каждое содержит семена травы своего типа.
ФД хочет засеять травой каждое из его \(N\) пастбищ, выбирая ровно один
тип для каждого пастбища.
ФД хочет обеспечить разнообразие диеты для своих \(M\) коров. Каждая из них
имеет два любимых пастбища. Некоторые из его коров имеют ограничение по диете
и это означает, что они постоянно должны есть траву только одного типа.
Поэтому ФД должен обеспечить один и тот же тип травы на обоих любимых
пастбищах каждой коровы. Некоторые из коров имеют другие диетные ограничения
- они должны разные типы травы. Для этих коров ФД должен обеспечить, чтобы
два их любимых пастбища содержали разные типы травы.
Определите количество различных способов, которыми ФД может засадить
травой эти \(M\) пастбищ.
ФОРМАТ ВВОДА (файл revegetate.in):
Первая строка ввода содержит \(N\) (\(2 \leq N \leq 10^5\)) и \(M\)
(\(1 \leq M \leq 10^5\)). Каждая из последующих \(M\) строк содержит символ
'S' или 'D', за которым следуют два числа в интервале \(1 \ldots N\),
описывающих пару пастбищ, которые являются любимыми для этой коровы.
Символ 'S' означает, что корова должна есть один и тот же тип травы на обоих
своих пастбищах, символ 'D' означает, что корова должна есть разные тип травы
на обоих своих пастбищах.
ФОРМАТ ВЫВОДА (файл revegetate.out):
Выведите количество способов которыми ФД может рассадить траву на своих
пастбищах. Ответ вывести в двоичном формате.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
S 1 2
D 3 2
|
10
|