CF1656I.Neighbour Ordering

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 \lt _{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 \lt _{v_2} v_3, v_2 \lt _{v_3} v_4, \ldots, v_{c-2} \lt _{v_{c-1}} v_c, v_{c-1} \lt _{v_c} v_1, v_c \lt _{v_1} v_2$.
• $v_1 \gt _{v_2} v_3, v_2 \gt _{v_3} v_4, \ldots, v_{c-2} \gt _{v_{c-1}} v_c, v_{c-1} \gt _{v_c} v_1, v_c \gt _{v_1} v_2$.

Given a graph $G$, determine whether there exists a good neighbour ordering for it and construct one if it does.

给定一个无向图 $G$，我们称邻居排序（neighbour ordering）为：对图 $G$ 中的每个顶点，将其所有邻居按某种顺序排成的一个有序列表。考虑图 $G$ 的一个给定邻居排序，以及三个顶点 $u$、$v$ 和 $w$，其中 $v$ 同时是 $u$ 和 $w$ 的邻居。我们记 $u \lt _{v} w$，当且仅当在 $v$ 的邻居列表中，$u$ 出现在 $w$ 之后。

若对图 $G$ 的任意简单环 $v_1, v_2, \ldots, v_c$，以下两个条件之一成立，则称该邻居排序是好的（good）：

• $v_1 \lt _{v_2} v_3,\; v_2 \lt _{v_3} v_4,\; \ldots,\; v_{c-2} \lt _{v_{c-1}} v_c,\; v_{c-1} \lt _{v_c} v_1,\; v_c \lt _{v_1} v_2$；
• $v_1 \gt _{v_2} v_3,\; v_2 \gt _{v_3} v_4,\; \ldots,\; v_{c-2} \gt _{v_{c-1}} v_c,\; v_{c-1} \gt _{v_c} v_1,\; v_c \gt _{v_1} v_2$。

给定一个图 $G$，请判断是否存在一个好的邻居排序；若存在，请构造出一个。

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 \lt 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$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 3 \cdot 10^5$，$1 \leq m \leq 3 \cdot 10^5$），分别表示图的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$0 \leq u, v \lt n$），表示顶点 $u$ 与顶点 $v$ 之间存在一条边。保证该图是连通的，且不存在自环或两点间有多条重边。

所有测试用例的 $n$ 之和与 $m$ 之和均不超过 $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.

对于每个测试用例，如果存在一个“好邻居排序”，则输出一行 YES；否则输出一行 NO。你可以以任意大小写（大写或小写）输出每个字母。

如果答案为 YES，则还需额外输出 $n$ 行，描述一个“好邻居排序”。在第 $i$ 行中，按顺序输出顶点 $i$ 的所有邻居。

若存在多个“好邻居排序”，输出任意一个即可。