I. Neighbour Ordering
constructive algorithms; graphs
Given an undirected graph \(G\), we say that a neighbour ordering is an ordered list of all the neighbours of a vertex for each of the vertices of \(G\). Consider a given neighbour ordering of \(G\) and three vertices \(u\), \(v\) and \(w\), such that \(v\) is a neighbor of \(u\) and \(w\). We write \(u <_{v} w\) if \(u\) comes after \(w\) in \(v\)'s neighbor list.A neighbour ordering is said to be good if, for each simple cycle \(v_1, v_2, \ldots, v_c\) of the graph, one of the following is satisfied: \(v_1 <_{v_2} v_3, v_2 <_{v_3} v_4, \ldots, v_{c-2} <_{v_{c-1}} v_c, v_{c-1} <_{v_c} v_1, v_c <_{v_1} v_2\). \(v_1 >_{v_2} v_3, v_2 >_{v_3} v_4, \ldots, v_{c-2} >_{v_{c-1}} v_c, v_{c-1} >_{v_c} v_1, v_c >_{v_1} v_2\). Given a graph \(G\), determine whether there exists a good neighbour ordering for it and construct one if it does.
The input consists of multiple test cases. The first line contains a single integer \(t\) (\(1 \leq t \leq 10^4\)) — the number of test cases. Description of the test cases follows.The first line of each test case contains two integers \(n\) and \(m\) (\(2 \leq n \leq 3 \cdot 10^5\), \(1 \leq m \leq 3 \cdot 10^5\)), the number of vertices and the number of edges of the graph.The next \(m\) lines each contain two integers \(u, v\) (\(0 \leq u, v < n\)), denoting that there is an edge connecting vertices \(u\) and \(v\). It is guaranteed that the graph is connected and there are no loops or multiple edges between the same vertices.The sum of \(n\) and the sum of \(m\) for all test cases are at most \(3 \cdot 10^5\).
For each test case, output one line with YES if there is a good neighbour ordering, otherwise output one line with NO. You can print each letter in any case (upper or lower).If the answer is YES, additionally output \(n\) lines describing a good neighbour ordering. In the \(i\)-th line, output the neighbours of vertex \(i\) in order. If there are multiple good neigbour orderings, print any.