Cycle Cover Decomposition in Undirected Graphs

Given an undirected graph with N vertices and M edges, your task is to decompose the graph into a collection of cycles (closed trails with no repeated edges) such that:

• The cycles are edge-disjoint (i.e. no edge appears in more than one cycle).
• The union of all cycles covers every edge and every vertex in the graph.

If such a decomposition exists, output the cycles. Otherwise, output -1.

Note: A cycle in this problem is defined as a closed trail that uses each edge at most once. It is well known that an undirected graph admits an edge decomposition into cycles if and only if every vertex with incident edges has an even degree. For this problem, if any vertex has degree 0 or an odd degree, then a valid cycle cover does not exist.

The graph’s vertices are numbered from 1 to N and each edge is specified by two integers (u and v) indicating an undirected edge between u and v.

inputFormat

The first line contains two integers N and M — the number of vertices and edges respectively. The next M lines each contain two integers u and v, indicating an undirected edge between vertices u and v.

outputFormat

If a cycle cover decomposition exists, first output a single integer K denoting the number of cycles. Then for each cycle, output two lines: the first line contains an integer L – the number of vertices in the cycle (note that the starting vertex appears again at the end to show closure), and the second line contains L space‐separated integers denoting the vertices in the order they appear in the cycle.

If no valid decomposition exists, output a single line containing -1.

sample

3 3
1 2
2 3
3 1

1
4
1 2 3 1