Algoritmizace B4B33ALG
Algoritmizace

Lakes and Waterfalls

Assignment

The management of the Highlands Lakes National Park is planning a new collection of short tourist routes in the Park. Each route will visit exactly four points of interest. A point of interest is either a lake or a waterfall in the hills. A route will start at a lake, than it will proceed to a waterfall, then it will go to another lake, and then to another waterfall, and finally it will return to the lake where it started. There are many paths connecting lakes and waterfalls and it is obvious that there are more possibilities to construct a route.

img1
Image 1. Paths schemes depicting input data in Examples bellow. Lakes and waterfalls are depicted as circles and triangles, respectively. In case a), there are eight possible routes: Two routes start at lake 0, four routes start at lake 4 and two routes start at lake 2. In case b), there are twelve possible routes: Two routes start at each of the lakes 2, 3, 8 and six routes start at lake 4. In case c), there are 36 routes, any sequence of sites consisting of a lake, a waterfall, another lake, and another waterfall, defines a route.

The task

You are given the scheme of paths connecting the points of interest in the Park. Find the total number of different routes.
Two routes are considered different if there is least one site which is a part of one route and not a part of the other route or if the routes visit the same sites in a different order.

Input

The first input line contains two integers N, M separated by space. The values indicate (in this order) the number of points of interest and the number of paths between them. The points of interest are labeled by integers 0, 1, …​, N−1. Next, there are M text lines, each describes one path. The path connects two points of interest, the line contains their labels separated by space. Finally, there are N text lines. Each line specifies the type of a particular point of interest. The line contains the label of the point of interest and a capital letter L for lake or W for waterfall. The values are separated by space. The order of paths and points of interest in the input is arbitrary.
It holds, 1 ≤ N ≤ 104, 1 ≤ M ≤ 106.

Output

The output contains one text line with one integer representing the total number of possible planned turist routes.

Examples

Example 1

Input
8 12
0 1
0 5
1 5
1 4
5 4
5 6
1 2
4 2
4 6
2 6
2 3
7 6
0 L
4 L
2 L
3 L
1 W
5 W
7 W
6 W
Output
8

The data of Example 1 are depicted in Image 1a).

Example 2

Input
9 16
0 1
1 2
3 4
4 5
6 7
7 8
0 3
3 6
1 4
4 7
2 5
5 8
0 4
4 2
4 8
3 7
0 W
1 W
2 L
3 L
4 L
5 W
6 W
7 W
8 L
Output
12

The data of Example 2 are depicted in Image 1b).

Example 3

Input
6 9
0 1
0 2
0 3
4 1
4 2
4 3
5 1
5 2
5 3
1 L
2 L
3 L
0 W
4 W
5 W
Output
36

The data of Example 3 are depicted in Image 1c).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Public data