În Pădurea Aurie există n obiective strategice care sunt legate printr-un număr total de m cărări pe care se poate circula în ambele sensuri.
    Elfii doresc să organizeze un serviciu de pază în cadrul căruia se stabilesc traseele parcurse de străjeri.
    Un traseu poate fi format din mai multe obiective strategice (cel puțin trei) astfel încât două obiective aflate pe poziții consecutive sunt legate direct printr-o cărare.
    În plus, primul și ultimul obiectiv trebuie să fie și ele legate printr-o cărare.
    Se dorește stabilirea unui număr maxim de astfel de trasee în așa fel încât pentru parcurgerea fiecărui traseu să fie necesară utilizarea unei cărări care să nu fie utilizată pentru nici unul dintre celelalte trasee.

Prima linie a fișierului de intrare INPUT.TXT conține numărul n al obiectivelor strategice.
    Cea de-a doua linie a fișierului de intrare conține numărul total m al cărărilor dintre obiectivele strategice.
    Fiecare dintre următoarele m linii ale fișierului conține câte două numere întregi, separate printr-un spațiu, care identifică două obiective strategice ale elfilor care sunt legate printr-o cărare.

Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie un număr k care reprezintă numărul traseelor care vor fi stabilite.
    Fiecare dintre următoarele k linii trebuie să descrie un traseu.
    Primul număr de pe o astfel de linie va conține numărul t al obiectivelor care fac parte din traseul respectiv.
    Linia va mai conține t numere care identifică obiectivele de pe traseul respectiv, în ordinea în care acestea ar trebui parcurse.
    Numerele de pe o linie vor fi separate prin câte un spațiu.

  • numărul obiectivelor strategice este cuprins între 3 și 100;
  • numărul total al cărărilor dintre obiectivele strategice este cel mult egal cu 1000:
  • obiectivele strategice vor fi identificate prin numere cuprinse între 1 și n;
  • fiecare obiectiv strategic poate apărea o singură dată în cadrul unui traseu;
  • dacă există mai multe soluții, va fi generată oricare dintre ele;
  • traseele pot fi descrise în orice ordine;
  • între două obiective strategice poate exista cel mult o cărare.


  • 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
    4
    4 1 2 4 3
    3 2 3 4
    3 5 6 7
    3 8 9 10