Description

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.

Input Format

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 Format

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.

4
R
RR
BRB

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

Hint

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 Day 2 T1 Travelling Salesperson.

Thanks to

Translated by ChatGPT 5