题目描述

有 $n$ 个集合，初始第 $i$ 个集合只包含第 $i$ 个点，每个点的初始颜色都为 $1$。要求使用下列 $3$ 种操作构建出给定的仙人掌。输出方案，操作数不得多于 $10^6$。

• $j\ a\ b$，将 $a$ 所在的集合和 $b$ 所在的集合合并成一个集合。

• $r\ a\ c_1\ c_2$（$c_1,c_2\in[1,2,3,4]$），将 $a$ 所在的集合中，所有颜色为 $c_1$ 的点的颜色改为 $c_2$。

• $c\ a\ c_1\ c_2$，将 $a$ 所在的集合中，每一个颜色为 $c_1$ 的点连向每一个颜色为 $c_2$ 的点，不允许出现重边。

输入第一行为点数 $n$ 和 $m$ 条边不重复的路径，每条边恰好会出现一次。接下来每行第一个数字 $k_i$ 代表路径的点数，后面 $k_i$ 个数字表示一条路径。

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

15 3
9 1 2 3 4 5 6 7 8 3
7 2 9 10 11 12 13 10
5 2 14 9 15 10

39
r 7 1 2
r 5 1 2
j 7 8
c 7 1 2
j 5 4
c 5 1 2
r 6 1 3
j 6 7
j 6 5
c 6 3 2
r 3 1 4
j 6 3
c 6 4 1
r 11 1 2
r 13 1 2
j 12 11
j 12 13
c 11 1 2
r 10 1 3
j 12 10
c 10 2 3
r 10 1 2
r 10 4 2
r 15 1 3
j 15 10
c 15 3 3
j 9 10
c 9 1 3
r 9 3 2
r 9 1 4
r 14 1 4
j 9 14
c 9 4 4
r 1 1 4
r 3 1 2
j 2 1
j 2 14
j 2 3
c 2 1 4

提示

对于 $100 \%$ 的数据，有 $1 \le n,m \le 5 \times 10^4$，$2 \le k_i \le 10^3$。