题目描述

译自 CCO $2020$ Day$2$ T$1$「Travelling Salesperson」，翻译者：EntropyIncreaser & jinhaoxian。

在红蓝城，每一对建筑之间都有一条无向边，每条边为红色或蓝色。定义路径的代价为边的颜色切换次数、路径长度为经过的建筑的个数（重复经过同一建筑需要重复计入）。如图，以下路径长度为 $5$，代价为 $1$：

如果第二次到达建筑 $3$ 之后再经由蓝边到达建筑 $2$，则代价会增加 $1$，即总代价为 $2$：

作为一个旅行商，你需要设计一条路径，满足该路径经过每个建筑至少一次（起点和终点视为经过），且该路径的代价不超过 $1$。在此前提下，你希望最小化重复经过的建筑数（即最小化路径长度）。对于每个建筑 $i$，以 $i$ 为起点设计一条满足上述条件的路径（终点可任选）。

输入格式

第一行输入一个正整数 $N$，表示建筑数量。

第 $2$ 至 $N$ 行每行一个字符串，其中第 $i$ 行的字符串 $C_i=C_{i,1}C_{i,2}\cdots C_{i,i-1}$ 表示连接建筑 $i$ 的边的颜色。对于字符 $C_{i,j}\,(1\le j<i)$，若该字符为 R，表示连接 $i$ 和 $j$ 的边为红边；若该字符为 B，表示连接 $i$ 和 $j$ 的边为蓝边。

输出格式

输出 $2N$ 行。

第 $2i-1$ 行（$1\le i\le N$）输出一个整数 $M_i$，表示你所构造的以 $i$ 为起点的路径长度。

第 $2i$ 行（$1\le i\le N$）输出 $M_i$ 个整数，相邻两个整数间用单个空格分隔，表示这条路径依次经过的节点。其中，第一个整数应为 $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$ 为起点的合法路径最小长度为 $4$（依次经过建筑 $3,2,1,4$），故在该路径上的得分是

$4\times \lfloor 8 + 8\times \frac{2\times 4 - 5}{4-1} \rfloor = 64$，即得分不会超过 $64$。

数据范围与提示

对于 $100 \%$ 的数据，$2 \le N \le 2000$, $C_{i,j}\in \{R,B\}$。

令 $K_i$ 是以 $i$ 为起点的最短合法路径的长度。如果存在一组 $M_i > 2K_i$，则在该测试点得 $0$ 分并被判为 Wrong Answer。

如果对于每个 $1\le i\le N$ 均满足 $K_i=M_i$，则在该测试点得 $100$ 分。否则，在该测试点的得分将是

$\min_{\substack{1\le i\le N}}\{4\times \lfloor 8 + 8\times \frac{2K_i - M_i}{K_i-1} \rfloor\}$。

特别地，若构造的某条路径不合法，则在该测试点得 $0$ 分并被判为 Wrong Answer。

选手在本题的得分为所有测试点得分的最小值。