Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIFACEBOOK - Facebook friend

Ph want to find out some intesting information about his friends. He asked some friends to gather all relationship of N friends (relationship may be duplicated). With that data, Ph want to know for each his friend, how many friends of the opposite gender he/she has.

Input

The first line contains two integers N (0 <N ≤ 105) and M (0 ≤ M ≤ 3 * 105), the number of people in the statistics list and the number of relationships counted.

 

The next line consists of N strings containing only "Nam" and "Nu", the i-th sequence is the gender of your ith
In the next M lines, each line has two numbers u and v, representing u and v being friends on Facebook

The next line consists of N strings containing only "Nam" and "Nu", the i-th sequence is the gender of your ith

In the next M lines, each line has two numbers u and v, representing u and v being friends on Facebook

 

Output

Output the number of friends of the opposite gender of each person on a line, separated by spaces.

Sample

Input  5 6 Nam Nu Nu Nam Nam 1 3 1 4 1 2 5 2 4 5 5 1

Output 2 2 1 0 1

 


Added by:Ha Minh Ngoc
Date:2017-01-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.