În mijlocul fiecărui sat al elfilor se află câte un arbore strămoșesc. Acești arbori pot comunica unii cu alții prin intermediul unor mesaje magice.
Arborii sunt identificați prin numere cuprinse între 1 și n, unde n este numărul total al arborilor. Din nefericire nu este posibilă comunicarea dintre oricare doi arbori strămoșești. Mai mult, dacă un arbore poate transmite un mesaj unui alt arbore, nu este obligatoriu ca al doilea arbore să poată transmite mesaje primului arbore.
Se dorește identificarea grupurilor de arbori strămoșești în cadrul cărora este posibilă comunicarea directă sau indirectă între oricare doi arbori. Mai mult, numărul total al grupurilor trebuie să fie minim.
Prima linie a fișierului de intrare INPUT.TXT conține numărul n al arborilor strămoșești.
Cea de-a doua linie a fișierului de intrare conține numărul total m al legăturilor directe dintre arborii strămoșești. Fiecare dintre următoarele m linii conține câte două numere întregi, separate printr-un spațiu, care indică doi arbori strămoșești. Arborele identificat prin primul număr va putea transmite întotdeauna mesaje către arborele identificat prin al doilea număr.
Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie numărul k al grupurilor de arbori care sunt formate.
Fiecare dintre următoarele k linii va conține descrierea unui grup de arbori. O astfel de linie va conține numerele de ordine ale arborilor care formează grupul corespunzător liniei. Aceste numere vor fi separate prin câte un spațiu.
INPUT.TXT
4 5 1 2 2 3 2 4 3 1 3 4 OUTPUT.TXT 2 1 2 3 4
|