时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
Special Judge, 64bit IO Format: %lld
题目描述
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, ..., n} . After that, the generator will do the following operations n times and during the q-th operation:
- 1.Find the all connected components C1, C2, ..., Cm in G.
-
2.Choose a subset Sq of
such that no two vertices in Sq belong to the same connected component.
-
3.Create a new vertex with index pq in G and add an edge between pq and every vertex v in
, where beli is the index of connected component which i belongs to.
Given the final generated graph, DreamGrid would like to know all the pq and Sq.
输入描述:
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 ≤ n ≤ 105, 0 ≤ m ≤ min(105,
) -- the number of vertices and the number of edges.
Each of the next m lines contains two integers ui and vi (1 ≤ ui, vi ≤ 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 *106.
输出描述:
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 pi and si (1 ≤ pi ≤ n) followed with si integers: a1, a2, ..., asi (1 ≤ aj ≤ 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.