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