SP22177 MARRIAGE - RajaRani

The practice of polygamy is said to have origanted in the Salt Lake City where gender is not an important constraint. In order to obtain a clear count of marriages, each unmarried person living in the city is assigned a unique number. Some believe that love marraiges results in happiness while the rest believe in arranged marriages. Whatsoever, its the parents who choose their heir's fiances/fiancees. Once their parents take a decision, their marriage is bound to happen in the near future. But recent studies on this city say that, 1\) A marriage between two persons having a difference of belief, results in a divorce. 2\) In order to avoid this from happening, some people often change their belief on the day of their marriage. But it is sad to note that, both these scenarios results in a death of one of their well-wishers. Given the information about each unmarried person in the city and their fiances/fiancees, help them so that there is minimum number of deaths. **Input:** The first line contains a single integer T, the number of test cases. T test cases follow: The first line of each test case contains two integers, N and M. N : Number of unmarried persons. M : Number of pairs for which their marriage has been fixed. M lines follow: Each of the M lines contains two integers : i & j In the following N lines,the belief of each unmarried person is listed, either "Love" or "Arranged" . ( quotes for claification ). **Output:** For each test case, print a single line: "Number of Deaths"(quotes for qualification), followed by a colon(:) & a space, and then a single integer containg the minimum number of deaths. Refer the sample output for clarification. **Constraints:** 1

N/A

N/A