Non-Cyclic Group Formation

A messaging service company is looking to implement a new feature that organizes users into chat groups based on shared interests. Given n users and m interest pairs, where each interest pair indicates that two users share a common interest, your task is to form groups under the following conditions:

• Each user must belong to exactly one group.
• Within each group, the connections (based on shared interests) form an acyclic graph (i.e., a tree structure). In other words, if there exists any cycle among users in a proposed group, the grouping is considered invalid.

If any cycle is detected in any connected component, the entire grouping should be considered invalid, and the output must be 0. Otherwise, output the total number of groups followed by each group’s members (sorted in increasing order within each group).

Note: Two users sharing an interest is represented by an edge in an undirected graph. A cycle exists if there is an alternative connection (other than the parent-child connection) between two nodes. Mathematically, if we denote the graph as \(G=(V,E)\), then each connected component must be a tree, satisfying \( |E| = |V| - 1 \).

inputFormat

The input is given via stdin in the following format:

 n m
 u1 v1
 u2 v2
 ...
 um vm

Here, the first line contains two integers, \(n\) (the number of users) and \(m\) (the number of interest pairs). Each of the next \(m\) lines contains two integers \(u\) and \(v\) indicating that user \(u\) and user \(v\) have a common interest.

outputFormat

The output should be written to stdout. If a cycle is detected in any connected component of the graph, output a single line containing 0. Otherwise, output the number of groups on the first line, followed by one line per group containing the user IDs (separated by spaces) sorted in increasing order.

For example, if there are 2 groups, the output should be:

2
1 2 3
4 5 6

## sample

6 4
1 2
2 3
4 5
5 6

2
1 2 3
4 5 6

</p>