Harry Potter and Moving Staircases

题意翻译

### 题意翻译 #### 题目描述 哈利波特在从管理员费尔奇那里逃走时，丢失了他的隐形衣。寻找一件隐形的物件可不是一件容易的事情。幸运的是哈利有乐意帮助他的朋友们。赫敏·格兰杰读了“隐形衣和关于它们的一切”，以及“最短路径百科全书”，“网络流”，“最长上升子序列”和其他的魔法物品。她已经为在复杂的动态系统（霍格沃茨是其中一个）中的隐形衣开发了一套搜索算法。 霍格沃茨由 n 层组成，这 n 层分别从 1 到 n 标号。一些楼层被楼梯连着。这些楼梯会改变自己一端的位置。通常情况像这样：如果之前连接着 a 层和 b 层，那么它移动后就可能连接 a 层和 c 层或 b层和 c 层，其中 c 层不为 a 层或 b 层。任何情况下楼梯都不能和本身相连。同时可以有多个楼梯连接相同楼层。 现在楼梯的活动十分少。然而，罗恩和赫敏很乐意去在它们上面释放法术来帮助哈利找到隐形衣。为了减少怀疑，三个人计划一个个移动楼梯。在两次移动楼梯中间，哈利可以在楼层上走动，从楼梯上到达另一层来寻找自己的隐形衣。此时可以认为楼梯不会自主移动。 请帮助三人来制定一个搜索的计划。如果有多个不同的方法可以解决问题（不一定是最优情况下），都可以被接受。 #### 输入格式 第一行是两个整数 n 和 m $(1 \le n \le 10^5,0\le m \le 2\times 10^5)$,分别表示楼层数量和楼梯的数量。以下有m行，每行两个数，表示开始阶段一对被楼梯连接的楼层。 #### 输出格式 如果哈利可以搜索所有楼层，在第一行输出 ``YES`` ，否则输出 ``NO``.如果可以搜索所有楼层,那么在第二行输出要移动的楼梯总数。 接下来的输出如下: 哈利的移动 楼梯的移动 哈利的移动 楼梯的移动 $\cdots$ 楼梯的移动 哈利的移动 每一次“哈利的移动”需要按哈利搜索的顺序用一串楼层的形式表现。所有串的元素总数不得超过$10^6$。在输出每一个楼层串时，先输出元素的数量再在同一行内输出被空格分开的每个元素。第一个楼层串的第一个号码应该是1号。除了第一个楼层串之外的任何楼层串都可能会包含0个元素。哈利可以多次访问一些楼层，但必须至少访问1~n中的每个楼层一次。哈利连续搜索的两个楼层必须通过楼梯连接，同时这两个楼层不能相等。 在“楼梯移动”中，应指出这个楼梯的编号（编号是按输入的顺序从1~m依次编号）和它移动后连接的两个楼层（任何顺序都可以）。 任何一个楼梯最多只能移动一次。如果有多组解，输出任意一组均可。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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 $ 10^{6} $ . 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.

输入输出样例

输入样例 #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