P6644 [CCO 2020] Travelling Salesperson

有一个有 $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$ 个整数，表示您的方案所遍历点的顺序。

#### 样例解释  聪明的你一定发现了这个样例输出不是最优的。 从 $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](https://cemc.math.uwaterloo.ca/contests/computing/2020/) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2020/cco/day2.pdf) T1 Travelling Salesperson。 感谢 @[tiger2005](https://www.luogu.com.cn/user/60864) 提供的 SPJ。