P6644 [CCO 2020] Travelling Salesperson

There is a complete graph with $N$ vertices. Every edge has weight $1$, and each edge is either red or blue. For each vertex, you need to construct a path that starts from that vertex, visits every vertex at least once, and has the minimum possible total edge weight. To make it harder, switching from one edge to another edge of a different color costs one ticket, and you only have one ticket.

The first line contains an integer $N$. The next $N$ lines each contain a string. The string on line $i$ is $C_i=C_{i,1},C_{i,2}\ldots C_{i,i-1}$. If $C_{i,j}$ is `R`, then the edge from $i$ to $j$ is red; otherwise, it is blue.

Output a total of $2\times N$ lines. On line $2\times i-1$ $(1\le i\le N)$, output an integer $M_i$, which is the length of the route you constructed that starts from $i$ and visits every vertex. On line $2\times i$ $(1\le i\le N)$, output $M_i$ integers, which describe the order of vertices visited by your route.

#### Sample Explanation  You should notice that the sample output is not optimal. If starting from $3$, an optimal route is $3\to 1\to 2\to 4$, with length $4$. Therefore, this route gets $\lfloor 8+8\times \frac{2\times 4-5}{4-1}\rfloor=16$ points. #### SPJ Scoring Strategy Each testdata case in this problem is scored based on the routes you design. For your $i$-th route, let its length be $M_i$, and let the length of the official solution’s $i$-th route be $K_i$. If $M_i>2\times K_i$ or your route is invalid, you will get $0$ points. If $M_i=K_i$ and your route is valid, you will get $25$ points. Otherwise, if your route is valid, you will get $\lfloor 8+8\times \frac{2\times K_i-M_i}{K_i-1}\rfloor$ points. The score of this testdata case is the minimum score among all routes. Your submission score is the minimum score among all testdata cases. **Translator’s note: To make SPJ implementation and per-testdata scoring easier, each testdata case is worth $100$ points, and all scores in the scoring strategy will be scaled proportionally.** #### Constraints and Limits For $100\%$ of the data, it is guaranteed that $1\le N\le 2\times 10^3$, and $C_{i,j}$ is `R` or `B`. #### Notes This problem is translated from [Canadian Computing Olympiad 2020](https://cemc.math.uwaterloo.ca/contests/computing/2020/) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day2.pdf) T1 Travelling Salesperson. Thanks to @[tiger2005](https://www.luogu.com.cn/user/60864) for providing the SPJ. Translated by ChatGPT 5