{"problem":{"name":"「Wdoi-6」最澄澈的空与海","description":{"content":"### 简要题意 给定 $2n$ 个点、$m$ 条边的[二分图](http://oi-wiki.com/graph/bi-graph/#_1)（可能有重边），左部点与右部点个数相同，判断其完美匹配数量是否**恰好**为 $1$。是则输出 `Renko`，否则输出 `Merry`。 > **注**：完美匹配是指，从边集中选出 $n$ 条边，这些边的顶点组成的点集恰好覆盖了所有的 $2n$ 个点。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8346"},"statements":[{"statement_type":"Markdown","content":"### 简要题意\n\n给定 $2n$ 个点、$m$ 条边的[二分图](http://oi-wiki.com/graph/bi-graph/#_1)（可能有重边），左部点与右部点个数相同，判断其完美匹配数量是否**恰好**为 $1$。是则输出 `Renko`，否则输出 `Merry`。\n\n> **注**：完美匹配是指，从边集中选出 $n$ 条边，这些边的顶点组成的点集恰好覆盖了所有的 $2n$ 个点。\n\n---\n### 原始题意\n\n在夜里，莲子与梅莉来到了东京的海边，躺在沙滩上，欣赏着澄澈的天空与大海，数起了天上的星星。\n\n在这些星星之中，有 $n$ 个星星 $\\{a_i\\}$，是莲子先发现的，被称为莲子星；而又有 $n$ 个星星 $\\{b_i\\}$，是梅莉先发现的，被称为梅莉星。由于她们心有灵犀，这两批星星之间**不存在交集**。  \n\n她们发现，有一些莲子星，与一些梅莉星之间恰好存在运动关系。具体而言，这些关系一共有 $m$ 组，每一组关系形如 $(u_i,v_i)$，也就是说第 $u_i$ 颗莲子星与第 $v_i$ 颗梅莉星之间存在运动关系。这些运动关系有可能重复。\n\n这让莲子和梅莉非常好奇。作为专攻超统一物理学的女大学生，莲子认为，如果认为这些星星的运动是**和谐**的，那么她应当能够从这 $m$ 个运动关系中，找出若干个运动关系，使得**每颗**星星**都被**这些运动关系**包含**的同时，不会有一颗星星**被包含在两个**运动关系之中。\n\n然而，梅莉认为，**和谐**的运动可能是不存在的，更何况即使莲子找到了**和谐**的运动，莲子也无法确保这种和谐运动的**唯一性**。两种和谐运动不同，当且仅当选取出的两组运动关系中，存在至少一个运动关系，是不相同的。\n\n因为意见不合，她们于是打情骂俏了一顿。莲子于是记下了她们所看到了星星和她们之间的运动关系，并且找到了已经证明了 P=NP 的你，希望你能告诉她们，最后是谁正确呢？\n\n## Input\n\n第一行输入一个正整数 $T$ 表示数据组数，对于每一组数据：\n\n- 第一行一个整数 $n$，代表莲子和梅莉每个人所先发现的星星的数量。\n- 第二行一个整数 $m$，代表运动关系的数量。\n- 接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示第 $u_i$ 颗莲子星，与第 $v_i$ 颗梅莉星之间，存在运动关系。\n\n## Output\n\n- 如果这些星星中存在唯一的和谐运动，输出 `Renko`。\n- 如果这些星星中不存在和谐运动，或者有不唯一的和谐运动方式，输出 `Merry`。\n\n[samples]\n\n## Background\n\n[![](https://cdn.luogu.com.cn/upload/image_hosting/hiekh6t5.png)](https://thwiki.cc/%E5%8D%AF%E9%85%89%E4%B8%9C%E6%B5%B7%E9%81%93_%EF%BD%9E_Retrospective_53_minutes.)\n\n广重号载着二人向东飞驰。毫无噪音，毫无摇摆，只是一个劲向东飞驰。在“万景幕”装置之下，尽管是全地下的卯酉东海道，乘客们也能饱览美丽的富士山和太平洋的景色。\n\n但是，从这列卯酉新干线『广重』上看到的极富日本风味的美丽情景，对于梅莉来说，只不过是无趣的视觉刺激罢了。高动态范围的影像也好，极富日本风味的情景也好，都敌不过真正的天空的颜色。\n\n身与华落，心将香飞。即便肉体会像花朵一样终有一天凋落，但心却可以如花香一般飘往远方。\n\n「梅莉，你看，天上的星星呦。」\n\n## Note\n\n### 样例解释\n\n#### 样例 \\#1\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/6skoily9.png)\n\n如图所示，存在唯一的方案：$\\{1\\to 1,2\\to 5,3\\to 2,4\\to 3,5\\to 4\\}$。\n\n### 数据范围\n\n**本题采用捆绑测试。**\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|c|c|c|}\\hline\n\\textbf{Subtask} & \\textbf{\\textsf{分值}} & \\bm{n\\le } & \\bm{m\\le} & \\textbf{\\textsf{特殊性质}} & \\textbf{Subtask \\textsf{依赖}}\\cr\\hline\n1 & 10 & 10 & 10 & - & - \\cr\\hline\n2 & 20 & 300 & 4\\times 10^4 & - & 1\\cr\\hline\n3 & 20 & 10^5 & 5 \\times 10^5 & \\mathbf{A} & - \\cr\\hline\n4 & 20 & 10^5 & 2 \\times 10^5 & \\mathbf{B} & - \\cr\\hline\n5 & 30& 10^6 & 2\\times 10^6 & - & 2,3,4 \\cr\\hline\n\\end{array}\n$$\n\n- 特殊性质 $\\mathbf{A}$：保证对于第 $i$ 颗莲子星，与第 $i$ 颗梅莉星之间存在运动关系。\n- 特殊性质 $\\mathbf{B}$：保证 $m=2n-1$。\n\n对于 $100\\%$ 的数据，保证 $1 \\le u_i,v_i\\le n \\le 10^6$，$1 \\le m \\le 2 \\times 10^6$，$1 \\leq T \\leq 5$ 且对于每个测试点，$\\sum m \\leq 4 \\times 10^6$。\n\n对于 $\\rm Subtask\\ 5$，时间限制为 $3$ 秒。其它测试点时间限制为 $1$ 秒。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8346","tags":["搜索","图论","洛谷原创","O2优化","二分图","洛谷月赛"],"sample_group":[["1\n5\n6\n1 1\n1 3\n3 2\n2 5\n4 3\n5 4","Renko"]],"created_at":"2026-03-03 11:09:25"}}