Cactus Construction

A cactus is a connected undirected graph in which every edge lies on at most one simple cycle. A cactus has no loops and no multiple edges. It is a tree that is allowed to contain some cycles.

Graphs can be assembled by the following process. Fix a number of colors $\hat{c}$. Every vertex carries one color, written as an integer from $1$ to $\hat{c}$. The workspace starts with $n$ separate graphs, one vertex in each. The $i$-th graph holds only vertex $i$, colored $1$, with no edges.

Three operations are permitted.

• join $a$ $b$: merge the graph containing vertex $a$ and the graph containing vertex $b$ into one graph. No edge is added. Vertices $a$ and $b$ must lie in different graphs.
• recolor $a$ $c_1$ $c_2$: inside the graph containing vertex $a$, change every vertex of color $c_1$ to color $c_2$.
• connect $a$ $c_1$ $c_2$: inside the graph containing vertex $a$, add an edge between every vertex of color $c_1$ and every vertex of color $c_2$. If $c_1 = c_2$, no loop is created. If such an edge already exists, a second parallel edge would appear. Multiple edges are not allowed in this problem, so that case must never occur.

Once the last operation is applied, the workspace holds a single graph, and the colors of its vertices no longer matter.

The smallest $\hat{c}$ that suffices to assemble a graph is called the clique width of that graph. On graphs of bounded clique width, many NP-hard problems can be solved in polynomial time by dynamic programming over this assembly process. Computing the exact clique width of a general graph is NP-hard, but bounds are known for some graph classes. The clique width of a cactus is at most $4$.

You are given a cactus. Assemble it with $\hat{c} = 4$ colors, following exactly the construction fixed in the output section.

The first line contains two integers $n$ and $m$ ($1 \le n \le 50000$; $0 \le m \le 50000$), the number of vertices and the number of paths. Vertices are numbered from $1$ to $n$. The edges of the graph are given as $m$ edge-distinct paths.

Each of the next $m$ lines describes one path. The line starts with an integer $k_i$ ($2 \le k_i \le 1000$), followed by $k_i$ vertex numbers between $1$ and $n$. Adjacent vertices on a line are different. A path may visit the same vertex several times, and every edge of the graph appears exactly once across the whole input.

The graph given this way is a cactus.

Many different operation sequences assemble the same cactus, so this problem fixes one of them.

Root the cactus at vertex $1$. Every edge of a cactus belongs to exactly one block, where a block is either a simple cycle or a bridge, that is, an edge that lies on no cycle. Two different blocks share at most one vertex. For a block $B$, let $\mathrm{top}(B)$ be the vertex of $B$ closest to vertex $1$; that vertex is unique. Block $B$ hangs from vertex $v$ when $\mathrm{top}(B) = v$.

Order the blocks hanging from $v$ by the smallest number among the vertices of the block other than $v$. Blocks hanging from the same vertex share nothing but $v$, so these minima are all different and the order is determined.

Let $B$ be a cycle block hanging from $v$ with $k$ vertices, so $k \ge 3$. Vertex $v$ has exactly two neighbors inside $B$. Let $w_1$ be the one with the smaller number, and walk around the cycle from $w_1$ in the direction away from $v$. That gives $w_1, w_2, \ldots, w_{k-1}$, where $w_{k-1}$ is the other neighbor of $v$.

Define the recursive procedure below. In the pseudocode, <x> is replaced by the number of vertex $x$, and every emitted string is one output line.

build(v):
    for each block B hanging from v, in the order defined above:
        if B is the bridge {v, u}:
            build(u)
            emit "r <u> 1 3"
            emit "j <v> <u>"
            emit "c <v> 1 3"
            emit "r <v> 3 2"
        else B is the cycle v, w[1], w[2], ..., w[k-1]:
            build(w[1])
            emit "r <w[1]> 1 3"
            build(w[2])
            emit "r <w[2]> 1 4"
            emit "j <w[1]> <w[2]>"
            emit "c <w[1]> 3 4"
            for i = 3, 4, ..., k-1:
                build(w[i])
                emit "j <w[1]> <w[i]>"
                emit "c <w[1]> 4 1"
                emit "r <w[1]> 4 2"
                emit "r <w[1]> 1 4"
            emit "j <v> <w[1]>"
            emit "c <v> 1 3"
            emit "c <v> 1 4"
            emit "r <v> 3 2"
            emit "r <v> 4 2"

Run build(1) and collect the emitted lines in order. Print their count $q$ on the first line, then the $q$ lines in that order. For $n = 1$ nothing is emitted, so print a single line holding $0$.

This sequence always assembles the input cactus correctly, it uses only the colors $1$ to $4$, and $q$ never exceeds $10^6$.

When build(v) returns, vertex $v$ has color $1$ and every other vertex of the graph containing it has color $2$. Colors $3$ and $4$ are therefore free at every point where a block is wired up, which is why four colors are enough.