There are N
cities numbered from 1 to N
(1 ≤ N
two-way roads connect them. There are at most one road between two cities. In summer holiday, members of DSAP Group want to make some traveling tours. Each tour is a route passes K
different cities (K
> 2) T1
, …, TK
and return to T1
. Your task is to help them make T
tours such that:
- Each of these T tours has at least a road that does not belong to (T−1) other tours.
- T is maximum.
The first line of input contains N and M separated with white spaces. Then follow by M lines, each has two number H and T which means there is a road connect city H and city T.
You must output an integer number T — the maximum number of tours. If T > 0, then T lines followed, each describe a tour. The first number of each line is K — the amount of different cities in the tour, then K numbers which represent K cities in the tour.
If there are more than one solution, you can output any of them.
3 1 2 4
3 1 4 3
4 1 2 3 4
Problem Author: Nguyen Xuan My (Converted by Dinh Quang Hiep and Tran Nam Trung)
Problem Source: From the third contest at Department of Mathematics and Informatics - Natural Sciences College - National University of HaNoi.