#CW28. 唯一搭档(unique)
唯一搭档(unique)
题目描述
小 Z 正在安排一场双人合作活动。参加者分成左右两组,每组各有 人,两组中的人都分别编号为 到 。
记录中有 条可合作关系。第 条记录为 ,表示左组的 号可以与右组的 号合作。相同的关系可能被记录多次,但无论出现多少次,都只视为一种关系。
一份完整安排需要选出 种关系,使左右两组的每个人都恰好出现在一种被选关系里。
如果完整安排恰好只有一种,输出 Renko;如果不存在完整安排,或存在至少两种不同的完整安排,输出 Merry。两份安排不同,当且仅当至少有一个人的搭档不同。
输入格式
第一行输入一个整数 ,表示测试数据的组数。
对于每组数据:
- 第一行输入一个整数 ;
- 第二行输入一个整数 ;
- 接下来 行,第 行输入两个整数 ,表示一条可合作关系。
输出格式
对于每组数据,若完整安排恰好只有一种,输出一行 Renko;否则输出一行 Merry。
样例 1 输入
1
2
4
1 1
1 1
1 2
2 2
样例 1 输出
Renko
样例 1 解释
关系 虽然被记录两次,但只算一种关系。唯一的完整安排是选择 和 。
样例 2 输入
2
2
2
1 1
1 2
2
4
1 1
1 2
2 1
2 2
样例 2 输出
Merry
Merry
数据范围
对于所有测试数据,保证:
- ;
- ;
- ;
- ;
- 单个测试点中,所有测试数据的 之和不超过 。
| 数据类别 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| A | 10 | 每组数据均满足 | |
| B | 15 | 每组数据均满足 且 | |
| C | 20 | 每组数据均满足 、,且所有关系 都至少被记录一次 | |
| D | 25 | 每组数据均满足 且 | |
| E | 30 | 无额外限制 |