给定一个无向图 $$$G$$$,我们说邻居排序是 $$$G$$$ 的每个顶点的顶点的所有邻居的有序列表。考虑 $$$G$$$ 的给定邻居排序和三个顶点 $$$u$$$、$$$v$$$ 和 $$$w$$$,使得 $$$v$$$ 是 $$$u$$$ 和 $$$w$$$ 的邻居。如果 $$$u$$$ 在 $$$v$$$ 的邻居列表中位于 $$$w$$$ 之后,我们就写 $$$u <_{v} w$$$。
如果对于图的每个简单循环 $$$v_1, v_2, \ldots, v_c$$$ 满足以下条件之一,则称邻居排序是好的:
- $$$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$$$。
给定一个图 $$$G$$$,确定它是否存在良好的邻居排序,如果存在,则构造一个。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$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 < n$$$),表示有一条边连接顶点 $$$u$$$ 和 $$$v$$$。保证图是连通的,并且相同顶点之间不存在环路或多条边。
所有测试用例的 $$$n$$$ 总和以及 $$$m$$$ 总和最多为 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,如果存在好邻居排序,则输出一行 YES,否则输出一行 NO。您可以以任何大小写(大写或小写)打印每个字母。
如果答案为“是”,则另外输出描述良好邻居排序的 $$$n$$$ 行。在第 $$$i$$$ 行中,按顺序输出顶点 $$$i$$$ 的邻居。
如果有多个好邻居订单,则打印任何一个。
示例
输入 #1
3 5 6 0 1 0 2 1 2 2 3 3 4 4 1 2 1 0 1 6 10 0 1 2 0 0 3 0 4 1 2 1 4 2 3 2 5 3 5 4 5
输出 #1
YES 1 2 4 2 0 0 1 3 2 4 3 1 YES 1 0 NO