← 返回题目列表

Codeforces · 65/E

E. 哈利·波特和移动楼梯

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

哈利·波特在逃离学校管理员费尔奇的追击时丢失了他的隐形衣。寻找看不见的物体并不是一件容易的事。幸运的是,哈利有愿意提供帮助的朋友。赫敏·格兰杰读过《隐形斗篷及其相关的一切》,以及六卷本《图、网络流、最大递增子序列和其他神奇物体快速搜索最短路径百科全书》。她已经开发了一种在复杂动态系统中搜索隐形斗篷的算法(霍格沃茨就是其中之一)。

霍格沃茨由 n 层楼组成,以 1 到 n 的整数编号。一些楼层通过楼梯连接。楼梯可能会改变其位置,仅移动一端。形式上的情况是这样的:如果楼梯连接a层和b层,那么在一次移动中它可能会改变其位置以连接a层和c层或b层和c层,其中c是与a层和b层不同的任何楼层。在任何情况下,楼梯都不能将楼层与其自身连接起来。同时,两层楼之间可以有多个楼梯。

最初,哈利位于数字 1 的楼层。他不记得自己在哪一层丢失了斗篷,并想在每个楼层寻找它。因此,他的目标是n层楼每层至少访问一次。哈利可以按任意顺序访问楼层并在任意楼层完成搜索。

如今楼梯很少移动。然而,罗恩和赫敏愿意对他们中的任何一个人施咒,以帮助哈利找到斗篷。为了减少怀疑,三个朋友计划将楼梯一层一层地移动,并且每个楼梯不超过一次。在移动楼梯之间,哈利将能够在地板上移动,此时可以从楼梯到达,并寻找他的隐形斗篷。假设在这段时间内楼梯不会自发移动。

帮助三个朋友制定一个搜索计划。如果有多种变体可以解决问题,则任何有效的选项(不一定是最佳的选项)都将被接受。

输入

第一行包含整数 n 和 m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000),分别是霍格沃茨的楼层数和楼梯数。接下来的 m 行包含在初始时刻通过楼梯连接的楼层对。

输出

如果 Harry 能够搜索所有楼层,则在第一行打印“YES”(不带引号),否则打印“NO”。如果答案是肯定的,则在第二行打印罗恩和赫敏必须移动的楼梯数。进一步的输出应如下所示:

哈利的举动

楼梯的移动

哈利的举动

楼梯的移动

...

楼梯的移动

哈利的举动

每个“哈利的举动”都应表示为按访问顺序排列的楼层列表。这些列表的元素总数不得超过 106。打印每个列表时,首先打印其中的元素数量,然后在同一行中打印实际的空格分隔元素。第一个列表中的第一个数字应该是数字 1(哈利开始搜索的楼层)。除第一个列表之外的任何列表都可能包含零个元素。请注意,哈利可以再次访问某些楼层,但必须至少访问所有 n 层一次。连续访问的两个楼层必须通过楼梯直接连接(当哈利从其中一层走到另一层时)。连续访问的两层楼不可能是相等的。

在“楼梯移动”的描述中,指示楼梯的数量(楼梯按照输入数据中给出的顺序从 1 到 m 编号)及其新位置(按任意顺序连接的两个楼层的编号)。

任何楼梯最多只能移动一次。如果有多个解,则输出任意一个。

示例

输入 #1

6 4
1 2
1 3
2 3
4 5

输出 #1

YES
2
3 1 2 3
2 3 5
3 5 4 5
4 5 6
3 6 5 3

输入 #2

4 1
1 2

输出 #2

NO

输入 #3

5 5
1 2
1 3
3 4
3 5
4 5

输出 #3

YES
0
6 1 2 1 3 4 5