Description

The Rainbow Dragon Cave can be abstracted as a connected undirected graph with $n$ vertices and $m$ edges. The graph may contain self-loops and multiple edges.

Yukari will use her gap ability to teleport Ran and Chen to some vertex in the Rainbow Dragon Cave. The time spent using gaps here is ignored. In the output format, $S$ denotes the initially teleported vertex.

Next, Chen and Ran will move separately. In each unit of time, either Ran or Chen can move to a vertex that is directly connected to the vertex she is currently on, or Yukari uses her gap ability to swap the positions of Ran and Chen. Note that in this unit of time, only one person (Ran, Chen, or Yukari) can act, and this swap operation also takes time.

Now, Ran Yakumo asks you to construct a plan such that both Chen and Ran each pass through every vertex in the Rainbow Dragon Cave at least $1$ time, and finally both return to the initial vertex $S$ to end this tour. In the "Output Format", Ran describes the format of the plan. You only need to output the plan in the required format and tell Ran.

Input Format

The first line contains two integers $n,m$, indicating that the graph has $n$ vertices and $m$ edges.

In the next $m$ lines, each line contains two integers $u,v$, indicating an undirected edge connecting $u$ and $v$.

Output Format

Output two integers $S$ and $k$ on the first line. The meaning of $S$ is described in the problem statement, and $k$ is the number of operations in your plan.

In the next $k$ lines, you may output one of the following three operations to guide the Yakumo family:

• Output Ran u, meaning letting Ran move to vertex $u$.
• Output Chen u, meaning letting Chen move to vertex $u$.
• Output Swap, meaning letting Yukari swap the positions of Chen and Ran.

You need to guarantee that your constructed plan is valid.

It is easy to see that the number of operations $k$ equals the number of unit-time steps spent performing all operations.

3 3
1 2
2 3
1 3

1 5
Ran 2
Chen 3
Swap
Ran 1
Chen 1

Hint

Sample Explanation

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Number of operations} & \textbf{Ran's position} &\textbf{Chen's position} \cr\hline 0 & 1 & 1 \cr\hline 1 & 2 & 1 \cr\hline 2 & 2 & 3 \cr\hline 3 & 3 & 2 \cr\hline 4 & 1 & 2 \cr\hline 5 & 1 & 1 \cr\hline \end{array}$$

Scoring

This problem uses a Special Judge.

For each test case, if your output plan is invalid (including an invalid move, or Ran or Chen does not pass through every vertex at least $1$ time, or Ran and Chen are not at vertex $S$ at the end), your score will be zero. Otherwise, your score is calculated as follows:

• If $k \leq 4\cdot n$, you will get $20\%$ of the score for this test point.
• If $k \leq 3\cdot n$, you will get $40\%$ of the score for this test point.
• If $k \le \lfloor\frac{11}{4} \cdot n\rfloor$, you will get $70\%$ of the score for this test point.
• If $k \le \lfloor\frac{8}{3} \cdot n\rfloor$, you will get full score for this test point.

Constraints

This problem uses bundled testcases, and there is only one subtask. The final score is the minimum score among all test points.

For $100\%$ of the testdata, $3\leq n,m \leq 5\times 10^5$.

Checker

To make it easier for contestants to test, we provide a checker.cpp file in the attachments. You may compile this program and use it to check your output file. However, note that it is not exactly the same as the checker used in the final judging. You also do not need to care about the specific code content.

The compile command is: g++ checker.cpp −o checker -std=c++14.

Usage of the checker is: ./checker <inputfile> <outputfile>, where the parameters are the input file and your output file, respectively.

If the range of numbers you output is invalid, the checker will give corresponding prompts. If the range of numbers you output is correct but the plan is wrong, it will give brief error messages:

1. A x, meaning the plan becomes invalid at operation $x$.
2. B x, meaning after all operations finish, Ran/Chen has not visited every vertex at least once, where $x=0$ means Ran and $x=1$ means Chen.
3. C x, meaning after all operations finish, Ran/Chen has not returned to vertex $S$, where $x=0$ means Ran and $x=1$ means Chen.
4. Illeagl Output, meaning you output an incorrect operation.

If your plan is correct, the checker will output OK.

It is guaranteed that, given correct input and a valid plan, the checker runs in less than 1s.

Translated by ChatGPT 5