#4841. [Neerc2016]Cactus Construction

题目描述

首先定义一种建图的方式，先选出一个常数C表示颜色的种类数，然后要建出一个含n个点的仙人掌，一开始图中一

共n连通块，n个点，没有边，每个点初始颜色均为1，你有如下3种操作可以使用：

1、join a b：将a所在的连通块和b所在的连通块划分为同一个连通块，不在a和b之间连边，必须保证a和b不能在同一个连通块。

2、recolor a c1 c2：将a所在的连通块中所有颜色为c1的点的颜色都改成c2。

3、connect a c1 c2：将a所在的连通块中颜色为c1的点和颜色为c2的点之间互相连边，如果c1=c2，则重边不连，

如果两个要连边的点已经连了一条边，则该次操作仍会在这两个点之间连边（当然重边是不允许出现在仙人掌中的

，所以你必须设法避免这种情况）。

给出最后构成的仙人掌，请你在保证C最小（保证C最大不会超过4）的情况下，输出构造方案。

输入格式

第一行两个数n（n<=50000,m<=50000)，表示最后构成的仙人掌有n个点，m条路径。

接下来m行，每行第一个数x(x<=1000),紧接着x个数，表示一条路径。

输出格式

第一行输出一个数q，表示操作次数。

接下来q行每行第一个输出一个字母：j或r或c，分别表示以上三种操作的第1、2、3种

若第一个字母为j，则接下来两个数a,b，含义如上所示

若第一个字母为r或c，则接下来三个数a,c1,c2，含义如上所述。

样例

样例输入

8 2  

5 1 2 3 4 7  

5 4 5 6 1 8

样例输出

17  

r 2 1 2  

j 2 3  

c 2 1 2  

r 6 1 2  

j 5 6  

c 6 1 2  

r 4 1 3  

j 4 3  

j 4 6  

j 4 7  

c 4 3 1  

r 4 3 1  

r 8 1 2  

r 1 1 3  

j 1 8  

j 1 4  

c 1 3 2

数据范围与提示

请不要提交！