CF65E.Harry Potter and Moving Staircases

Harry Potter lost his Invisibility Cloak, running from the school caretaker Filch. Finding an invisible object is not an easy task. Fortunately, Harry has friends who are willing to help. Hermione Granger had read "The Invisibility Cloaks, and Everything about Them", as well as six volumes of "The Encyclopedia of Quick Search of Shortest Paths in Graphs, Network Flows, the Maximal Increasing Subsequences and Other Magical Objects". She has already developed a search algorithm for the invisibility cloak in complex dynamic systems (Hogwarts is one of them).

Hogwarts consists of n floors, numbered by integers from 1 to n. Some pairs of floors are connected by staircases. The staircases may change its position, moving exactly one end. Formally the situation is like this: if a staircase connects the floors a and b, then in one move it may modify its position so as to connect the floors a and c or b and c, where c is any floor different from a and b. Under no circumstances the staircase can connect a floor with itself. At the same time there can be multiple stairs between a pair of floors.

Initially, Harry is on the floor with the number 1. He does not remember on what floor he has lost the cloak and wants to look for it on each of the floors. Therefore, his goal is to visit each of n floors at least once. Harry can visit the floors in any order and finish the searching at any floor.

Nowadays the staircases move quite rarely. However, Ron and Hermione are willing to put a spell on any of them to help Harry find the cloak. To cause less suspicion, the three friends plan to move the staircases one by one, and no more than once for each staircase. In between shifting the staircases Harry will be able to move about the floors, reachable at the moment from the staircases, and look for his Invisibility Cloak. It is assumed that during all this time the staircases will not move spontaneously.

Help the three friends to compose a searching plan. If there are several variants to solve the problem, any valid option (not necessarily the optimal one) will be accepted.

哈利·波特在躲避学校管理员费尔奇时弄丢了隐形斗篷。寻找一件隐形物品可不是件容易的事。幸运的是，哈利有愿意帮忙的朋友。赫敏·格兰杰不仅读过《隐形斗篷及其一切》，还研读了六卷本的《图中最快最短路径、网络流、最长递增子序列及其他魔法物体速查百科全书》。她已为复杂动态系统（霍格沃茨即属此类）开发出一种搜寻隐形斗篷的算法。

霍格沃茨共有 $n$ 层楼，编号为 $1$ 至 $n$ 的整数。某些楼层对之间由楼梯连接。这些楼梯的位置可能发生变化，每次移动恰好改变其一端。形式化地讲：若某楼梯连接楼层 $a$ 和 $b$，则一次操作可将其位置修改为连接楼层 $a$ 和 $c$，或 $b$ 和 $c$，其中 $c$ 为任意不同于 $a$ 和 $b$ 的楼层。楼梯绝不可连接某楼层与其自身。同时，任意一对楼层之间可能存在多条楼梯。

初始时，哈利位于编号为 $1$ 的楼层。他不记得自己把斗篷丢在哪一层，因此需逐一搜寻全部 $n$ 层楼。换言之，他的目标是至少访问每层楼一次。哈利可按任意顺序访问各楼层，并可在任意楼层结束搜寻。

如今，楼梯自行移动的频率已大大降低。然而，罗恩和赫敏愿对任意楼梯施法以协助哈利寻找斗篷。为减少怀疑，三人计划每次仅移动一条楼梯，且每条楼梯至多移动一次。在楼梯移动的间隙，哈利可在当时由楼梯所连通的楼层间自由移动，并搜寻他的隐形斗篷。整个过程中，楼梯不会自发移动。

请协助这三位朋友制定一份搜寻方案。若存在多种可行解，任一有效方案（未必最优）均可接受。

The first line contains integers n and m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000), which are the number of floors and staircases in Hogwarts, respectively. The following m lines contain pairs of floors connected by staircases at the initial moment of time.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 100000$，$0 \leq m \leq 200000$），分别表示霍格沃茨的楼层数和楼梯数。接下来的 $m$ 行每行包含一对由楼梯在初始时刻连接的楼层。

In the first line print "YES" (without the quotes) if Harry is able to search all the floors, and "NO" otherwise. If the answer is positive, then print on the second line the number of staircases that Ron and Hermione will have to shift. Further output should look like this:

Harry's moves

a staircase's move

Harry's moves

a staircase's move

...

a staircase's move

Harry's moves

Each "Harry's move" should be represented as a list of floors in the order in which they have been visited. The total amount of elements of these lists must not exceed 106. When you print each list, first print the number of elements in it, and then in the same line print the actual space-separated elements. The first number in the first list should be the number 1 (the floor, from which Harry begins to search). Any list except the first one might contain the zero number of elements. Note that Harry can visit some floors again, but must visit all n floors at least once. Two consecutively visited floors must be directly connected by a staircase (at the time Harry goes from one of them to the other one). No two floors that are visited consequtively can be equal.

In the description of a "staircase's move" indicate the number of staircase (the staircases are numbered from 1 to m in the order in which they are given in the input data) and its new location (two numbers of the connected floors in any order).

Any staircase can be moved at most once. If there are several solutions, output any.

第一行输出“YES”（不带引号），如果哈利能够搜索所有楼层；否则输出“NO”。若答案为肯定，则在第二行输出罗恩和赫敏需要移动的楼梯数量。后续输出格式如下：

哈利的移动

一段楼梯的移动

哈利的移动

一段楼梯的移动

...

一段楼梯的移动

哈利的移动

每段“哈利的移动”应表示为一个楼层列表，按其被访问的顺序排列。所有这些列表中元素的总数不得超过 $10^6$。打印每个列表时，首先在同一行中输出该列表的元素个数，然后在同一行中输出各元素（以空格分隔）。第一个列表中的第一个数字应为 $1$（即哈利开始搜索的楼层）。除第一个列表外，其余列表可以为空（即包含零个元素）。注意：哈利可以重复访问某些楼层，但必须至少访问全部 $n$ 个楼层一次；连续访问的两个楼层在哈利从其中一个前往另一个时，必须由一段楼梯直接连接；任意两个连续访问的楼层不能相同。

在每段“楼梯的移动”的描述中，需指明楼梯编号（楼梯按输入数据中给出的顺序编号为 $1$ 至 $m$）及其新位置（即该楼梯所连接的两个楼层编号，顺序任意）。

每段楼梯最多只能被移动一次。若存在多种解法，输出任意一种即可。