Республіки#5464
У країні є міст, деякі з яких з'єднані двосторонніми дорогами. Можна доїхати з будь-якого міста в будь-яке інше. Для поповнення казни деякі дороги вже були закриті. Казначейство бажає закрити ще більше доріг, але тоді король не зможе доїхати до деяких міст своєї країни.
Для подальшої економії був розроблений план поділити країну на республіки, доручивши турботу про дороги місцевим правителям. Однак республіки не можна утворювати довільно — у кожній республіці має бути не менше доріг, щоби республіканська поліція могла ефективно справлятися із заворушеннями. Також у кожній республіці має бути можливо доїхати з будь-якого міста в будь-яке, не виїжджаючи за її межі. Казначейство хоче створити якомога більше республік, вважаючи, що чим більше республік, тим більший дохід. Зрозуміло, що кожне місто має входити рівно в одну республіку. Допоможіть їм виконати цей план.
У першому рядку містяться два цілих числа: 1 \leq N \leq 100 та M \geq N-1 — кількість міст і кількість доріг у країні відповідно. У наступних рядках міститься опис доріг — кожен рядок містить два числа 1 \leq x, y \leq N. В останньому рядку міститься число 1 \leq K \leq M — мінімальна кількість доріг у республіці.
У першому рядку виведіть — максимальну кількість республік. У наступних рядках має бути опис республік, по одному опису в рядку. У кожному описі спочатку виведіть кількість міст у республіці, потім перелічіть номери міст у цій республіці через пробіл.
Приклад 1