SP22177 MARRIAGE - RajaRani

传闻一夫多妻制起源于盐湖城，在那里，性别并不是结婚的限制条件。为了统计婚姻数量，每位未婚者都有一个独特的编号。人们对于婚姻的看法分为两派：一些人认为自由恋爱带来幸福，另一些则偏爱包办婚姻。 无论如何，父母总是为子女挑选未来的伴侣。一旦父母做出决定，婚礼就不可避免地要举行。然而，最近对该城市进行的研究指出： 1. 如果结婚的两人信仰不同，婚姻会以离婚告终。 2. 为了防止离婚，一些人在结婚当天会改变信仰。 但遗憾的是，无论哪种情况，都会导致他们的一位亲友的去世。现在，给定城市中每个未婚者及其未婚伴侣的信息，请帮助他们尽量减少死亡人数。 **输入格式：** 第一行是一个整数 $T$，表示测试用例的数量。 接下来是 $T$ 个测试用例： 每个测试用例的第一行包括两个整数 $N$ 和 $M$： - $N$：未婚人数。 - $M$：已经确定婚姻的对数。 然后是 $M$ 行，每行包含两个整数 $i$ 和 $j$，表示第 $i$ 个人将与第 $j$ 个人结婚。 接下来是 $N$ 行，每行表示一个未婚者的信仰：「Love」或「Arranged」（引号仅为说明用途）。 **输出格式：** 对每个测试用例，输出一个格式为「Number of Deaths: X」的字符串，其中 X 是最少的死亡人数。请参考示例输出以获得更详细的信息。 **数据范围与提示：** - $1 \le T \le 100$ - $1 \le N \le 140$ - $1 \le M \le 10000$ - $1 \le i, j \le N$ **示例输入：** ``` 1 3 2 1 2 2 3 Love Arranged Love ``` **示例输出：** ``` Number of Deaths: 1 ``` **本翻译由 AI 自动生成**

无

无