Grass Seeding

Farmer John has N pastures that are barren after a long drought. With the arrival of the rainy season, it’s time to replant. In his farmhouse, John has two buckets containing different types of grass seeds. He wants to seed each of his N pastures with one type of grass.

However, as a dairy farmer, John must cater to the unique dietary needs of his m cows. Each cow has two favorite pastures. Some cows have a dietary restriction that they should only eat one type of grass, so for such cows, John must plant the same type of grass in their two favorite pastures. Other cows require different types of grass in their favorite pastures. Help John determine the number of valid ways to assign one of the two grass types to each pasture so that all cows’ dietary restrictions are satisfied.

In mathematical terms, consider pastures numbered from 1 to N. For each cow, you are given two pasture indices u and v and a constraint: either they must have the same grass type (denoted by S) or different grass types (denoted by D). Compute the number of valid assignments. If a connected group of pastures (formed by the cow constraints) is consistent, there are exactly 2 choices for that component. Otherwise, if any conflict arises, the answer is 0.

The answer can be mathematically expressed as:

[ \text{Answer} = \begin{cases} 0, & \text{if a contradiction exists} \ 2^{c}, & \text{otherwise} \end{cases} ]

where c is the number of connected components in the graph described by the cow constraints.

inputFormat

The first line contains two integers N and m (the number of pastures and the number of cows, respectively).

Each of the next m lines contains two integers u and v (1-based indices of pastures) and a character that is either S or D representing the cow’s dietary requirement:

• S: the two pastures must be planted with the same type of grass.
• D: the two pastures must be planted with different types of grass.

outputFormat

Output a single integer representing the number of valid assignments of grass types to the pastures, satisfying all the given constraints.

sample

3 2
1 2 S
2 3 D

2