Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3984
Graph Generator

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

DreamGrid has made a graph generator. The generator will take in a single integer \(n\) and generate an undirected graph with \(n\) vertices.

More specifically, the generator will generate an empty graph \(G\) and a permutation \(p\) of \(\{1, 2, \dots, n\}\) . After that, the generator will do the following operations \(n\) times and during the \(q\)-th operation:

  1. Find the all connected components \(C_1, C_2, \dots, C_m\) in \(G\).
  2. Choose a subset \(S_q\) of \(\bigcup\limits_{i = 1}^{m} C_i\) such that no two vertices in \(S_q\) belong to the same connected component.
  3. Create a new vertex with index \(p_q\) in \(G\) and add an edge between \(p_q\) and every vertex \(v\) in \(\bigcup\limits_{i \in S_q} C_{bel_i}\), where \(bel_i\) is the index of connected component which \(i\) belongs to.

Given the final generated graph, DreamGrid would like to know all the \(p_q\) and \(S_q\).


There are multiple test cases. The first line of input contains an integer \(T\), indicating the number of test cases. For each test case:

The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 10^5, 0 \le m \le \min(10^5, \frac{n(n-1)}{2})\)) -- the number of vertices and the number of edges.

Each of the next \(m\) lines contains two integers \(u_i\) and \(v_i\) (\(1 \le u_i, v_i \le n\)). There will be no self loops or multiple edges.

It is guaranteed that neither the sum of all \(n\) nor the sum of all \(m\) exceeds \(2 \times 10^6\).


For each test case, if the the graph cannot be generated by the generator, output "No" in the first line. Otherwise, output "Yes" in the first line. Then in the \(i\)-th of the following line, output two integers \(p_i\) and \(s_i\) (\(1 \le p_i \le n\)) followed with \(s_i\) integers: \(a_1, a_2, \dots, a_{s_i}\) (\(1 \le a_j \le n\)) -- the index of the newly created vertex and the subset during the \(i\)-th operation. If there are multiple solutions, print any of them.

Sample Input

3 0
4 4
1 2
2 3
3 4
2 4
5 5
1 2
2 3
3 4
4 5
2 4

Sample Output

1 0
2 0
3 0
1 0
4 0
3 1 4
2 2 1 3

Author: LIN, Xi
Source: The 2017 China Collegiate Programming Contest, Qinhuangdao Site
Submit    Status