← 返回题目列表

Codeforces · 1170/G

G. 图分解

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

给你一个无向图,由 $$$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

注意

第一个例子对应的图片: