Constructing a Cactus Graph via Clique‐Width Operations

Given an undirected cactus graph, you are to construct it step‐by‐step using a set of graph operations under the constraint that at most \(4\) colors are used. A cactus is a connected graph in which every edge lies on at most one simple cycle. No multi-edges or loops are allowed.

Construction model:

We start with a workspace containing \(n\) graphs. Each graph has one vertex (numbered from 1 to \(n\)) and is initially colored with color \(1\). The following operations are allowed:

• join a b: If vertices a and b are in different graphs, join (merge) the graphs containing them. No edge is added in this step.
• recolor a c1 c2: In the graph containing vertex a, change the color of every vertex having color \(c_1\) to color \(c_2\).
• connect a c1 c2: In the graph containing vertex a, add an edge between every pair of vertices where one is colored \(c_1\) and the other is colored \(c_2\). If \(c_1=c_2\), then no loop is added. The operation is only allowed if it does not create a scenario where an edge would be added between vertices that are already connected (since no multi‐edges are allowed).

The final goal is to have all vertices merged into a single graph with exactly the edges of the given cactus. Note that the final color assignments do not matter. It is known that the clique width of any cactus graph does not exceed \(4\).

Input: The first line contains two integers \(n\) and \(m\), denoting the number of vertices and edges, respectively. Each of the next \(m\) lines contains two integers \(u\) and \(v\) (1-indexed) indicating an edge between vertices \(u\) and \(v\).

Output: Output a sequence of operations (each on a separate line) that builds the given cactus graph using the allowed operations and at most 4 colors. The first line of output should be the number of operations. It is guaranteed that under the given restrictions a valid construction exists.

Note: For the purpose of this problem, you may assume that the input graphs in the test cases are one of the following:

• A graph with a single vertex.
• A graph with 2 vertices and 1 edge.
• A triangle (3 vertices, 3 edges).

You need to produce a valid construction series for these cases.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (1 \(\le\) n \(\le\) ...). Each of the following \(m\) lines contains two integers \(u\) and \(v\) (1-indexed) representing an edge in the cactus graph. For the test cases provided, the graphs will be one of the following:

• Case 1: A single vertex and no edge.
• Case 2: Two vertices with one edge.
• Case 3: Three vertices forming a triangle.

outputFormat

Output the number of operations \(k\) on the first line. Then output \(k\) lines, each describing one operation. The operations must be one of the following forms:

• recolor a c1 c2
• join a b
• connect a c1 c2

The resulting sequence of operations must combine the initial \(n\) graphs into one graph that exactly equals the given cactus.

sample

1 0

0

</p>