Republics
In the country, there are N cities, some of which are connected by two-way roads. It is possible to travel from any city to any other city. However, to support the treasury, some roads have been closed. The treasury would like to close even more, but doing so would prevent the king from reaching some cities.
To further economize, a plan has been devised to divide the country into republics, assigning the maintenance of roads to local rulers. Republics cannot be formed arbitrarily—each must have at least K roads to ensure the republican militia can effectively manage disturbances. Additionally, it must be possible to travel between any two cities within a republic without crossing its borders. The treasury aims to create as many republics as possible, believing that more republics will lead to more revenue. Naturally, each city must belong to exactly one republic. Assist them in achieving this goal.
Input
The first line contains two integers: 1 ≤ N ≤ 100 and M ≥ N-1, representing the number of cities and the number of roads in the country, respectively. The following M lines describe the roads, with each line containing two numbers 1 ≤ x, y ≤ N. The last line contains the integer 1 ≤ K ≤ M, which is the minimum number of roads required in a republic.
Output
On the first line, output R, the maximum number of republics. The next R lines should provide descriptions of the republics, one per line. For each republic, first state the number of cities it contains, followed by the list of city numbers in that republic.