MARRIAGE - RajaRani
The practice of polygamy is said to have originated 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 marriages results in happiness while the rest believe in arranged marriages.
Whatsoever, it's 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:
- A marriage between two persons having a difference of belief, results in a divorce.
- 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.
Each of the M lines contains two integers: i and j.
In the following N lines, the belief of each unmarried person is listed, either "Love" or "Arranged". (quotes for clarification).
Output
For each test case, print a single line: "Number of Deaths" (quotes for qualification), followed by a colon(:) and a space, and then a single integer containing the minimum number of deaths. Refer the sample output for clarification.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 140
1 ≤ M ≤ 10000
1 ≤ i ≤ N
1 ≤ j ≤ N
Example
Input: 1 3 2 1 2 2 3 Love Arranged Love Output: Number of Deaths: 1
hide comments
Oleg:
2023-09-25 06:01:24
Problem is interesting. but Indeed takes some time to figure out what problem needs.
|
|
himanshu_12345:
2017-06-20 13:13:41
@Mohan K
|
|
quock:
2017-05-10 05:21:06
1 2 -->LA
|
|
troll_face:
2017-01-26 15:51:45
@Mohan K
|
|
h_a_k_r:
2015-08-22 18:27:45
Passing all the test cases given here
|
|
rsd_unleashed:
2015-05-19 08:59:54
@Mohan : What do "i and j" denote? Can we assume that all married couples have same belief? Can you re-verify the testcases provided?
|
|
Avi Aryan:
2015-03-08 19:08:12
Thanks @mohan
|
|
Mohan K:
2015-03-08 09:17:14
@avi
|
|
Avi Aryan:
2015-03-05 15:53:23
Can you provide another test case to make the problem clearer ? I have submitted a code and from the logic I have made out, the code should be correct but it's getting WA. Last edit: 2015-03-05 18:37:10 |
Added by: | Mohan K |
Date: | 2014-12-20 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own |