Background

Special for beginners, ^_^

Description

FJ 有 N 头牛，共三种品种，每头牛有可能是三种品种之一。不幸的是，FJ 忘记了哪头牛是哪个品种，它只记得一些两头牛的关系。现在给定K个头系，求每头是哪个品种的所有可能情况。

Format

Input

第一行包括两个整数 N 和K。 以下K行，每行第一个为字母 D或S，紧接着两个整数 X和 Y。D表示 X 和 Y 不同品种，S 表示 X 和 Y 同一品种。保证 X 不等于 Y。

Output

输出所有可能情况。如果有相互矛盾的情况，则输出 0

Samples

4 2
S 1 2
D 1 3

18

Limitation

前三个有 6种可能情况，第 4 个有三种可能情况，总共有 18种可能情况。 2 <= N <= 15 1 <= K <= 50 1 <= X,Y <= N