Problem G
Red/Blue Hackenbush

Sample input 2

Hackenbush is a game played on edges of three colours which all connect to each other or the ground. The edges are all red, green or blue. The first player can hack red and green edges and the second blue and green edges. When a player hacks an edge it is deleted. Any edges that can’t reach the ground are discarded.

The value of a Hackenbush game with red and blue edges can be defined in a few steps. We say that a blue edge is $+1$ and a red edge is $-1$. We also regard any position where whoever plays first loses as having value $0$. By repeating, combining and comparing games we can figure when the value becomes $0$ to determine the value of a given game. Consider as an example the game with one blue edge attached to a single red edge which is attached to the ground. If we take two copies of this game and a single blue edge attached to the ground, we get a game with value $0$. Thus the value of the game we are considering is $-1/2$.

You are given a position of Red/Blue Hackenbush. This is a position in the game Hackenbush where all edges are red or blue.

You need to determine the value of the game. It can be shown that this is always an integer fraction.

Input

The first line contains a two integer $0 \leq n, m \leq 20$, the number of points where the edges meet and the number of edges. The next $m$ lines each describe an edge. Each line contains two integers $-1 \leq x, y \leq n$ with $x, y \neq 0$ which denotes an edge going from point $x$ to point $y$. If $x = -1$ the edge goes from the ground to $y$ and vice versa. After the two integers a single letter follows which is always either R or B. R means the edge is red and B means it is blue.

Output

If the value of the game is $p/2^q$ print p/2q where $p/2^q$ is a fully reduced fraction. If the fraction is an integer, print just that integer without /20. The value of the game is always of this form.

4 5
-1 1 B
-1 2 R
1 2 R
2 3 B
3 4 B

1/2^1

16 20
-1 1 B
1 3 B
1 5 B
-1 2 R
2 4 R
4 6 R
5 6 B
5 7 R
6 8 R
7 9 B
8 9 B
9 10 R
10 11 R
10 11 B
11 12 R
10 13 B
13 14 B
14 14 R
10 15 R
15 16 B

-1/2^1