Background

The Hiroshige sped eastward with the two of them aboard. No noise, no shaking, just rushing eastward. Under the “Bankei-maku” device, even on the fully underground Boyo Tokaido, passengers could still enjoy the beautiful views of Mount Fuji and the Pacific Ocean.

However, the beautiful, very Japanese scenery seen from this Boyo Shinkansen “Hiroshige” was, to Merry, nothing more than boring visual stimulation. High dynamic range images or very Japanese scenery could not compare to the color of the real sky.

Body may fall like flowers, but the heart can drift far away like fragrance. Even if the body will one day wither like a flower, the heart can float to the distance like the scent of flowers.

"Merry, look, the stars in the sky."

Problem Description

Brief Statement

Given a bipartite graph with $2n$ vertices and $m$ edges (multiple edges may exist), where the left part and the right part have the same number of vertices, determine whether the number of its perfect matchings is exactly $1$. If yes, output Renko; otherwise, output Merry.

Note: A perfect matching means selecting $n$ edges from the edge set such that the set of vertices incident to these edges covers exactly all $2n$ vertices.

---

Original Statement

At night, Renko and Merry came to the seaside in Tokyo. Lying on the beach, they admired the clear sky and sea, and counted the stars in the sky.

Among these stars, there are $n$ stars $\{a_i\}$ that Renko found first, called Renko Stars; and there are also $n$ stars $\{b_i\}$ that Merry found first, called Merry Stars. Since they were in sync, there is no intersection between these two sets of stars.

They discovered that some Renko Stars and some Merry Stars have exactly a motion relationship between them. Specifically, there are $m$ such relationships, each in the form $(u_i, v_i)$, meaning that the $u_i$-th Renko Star and the $v_i$-th Merry Star have a motion relationship. These motion relationships may repeat.

This made Renko and Merry very curious. As a college girl majoring in super unified physics, Renko believed that if the motion of these stars is harmonious, then she should be able to pick some relationships from the $m$ motion relationships such that, while every star is included in these motion relationships, no star is included in two motion relationships at the same time.

However, Merry believed that harmonious motion might not exist. Moreover, even if Renko found such harmonious motion, she could not ensure the uniqueness of this harmonious motion. Two harmonious motions are different if and only if among the two selected sets of motion relationships, there exists at least one motion relationship that is not the same.

Because they could not agree, they flirt-argued for a while. Renko wrote down the stars they saw and the motion relationships between them, and found you, who has already proved $P=NP$, hoping you can tell them who was correct in the end.

Input Format

The first line contains a positive integer $T$, the number of test cases. For each test case:

• The first line contains an integer $n$, the number of stars each of Renko and Merry found first.
• The second line contains an integer $m$, the number of motion relationships.
• The next $m$ lines each contain two integers $u_i, v_i$, meaning that there exists a motion relationship between the $u_i$-th Renko Star and the $v_i$-th Merry Star.

Output Format

• If there exists a unique harmonious motion among these stars, output Renko.
• If there is no harmonious motion, or the harmonious motion is not unique, output Merry.

1
5
6
1 1
1 3
3 2
2 5
4 3
5 4

Renko

Hint

Sample Explanation

Sample #1

As shown in the figure, there is a unique solution: $\{1\to 1,2\to 5,3\to 2,4\to 3,5\to 4\}$.

Constraints

This problem uses bundled testdata.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n\le } & \bm{m\le} & \textbf{\textsf{特殊性质}} & \textbf{Subtask \textsf{依赖}}\cr\hline 1 & 10 & 10 & 10 & - & - \cr\hline 2 & 20 & 300 & 4\times 10^4 & - & 1\cr\hline 3 & 20 & 10^5 & 5 \times 10^5 & \mathbf{A} & - \cr\hline 4 & 20 & 10^5 & 2 \times 10^5 & \mathbf{B} & - \cr\hline 5 & 30& 10^6 & 2\times 10^6 & - & 2,3,4 \cr\hline \end{array}$$

• Special property $\mathbf{A}$: It is guaranteed that there exists a motion relationship between the $i$-th Renko Star and the $i$-th Merry Star.
• Special property $\mathbf{B}$: It is guaranteed that $m = 2n - 1$.

For $100\%$ of the data, it is guaranteed that $1 \le u_i, v_i \le n \le 10^6$, $1 \le m \le 2 \times 10^6$, $1 \leq T \leq 5$, and for each test point, $\sum m \leq 4 \times 10^6$.

For $\rm Subtask\ 5$, the time limit is $3$ seconds. For the other test points, the time limit is $1$ second.

Translated by ChatGPT 5