San Guo Sha

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

San Guo Sha is a popular Board Game. There are four kinds of cards: identity, role, life and magic card. Today we just regard the identity cards. There are four kinds of identity: Lord(ZG), Loyal minister(ZC), Provocateur(NJ) and Rebel(FZ). To win the game Lord and Loyal minister 's goal is make all of Provocateur and rebel dead, Rebel's goal is make Lord dead, Provocateur's goal is to be the last survivor. If Load dead and there's only one Provocateur then he wins (just one Provocateur win), others Rebels win.


In the standard contest, there are score rule:(If you know Chinese, could see the second picture)

The last score equal basic score plus extra score. Now I will tell the identity of everyone and who killed who, please compute everyone' last score.

Input

On the first line of input is a single positive integer, 1<=T<=100, specifying the number of test cases to follow.
Each test case begins with 2 integers N , M (4<=N<=100, 0<=M<N). N is the number of players and M is the relation of who kill who.
Then N string on next line("ZG","ZC","FZ","NJ"), specifying each's identity(begin with 0). I promise each identity will be at least one and there is one and only one ZG.
Then M lines follow, each line with two numbers A B, meaning A killed B.I promise A and B must alive player. If someone was win then you should not deal with the remain instruct.

Output

Please output the everyone's last score in a line, n integers separate by a empty.

Sample Input

3 4 3 ZG ZC NJ FZ 1 3 2 1 0 2 6 1 ZG ZC NJ FZ FZ FZ 3 0 8 7 ZG ZC ZC NJ NJ FZ FZ FZ 3 1 3 2 3 4 3 5 3 6 3 7 3 0

Sample Output

5 6 4 0 0 0 1 11 9 9 1 0 0 20 0 0 0 0

Hint

lcy

Source

HDOJ Monthly Contest – 2010.04.04

提交代码