P8119 "Wdoi-1.5" Gensokyo Tour Plan

(This is background; you may skip it.) Ever since Momoyo Himemushi started digging the Rainbow Dragon Cave at the top of Youkai Mountain, the unchanging Gensokyo has gained another place to explore. Yukari Yakumo, who is full of schemes and watches every movement in Gensokyo, naturally needs to know everything inside it, in order to maintain absolute control over Gensokyo. Ran Yakumo, Yukari's shikigami, is ordered to explore this area. Also traveling with them is Ran's shikigami, Chen. The purpose of mining the Rainbow Dragon Cave is to obtain the Dragon Jewels inside, which are scattered throughout the cave. To obtain more Dragon Jewels without missing anything, Momoyo dug out crisscrossing tunnels, connecting the collection points of the Dragon Jewels. The tunnels intersect with each other, forming a layered, dense network. Ran and Chen's task is to each visit every Dragon Jewel collection point in the Rainbow Dragon Cave, gathering enough information to fulfill Yukari's goal of thoroughly monitoring the cave. However, in the dark cave, the huge Rainbow Dragon Cave is very dangerous. The extremely oxygen-poor environment makes exploring it difficult, so Ran and Chen cannot stay inside for too long. Fortunately, Ran can contact Yukari; and Yukari, who can manipulate boundaries, can use gaps to swap the positions of Ran and Chen. Yukari has already colluded with Tsukasa Kudamaki and obtained the internal map of the Rainbow Dragon Cave from the Great Tengu. To minimize the time spent inside the cave, the Yakumo family needs to design a feasible plan.

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.

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 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.

### 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 `, 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