johnie

In a far away country there lived Johnie Walker, a character who really enjoyed walks. In Johnie Walker's country there are N cities (numbered from 1 to N), and between certain pairs of cities there are alleyways. Johnie wants to travel every alleyway in his country. As such, he's decided to take one big walk, in several stages. In each stage, Johnie leaves from any city in the country, travels a certain trip and stops in whichever city he wants. A trip is represented by a row of cities, so that there is an alleyway between any 2 consecutive cities. In his walk, Johnie wants to travel each alleyway only once. He doesn't care if he goes through a city more than once, even on the same trip.

Task

Being given the number of cities from the country and the alleyways between them, determine minimum number of stages in which Johnie can travel all the alleyways. Also, determine a way to travel the alleyways in stages.

Input Data

Line one of input file johnie.in describes two positive integers separated by a space, N, representing the number of cities and M, representing the number of alleyways. Each of the following M lines contains two distinct positive integers, i j (between 1 and N) with the meaning that there is a path from city i to city j.

Output Data

Output file johnie.out will contain on line one a positive integer min representing the minimum number of walk stages. The following min lines represent the trips Johnie travels every day in each stage, one trip per line. The first number off the line describing a trip is the number of cities traveled in said trip, and the following numbers representing the cities traveled, in the order they are traveled. Numbers written on the same line are separated by a space.

Restrictions and Mentions

• 1 <= N <= 50000
• 1 <= M <= 100000
•There can be more than one alleyway between two cities.
•An alleyway is two-directional.
•There are no alleyways beginning and ending in the same city.

Example

Time limit: 0.5 seconds/test

Daniel Pasaila
"Al. I Cuza" University, Iaşi - IT Department
danielpasaila@yahoo.com