Graph Decomposition

Description:

Input:

The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of vertices and the number of edges in the graph.

The next $$$m$$$ lines contain edges of the graph. The $$$i$$$-th line contains the $$$i$$$-th edge $$$x_i, y_i$$$ ($$$1 \le x_i, y_i \le n$$$), where $$$x_i$$$ and $$$y_i$$$ are vertices connected by the $$$i$$$-th edge. The graph can contain loops or multiple edges.

Output:

If it is impossible to decompose the given graph into simple cycles, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line print $$$k$$$ — the number of simple cycles in the graph decomposition.

In the next $$$k$$$ lines print cycles themselves. The $$$j$$$-th line should contain the $$$j$$$-th cycle. First, print $$$c_j$$$ — the number of vertices in the $$$j$$$-th cycle. Then print the cycle as a sequence of vertices. All neighbouring (adjacent) vertices in the printed path should be connected by an edge that isn't contained in other cycles.

Sample Input:

6 9
1 2
2 3
1 3
2 4
2 5
4 5
3 5
3 6
5 6

Sample Output:

YES
3
4 2 5 4 2 
4 3 6 5 3 
4 1 3 2 1 

Sample Input:

4 7
1 1
1 2
2 3
3 4
4 1
1 3
1 3

Sample Output:

YES
3
2 1 1 
5 1 4 3 2 1 
3 1 3 1 

Sample Input:

4 8
1 1
1 2
2 3
3 4
4 1
2 4
1 3
1 3

Sample Output:

NO

Note:

The picture corresponding to the first example: