Republics#5464
In the country, there are 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 already been closed. The treasury would like to close even more, but doing so would prevent the king from reaching some cities in his realm.
To further save costs, a plan has been devised to divide the country into republics, assigning road maintenance to local rulers. Republics cannot be formed arbitrarily—each must include at least roads, so that the republican militia can effectively manage disturbances. Furthermore, within a republic, it must be possible to travel from any city to any other city without crossing the republic's borders. The treasury wants to create as many republics as possible, believing that a greater number of republics will bring more revenue. Of course, each city must belong to exactly one republic. Help them achieve this goal.
The first line contains two integers: 1 \leq N \leq 100 and M \geq N-1, representing the number of cities and the number of roads in the country, respectively. The following lines describe the roads, each with two integers 1 \leq x, y \leq N. The last line contains the integer 1 \leq K \leq M, indicating the minimum number of roads required in a republic.
On the first line, output , the maximum number of republics. The next lines should describe the republics, one per line. For each republic, first output the number of cities it contains, followed by the list of city numbers in that republic, separated by spaces.
Example 1