题目描述

有一个有 $N$ 个点的完全图，边权为 $1$，边是红色或蓝色。

对于每一个点，您需要构造从该点出发，经过每一个点至少一次且边权和最小的路径。

为了增大难度，我们要求您从一条边走到另一条异色的边需花费一张票，并且您只有一张票。

输入格式

第一行为一个整数 $N$。

接下来 $N$ 行，一行一个字符串，第 $i$ 行的字符串为 $C_i=C_{i,1},C_{i,2}\ldots C_{i,i-1}$，如果 $C_{i,j}$ 为 R，说明从 $i$ 到 $j$ 的边为红色的，反之，则为蓝色。

输出格式

输出共 $2\times N$ 行。

对于 $2\times i-1(1\le i\le N)$ 行，您需要输出一个整数 $M_i$，表示您所构造的从 $i$ 出发的遍历每一个点的方案的长度。

对于 $2\times i (1\le i\le N)$ 行，您需要输出 $M_i$ 个整数，表示您的方案所遍历点的顺序。

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

提示

样例解释

聪明的你一定发现了这个样例输出不是最优的。

从 $3$ 出发的话，有最优方案为 $3\to 1\to 2\to 4$，长度为 $4$，所以这个方案得 $\lfloor 8+8\times \frac{2\times 4-5}{4-1}\rfloor=16$ 分。

SPJ 计分策略

本题的每个测试点按您设计的路线计分。

对于您设计的第 $i$ 个方案，设其长度为 $M_i$，标准答案的第 $i$ 个方案长度为 $K_i$。

如果 $M_i>2\times K_i$ 或者您的方案错误，您会得 $0$ 分。

如果 $M_i=K_i$ 且您的方案合法，您会得 $25$ 分。

否则，如果您的方案合法，您会得 $\lfloor 8+8\times \frac{2\times K_i-M_i}{K_i-1}\rfloor$ 分。

这个测试点的分数为每个方案的得分的最小值。

您的提交得分为每个测试点得分的最小值。

译者提醒：为了方便 SPJ 的编写和测试点的计分，每个测试点 $100$ 分，题目的计分策略里的所有分数会按比例计算。

数据范围及限制

对于 $100\%$ 的数据，保证 $1\le N\le 2\times 10^3$，$C_{i,j}$ 为 R 或 B。

说明

本题译自 Canadian Computing Olympiad 2020 Day 2 T1 Travelling Salesperson。

本题数据有删减。

感谢

SPJ。