You are given an undirected graph A, which has n vertices and m edges.
There is another undirected graph B, which has n vertices and n * (n - 1) / 2 - m edges. For each pair of vertices u, v there is an edge between them if and only if they are not connected by an edge in graph A.
Find the number of connected components in graph B and the size of each component.
Input Format:
- The first line contains T, the number of test cases. The following lines contain the descriptions of the test cases.
- The first line of each test case contains two integers, n and m.
- Then m lines follow, each line containing two integers u and v (1 <= u, v <= n) denoting the edges present in graph A.
Output Format:
- On the first line print an integer K - denoting the count of connected components in the graph.
- In the next line, print K integers denoting the size of K connected components in the graph. The size of components should be printed in increasing order.
Constraints-
- 1<=T<=100
- 1<=n<=2∗105
- 0<=m<=min(n∗(n−1)/2,2∗105)
- sum of n and m overall testcases <=2∗105
In the first test case, in graph B there are 2 edges. First edge is between 1 and 2, and second edge is between 3 and 4. So, there are 2 connected components containing 2 vertices each.
In the second test case, there is only one edge in graph A between 1 and 2. So, vertices 1 and 2 donot have an edge in graph B. But 1 and 2 are connected to 3 in graph B. So, all 3 vertices are in same connected component.
