P5543 [USACO19FEB] The Great Revegetation S

A long drought has left Farmer John’s $N$ pastures without grass. However, with the arrival of the rainy season, it is time to “revegetate”. In Farmer John’s barn, he has two buckets, each containing a different type of grass seed. He wants to plant grass in each of his pastures, choosing one type of grass for each pasture. As a dairy farmer, Farmer John wants to make sure he can meet the special dietary needs of his cows. His $m$ cows each have two favorite pastures. Some cows have a dietary restriction that they should eat only one type of grass, so Farmer John wants to make sure that the same type of grass is planted in the two pastures favored by such cows. Other cows have a different dietary restriction that requires them to eat different types of grass. For those cows, Farmer John of course wants to make sure that there is different grass in their two favorite pastures. Please help Farmer John determine the number of different ways to plant grass on his $N$ pastures.

The first line of input contains two integers $N$ ($2\le N\le10^5$) and $m$ ($1\le m\le10^5$). The next $m$ lines each describe one cow. Each line begins with a character `S` or `D`, indicating whether this cow needs the same (`S`) or different (`D`) grass types, followed by two integers in $1\sim N$, representing the two pastures favored by this cow.

Output the total number of ways Farmer John can plant grass on his $N$ pastures. Please write your answer in binary.

USACO February 2019 Contest, Silver Division, Problem 3. Translated by ChatGPT 5