Respublikalar#5464
Ölkədə şəhər var və bəziləri ikitərəfli yollarla birləşdirilib. İstənilən şəhərdən digərinə getmək mümkündür. Xəzinəni dəstəkləmək üçün bəzi yollar artıq bağlanıb. Xəzinədarlıq daha çox yol bağlamaq istərdi, amma bu halda kral ölkənin bəzi şəhərlərinə gedə bilməzdi.
Daha çox qənaət etmək üçün ölkəni respublikalara bölmək və yolların idarəsini yerli hökmdarlara həvalə etmək planı hazırlanıb. Lakin respublika istənilən şəkildə yaradılması mümkün deyil — əgər orada ən azı yol yoxdursa, respublika polisi qarışıqlıqlarla effektiv mübarizə apara bilməz. Bundan əlavə, hər bir respublikada istənilən şəhərdən digərinə, sərhədləri aşmadan getmək mümkün olmalıdır. Xəzinədarlıq mümkün qədər çox respublika yaratmaq istəyir, çünki daha çox respublika, daha çox gəlir deməkdir. Hər bir şəhər yalnız bir respublikaya daxil olmalıdır. Onlara bu işdə kömək edin.
Birinci sətirdə iki tam ədəd: 1 \leq N \leq 100 və M \geq N-1 — ölkədəki şəhərlərin və yolların sayı verilir. Növbəti sətirdə yolların təsviri verilir — hər bir sətrdə iki ədəd 1 \leq x, y \leq N verilir. Sonuncu sətirdə 1 \leq K \leq M — respublikada minimum yol sayı.
Birinci sətirdə — maksimum respublika sayını çıxarın. Növbəti sətir respublikaların təsvirini ehtiva etməlidir, hər biri bir sətrdə olmalıdır. Hər bir təsvirin əvvəlində respublikadakı şəhərlərin sayını, sonra isə bu respublikadakı şəhərlərin nömrələrini sadalayın.
Nümunə 1