← 返回题目列表

Codeforces · 1656/I

I. 邻居订购

中文机器翻译题面 查看原题

给定一个无向图 $$$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