police      

In a city the new Traffic Police Chief tries to decrease the number of police officers that sit in their offices without any real tasks. For this purpose he wants to send as many officers on the field, in order to watch the city streets. In the city there are m streets and n intersections. Intersections are numbered from 1 to n. A street connects two intersections and is identified by the two intersections that delimit it.
The Chief thinks he will control the officers more easily if he will assign to each of them the same type of route. By route he understands a sequence of intersections that meets the following conditions:
- there is a connecting street between any two consecutive intersections on the route;
- from any route intersection he might be at, the officer can go through every street of the route by going on each street only once and arriving back at the departure intersection;
- the route assigned to each officer must contain at least one street that is not being watched by the other officers on patrol.
An officer will only go on streets on his route.

Task
Write a program that determines the maximum number of police officers that can be sent on the field and the routes assigned to each of them.

Input data
Input file police.in has the following structure:   
- on the first line there are two integers separated by a space n m, representing the number of intersections and, respectively, the number of streets;
- the next m lines contain information about the m streets, one street per line; for every street there are two integers between 1 and n separated by a space, representing the two intersections that delimit the street.

Output data
Output file police.out will have the following structure:   
- number p will be written on the first line, representing the maximum number of officers that can be sent on the field;
- the next p lines will contain the routes assigned to the officers, one route per line; the intersections located on each route will be specified, any two consecutive intersections being separated by a space.

Constraints
1 < n <= 1500
0 < m <= 4000
In case there is more than one solution only one shall be provided.
Between any two intersections there must be at most one street.

Example

Time limit: 0.3 seconds/test

prof. Dana Lica
“Ion Luca Caragiale” National College - Ploiesti
Contact: danal182001@yahoo.com