Mail Lady

The lady works as a postwoman after school. She finds this job incredibly interesting and has been doing it for quite some time. As the most experienced postwoman, she ensures that all letters are delivered promptly and plans the routes for the postmen.

The city where she lives is divided into postal districts. Each district has a network of roads connecting intersections where residents' houses are located. These roads can be traveled in both directions. Any number of people can be employed in postal services within each district.

Every morning, each postman receives a bag with letters to be delivered along a route that passes through some streets of the district. Each route must satisfy the conditions set by the lady:

1. The route starts and ends at the same intersection.

2. The route never passes through the same intersection twice.

3. The route must not share any road with any other route. That is, each road must be serviced by exactly one postman.

Together, all the postmen must fully service the district. Each road must belong to exactly one route.

As you might have guessed, the lady is responsible for planning the postmen's routes. She can hire any number of postmen. She asks you to find a set of routes for the postmen in certain postal districts that will satisfy all the conditions.

Input

The first line contains two integers $n$ and $m$ ($3\le n\le 5\cdot 10^5$, $3\le m\le 5\cdot 10^5$) — the number of intersections and the number of roads.

Each of the next $m$ lines contains two integers $u$ and $v$ ($1\le u,v\le n,u\ne v$) — the intersections between which there is a road.

The input data satisfies the conditions:

1. Any two intersections are connected by at most one road.

2. There is a path between any two intersections that may pass through one or more roads.

3. There is a solution, meaning the lady can always find a set of routes that satisfy all the conditions.

Output

In the first line, output a single integer $d$ ($1\le d\le m$) — the number of routes.

In each of the next $d$ lines, output a single integer $w$ ($1\le w\le m$) — the number of intersections in the route, followed by $w$ integers $l_1,l_2,\dots ,l_w$ ($1\le l_i\le n$) — the intersection numbers. The intersections should be output in the order in which the postman will traverse them. The intersection where the postman's route starts and ends should be output only once at the beginning of the route.

If there are multiple solutions, your program may output any of them.

Examples

Scoring

1. ($38$ points): $3\le n\le 2000,3\le m\le 10^5$;

2. ($17$ points): $3\le n\le 10^5,3\le m\le 10^5$;

3. ($45$ points): $3\le n\le 5\cdot 10^5,3\le m\le 5\cdot 10^5$.