珅泽教育的小婷老师正在准备一项搜索实践，她请小泽完成下面的任务。

有 N 块花圃，每块只能选择两种类型之一。M 条关系中，S 表示两块花圃必须同类，D 表示必须异类。判断全部关系能否同时满足。若可以，设关系图有 c 个连通块，输出一个 1 后接 c 个 0；若存在矛盾，输出 0。

输入格式

第一行输入 N、M。接下来 M 行，每行输入字符 S 或 D，以及两个花圃编号。

输出格式

若无解输出 0；否则输出十进制形式的 1 后接 c 个 0，其中 c 是约束图的连通块数量。

2 1
D 2 1

10

6 5
S 2 1
S 3 1
S 4 3
D 5 3
D 6 1

10

10 9
S 2 1
D 3 1
S 4 3
S 5 2
S 6 1
S 7 6
D 8 7
D 9 7
D 10 7

10

数据范围与约定

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 100000