
ZOJ Problem Set  3984
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:
Given the final generated graph, DreamGrid would like to know all the \(p_q\) and \(S_q\). InputThere 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(n1)}{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\). OutputFor 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 Input3 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 OutputYes 1 0 2 0 3 0 Yes 1 0 4 0 3 1 4 2 2 1 3 No Author: LIN, Xi Source: The 2017 China Collegiate Programming Contest, Qinhuangdao Site 