There are
N cities numbered from 1 to
N (1 ≤
N ≤ 200)
and
M 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,
T2, …,
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.
Пример
исходные данные | результат |
---|
5 7
1 2
1 3
1 4
2 4
2 3
3 4
5 4
| 3
3 1 2 4
3 1 4 3
4 1 2 3 4
|
Автор задачи: Nguyen Xuan My (Converted by Dinh Quang Hiep and Tran Nam Trung)
Источник задачи: From the third contest at Department of Mathematics and Informatics - Natural Sciences College - National University of HaNoi.