22172_TheGreatMingDynasty

In 1368 A.D., in China, the king Yuanzhang Zhu won the war and build up the Ming dynasty. In order to manage this huge country efficiently, he rebuilt the traffic network of China. This was absolutely a great project, and the people who in charge named Bowen Liu. As we all know, ancient kings wanted their dynasty can keep forever. In China, kings used Fengshui which is a kind of metaphysics, and Bowen Liu is a very famous Fengshui master in Chinese history.

Figure 1 Relationship between 5 elements

The project is based on the present traffic network. There were many cities all over the country, and many roads connecting two cities had been built. The rebuilding rules according as Chinese traditional five elements system -- Gold, Wood, Water, Fire and Ground. In this system, five elements compose as a circuit. As in the figure, one element is borned by another element, and also it will born another element too. But adjacent elements in the circuit will kill each other, we call that collision. In ancient Chinese philosophy, every thing has its represent element, so as city. By Master Bowen Liu, the particular rule is like that:

Every city has one represent element. Suppose a road Y connecting City A and City B.

1. If A's represent element will kill B's, then this road will be destroy!

2. If no collision between A and B, and A's element boms B's, then this road would be used as a directed road from A to B. So as to B's element boming A's.

3. Otherwise, the road will be stay as an undirected road.

Here is a simple example:

Jinling (Today's Nanjing City) is the capital, and in the middle of the country, its element is Ground.

Nanhai (Today's Guangzhou City) in the south of China, its elements is Fire.

Dadu (Today's Beijing, Dadu is named by the last dynasty Yuan) in the north of China, its element is Water.

Mingzhou (Several years later, it was changed to be Ningbo by Yuanzhang Zhu) in the east of China, its element is Wood.

Chengdu in the west of China, its element is Gold.

After this rebuilding project, the whole country divided to several provinces. The province dividing rule is that:

1. The less province the better.

2. In a province, any city can go to any other city of the province.

And, of course, some province only one city is possible.

For the above example, Jinling, Nanhai, Dadu, Mingzhou and Chengdu form a province.

Right now, we have the map of the traffic network before rebuilding, including all the cities and original roads. And we have got the important records from Bowen Liu which defines represent elements of all the cities. We want to find out how many provinces of China at that age.

For convenience, city names have been hided, we used natural number 0 ... N-1 ( N ≤ 100 ) to represent the cities.

There are several set of data.

For each set of data, the first line includes two integers: N, M. N is the number of cities and M is the number of original roads before rebuilding.

There're N lines. Every line includes a word from (Gold, Wood, Water, Fire or Ground). The first line point out the represent element of City 0, the second line points out the represent element of City 1, so that the last line points out the represent element of City N-1.

At last, there're M lines. Every line includes two numbers A and B, means there's an original road connecting City A and City B before rebuilding.

The output should be an integer pointing out the number of province.

5 8
Ground
Fire
Water
Wood
Gold
0 1
0 2
0 3
0 4
1 4
4 2
2 3
3 1

1

It's corresponding to the sample inside the problem depict.

0 -> Jinling

1 -> Nanhai

2 -> Dadu

3 -> Mingzhou

4 -> Chengdu