Find Clusters in a Social Network

You are given a social network with N people and M friendship connections. Each friendship connects two persons and is undirected. A person may also have a self-loop (friendship with themselves) or multiple edges. Your task is to determine the clusters (connected components) of friends.

For each test case, you will be provided with the number of persons and the list of connections. You have to output, for every test case, the number of clusters followed by the sorted list of members in each cluster. The clusters should be sorted in increasing order by their smallest member.

In mathematical terms, if the graph is represented as \(G(V,E)\) where \(V = \{1, 2, \dots, N\}\) and \(E\) are the undirected edges, then you need to find its connected components. Two persons \(u\) and \(v\) are in the same cluster if there exists a path between them.

Note: Self-loops do not extend connectivity and multiple edges between the same pair of nodes should be treated as a single connection.

inputFormat

The input begins with an integer T denoting the number of test cases. For each test case:

• The first line contains two integers N and M, where N is the number of people and M is the number of friendship connections.
• This is followed by M lines, each containing two integers u and v which indicate that person u and person v are connected.

Input is read from standard input (stdin).

outputFormat

For each test case, output the cluster information:

• On the first line, output an integer representing the number of clusters.
• Then, for each cluster, output a line with the members of that cluster in increasing order, separated by spaces.

The clusters themselves should be output in increasing order of their smallest member. Output should be written to standard output (stdout).

## sample

2
6 4
1 2
2 3
4 5
5 6
5 3
2 2
1 1
2 1

2
1 2 3
4 5 6
4
1 2
3
4
5

</p>