Datorită faptului că atacurile orcilor continuă, elfii trebuie să ia măsuri drastice.
Ei vor să grupeze cele m cărări dintre cele n sate ale elfilor în grupuri, astfel încât dacă se pierde controlul asupra unuia dintre satele care se află la extremitatea unei cărări dintr-un grup, atunci va exista în continuare posibilitatea de a călători între toate celelalte sate care sunt extremități ale cărărilor din grup. Practic, se vor forma grupuri de sate (un sat poate face parte din mai multe grupuri), astfel încât, dacă se pierde controlul asupra unui sat dintr-un grup, va exista în continuare posibilitatea de a călători între oricare alte două sate ale grupului.
Un grup de sate nu poate fi subgrup al unui alt grup. Cu alte cuvinte, aceste grupuri trebuie să fie maximale.
Prima linie a fișierului de intrare INPUT.TXT conține numărul n al satelor elfilor.
Cea de-a doua linie a fișierului de intrare conține numărul total m al cărărilor dintre satele elfilor. Fiecare dintre următoarele m linii ale fișierului conține câte două numere întregi, separate printr-un spațiu, care identifică două sate care sunt legate printr-o cărare.
Prima linie a fișierului de ieșire OUTPUT.TXT trebuie să conțină numărul k al grupurilor care vor fi formate.
Fiecare dintre următoarele k linii trebuie să descrie un grup. Primul număr de pe o astfel de linie va conține numărul t al satelor care fac parte din grupul corespunzător liniei. Linia va mai conține t numere care identifică satele care formează grupul.
INPUT.TXT
10 13 1 2 1 3 2 3 2 4 3 4 3 5 4 8 5 6 5 7 6 7 8 9 8 10 9 10 OUTPUT.TXT 5 4 1 2 3 4 2 3 5 2 4 8 3 5 6 7 3 8 9 10
|