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:

  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.

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

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

hide comments
2023-09-25 06:01:24 Oleg
Problem is interesting. but Indeed takes some time to figure out what problem needs.

Will try to help with description:
Imagine all marriages happened.
and now for each person and each marriage we have to choose
1) divorce person A and person B and pay 1$
2) change believe (from Love to Arranged for example) of any person and pay 1$
3) after we did all choices number of marriages with difference in believes should be 0.
we should minimize $$$ we pay.

Clarification for example in description:
we have 2 options: divorce 1-2 and 2-3 and pay 2$
or change believe of person 2 from Arranged to Love and pay 1$.

Another test case:
1
5 4
1 2
1 3
1 4
1 5
Love
Love
Arranged
Arranged
Arranged

Answer should be 2 (we can divorce 1-3, 1-4, 1-5 or change 1's and 2's believes.

Last edit: 2023-09-25 06:03:08
2017-06-20 13:13:41
@Mohan K
in my opinion answer will be zero of your case
2017-05-10 05:21:06
1 2 -->LA
2 3 -->AL
These are the combination has made for 2 couple . Would you please explain how it's calculated death as 1 point ? Or any hint that would much appreciate thanks.
2017-01-26 15:51:45
@Mohan K

You said in problem that, In the following N lines,the belief of each unmarried person is listed...

My question is:
Is this list of belief is in order ?? For example. if N=5 then Love,Love,Love,Arranged,Arranged is for Unmarried person 1,2,3,4,5 ??
2015-08-22 18:27:45
Passing all the test cases given here
still WA
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?
2015-03-08 19:08:12 Avi Aryan
Thanks @mohan
My program passes your testcase but it's still WA in the main run. BTW, I have some questions -
"help them so that there is minimum number of deaths." - How can we help them ? By advising some people to change religion before their marriage ??
Can we assume a change of belief of person is valid for all his marriages ?
2015-03-08 09:17:14 Mohan K
@avi

1
6 6
1 2
3 2
2 4
3 5
4 5
5 6
Love
Love
Love
Arranged
Arranged
Arranged

Ans:
2
2015-03-05 15:53:23 Avi Aryan
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.