给你一个无向图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。
回想一下,循环是在同一顶点开始和结束的路径。如果图中的一个循环包含每个顶点(起始点和结束点除外)不超过一次(起始点和结束点总是包含两次),则该循环被称为简单循环。请注意,循环被视为简单循环。
一步操作中,您可以选择该图中的任何简单循环并擦除与该循环对应的边(相应的顶点保留在图中)。允许擦除循环或同一边的两个副本(查看示例)。
你的问题是应用一些移动序列来获得没有边的图形。没有必要最小化循环次数。如果不可能,请打印“NO”。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 图中的顶点数和边数。
接下来的 $$$m$$$ 行包含图形的边缘。第 $$$i$$$ 行包含第 $$$i$$$ 边 $$$x_i, y_i$$$ ($$$1 \le x_i, y_i \le n$$$),其中 $$$x_i$$$ 和 $$$y_i$$$ 是第 $$$i$$$ 边连接的顶点。该图可以包含循环或多条边。
输出
如果无法将给定的图分解为简单的循环,请在第一行打印“NO”。
否则在第一行打印“YES”。在第二行中打印 $$$k$$$ — 图分解中的简单循环数。
在接下来的 $$$k$$$ 行中打印循环本身。第 $$$j$$$ 行应包含第 $$$j$$$ 循环。首先,打印 $$$c_j$$$ — 第 $$$j$$$ 个循环中的顶点数。然后将循环打印为顶点序列。打印路径中的所有相邻(相邻)顶点应通过不包含在其他循环中的边连接。
示例
输入 #1
6 9 1 2 2 3 1 3 2 4 2 5 4 5 3 5 3 6 5 6
输出 #1
YES 3 4 2 5 4 2 4 3 6 5 3 4 1 3 2 1
输入 #2
4 7 1 1 1 2 2 3 3 4 4 1 1 3 1 3
输出 #2
YES 3 2 1 1 5 1 4 3 2 1 3 1 3 1
输入 #3
4 8 1 1 1 2 2 3 3 4 4 1 2 4 1 3 1 3
输出 #3
NO
注意
第一个例子对应的图片: