#BZOJ4841. Cactus Construction

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

数据范围与约定

 请不要提交!