The Great Revegetation

题目描述

一场漫长的干旱让 Farmer John 的 $N$ 块牧场都没有了草。不过，雨季即将到来，是时候“重新植被”了。

在 Farmer John 的棚子里，他有两个桶，每个桶里装着一种不同类型的草籽。他想在他的 $N$ 块牧场中的每一块都种上草，并且在每块牧场上恰好选择一种草来种植。

作为一名奶牛农场主，Farmer John 想确保满足他 $M$ 头奶牛较为特殊的饮食需求。每头奶牛都有两块最喜欢的牧场。有些奶牛有饮食限制：它们只能始终吃同一种草——因此 Farmer John 想确保这类奶牛最喜欢的两块牧场种植的是同一种草。另一些奶牛的限制则完全不同，要求它们吃不同种类的草。对于这些奶牛，Farmer John 当然希望它们最喜欢的两块牧场种植的是不同种类的草。

请帮助 Farmer John 确定，他在 $N$ 块牧场上种草共有多少种不同的方案。

输入格式

第一行包含 $N$（$2 \leq N \leq 10^5$）和 $M$（$1 \leq M \leq 10^5$）。接下来 $M$ 行，每行包含一个字符（'S' 或 'D'），后接两个在范围 $1 \ldots N$ 内的整数，描述某头奶牛最喜欢的两块牧场。 如果字符为 'S'，表示这头奶牛需要其最喜欢的两块牧场种植相同类型的草。 如果字符为 'D'，表示这头奶牛需要其最喜欢的两块牧场种植不同类型的草。

输出格式

输出 Farmer John 在 $N$ 块牧场上种草的方案数。 请将答案用二进制表示。

3 2
S 1 2
D 3 2

10

提示

题目作者：Dhruv Rohatgi 和 Brian Dean

标签: USACO|2019|Silver

来源

USACO|2019|Silver