BZPRO

#4841. [Neerc2016]Cactus Construction

内存限制：128 MiB 时间限制：100 Sec
提交 提交记录 讨论

题目描述

首先定义一种建图的方式，先选出一个常数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

数据范围与提示

 请不要提交！

BZPRO Powered by Remmina.
Github Repository