Велике відродження (срібло)#10346

Велике відродження (срібло)

1 секунда

128 мегабайтів

Легка

Через тривалу посуху пасовища фермера Джона залишилися без трави. Однак з наближенням сезону дощів настала пора взятися за відновлення трав'яного покриву. У сараї Джона є два відра із різним насінням трави. Він хоче засіяти травою кожне зі своїх $n$ пасовищ. Кожне пасовище має бути засіяне рівно одним видом трави.

Фермер Джон, який займається молочним тваринництвом, хоче бути впевненим у тому, що він задовольнить особливі дієтичні потреби своїх $m$ корів. У кожної з його $m$ корів є два улюблених пасовища. У деяких корів є дієтичне обмеження: вони повинні постійно їсти тільки один вид трави — тому фермер Джон хоче, щоб на двох улюблених полях будь-якої такої корови був посаджений один і той же тип трави. В інших корів зовсім інші дієтичні обмеження, які вимагають від них їсти різні види трави. Щодо цих корів, фермер Джон, звісно ж, хоче, щоб на двох їхніх улюблених полях були різні типи трави.

Допоможіть фермеру Джону визначити кількість різних способів вирощування трави на його $n$ пасовищах.

Вхідні дані

Перший рядок містить числа $n (2 \leq n \leq 1 0^{5})$ n~(2 \le n \le 10^5) і $m (1 \leq m \leq 1 0^{5})$ m~(1 \le m \le 10^5). Кожен з наступних $m$ рядків містить символ 'S' або 'D', за яким слідують два цілих числа в діапазоні $1 \dots n$ , що описують пару пасовищ, які є улюбленими для однієї з корів фермера Джона. Символ 'S' означає, що корові на її двох улюблених пасовищах потрібна трава одного типу. Символ 'D' означає, що корові на пасовищах потрібні різні типи трави.

Вихідні дані

Виведіть кількість способів, якими фермер Джон може засіяти траву на $n$ пасовищах. Запишіть відповідь у двійковому форматі.

Приклади

Приклад 1

Приклад 2