#CW28. 唯一搭档(unique)

唯一搭档(unique)

题目描述

小 Z 正在安排一场双人合作活动。参加者分成左右两组,每组各有 nn 人,两组中的人都分别编号为 11 到 nn。

记录中有 mm 条可合作关系。第 ii 条记录为 (li,ri)(l_i,r_i),表示左组的 lil_i 号可以与右组的 rir_i 号合作。相同的关系可能被记录多次,但无论出现多少次,都只视为一种关系。

一份完整安排需要选出 nn 种关系,使左右两组的每个人都恰好出现在一种被选关系里。

如果完整安排恰好只有一种,输出 Renko;如果不存在完整安排,或存在至少两种不同的完整安排,输出 Merry。两份安排不同,当且仅当至少有一个人的搭档不同。

输入格式

第一行输入一个整数 TT,表示测试数据的组数。

对于每组数据:

  • 第一行输入一个整数 nn;
  • 第二行输入一个整数 mm;
  • 接下来 mm 行,第 ii 行输入两个整数 li,ril_i,r_i,表示一条可合作关系。

输出格式

对于每组数据,若完整安排恰好只有一种,输出一行 Renko;否则输出一行 Merry。

样例 1 输入

1
2
4
1 1
1 1
1 2
2 2

样例 1 输出

Renko

样例 1 解释

关系 (1,1)(1,1) 虽然被记录两次,但只算一种关系。唯一的完整安排是选择 (1,1)(1,1) 和 (2,2)(2,2)。

样例 2 输入

2
2
2
1 1
1 2
2
4
1 1
1 2
2 1
2 2

样例 2 输出

Merry
Merry

数据范围

对于所有测试数据,保证:

  • 1≤T≤51 \le T \le 5;
  • 1≤n≤1061 \le n \le 10^6;
  • 1≤m≤2×1061 \le m \le 2\times 10^6;
  • 1≤li,ri≤n1 \le l_i,r_i \le n;
  • 单个测试点中,所有测试数据的 mm 之和不超过 4×1064\times 10^6。
数据类别 分值 测试点 附加条件
A 10 1∼21\sim 2 每组数据均满足 n,m≤10n,m \le 10
B 15 3∼53\sim 5 每组数据均满足 n≤300n \le 300 且 m≤4×104m \le 4\times 10^4
C 20 6∼96\sim 9 每组数据均满足 n≤105n \le 10^5、m≤5×105m \le 5\times 10^5,且所有关系 (i,i)(i,i) 都至少被记录一次
D 25 10∼1410\sim 14 每组数据均满足 n≤105n \le 10^5 且 m=2n−1m=2n-1
E 30 15∼2015\sim 20 无额外限制