Problem description

Nastały czasy różnorakich wypraw morskich – wielkie odkrycia geograficzne, przygody, morskie potwory i piraci. Na świecie powstają wielkie imperia mające swoje terytoria we wszelkich zakątkach naszego globu. Zostałeś właśnie najważniejszym kartografem (obraźliwie zwanym mapoludem) jednego z największych imperiów na świecie. Twoim zadaniem będzie zaplanowanie odpowiednich handlowych szlaków morskich, które pozwolą skutecznie rozprowadzać różnorakie towary na obszar całego imperium. W końcu pracownicy bezpłatni sami nie dopłyną na plantacje, a egzotyczne owoce same nie wyrosną na stole władcy.

Widzisz przed sobą mapę całego świata, a na niej N zaznaczonych ważnych portów, numerowanych kolejnymi liczbami naturalnymi od 1 do N, a każdy z nich dostarcza reszcie świata ważne surowce. Ponadto na mapie zaznaczonych jest M dwukierunkowych tras morskich, a każda z tras morskich łączy ze sobą dwa różne porty. Twoim zadaniem jest zaplanowanie handlowych szlaków morskich.

Handlowy szlak morski to taki ciąg portów, że pomiędzy każdą parą portów sąsiednich w ciągu istnieje trasa morska je łącząca. W szczególności handlowy szlak morski może wielokrotnie przepływać przez ten sam port, jednak nigdy nie może przepływać dwukrotnie tą samą trasą morską.

Twoim zadaniem jest zaplanowanie minimalnej liczby handlowych szlaków morskich, które będą korzystały z każdej zaznaczonej na mapie trasy morskiej, jednak każda trasa morska może być używana przez dokładnie jeden handlowy szlak morski.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby naturalne N i M, oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę portów i tras morskich pomiędzy nimi. W kolejnych M wierszach znajdują się po dwie liczby naturalne A_i i B_i oddzielone pojedynczym odstępem i oznaczające istnienie trasy morskiej pomiędzy portami o numerach A_i i B_i. Pomiędzy każdą parą portów istnieje co najwyżej jedna trasa morska.

Wyjście

W pierwszym wierszu wyjścia należy wypisać jedną liczbę naturalną K – minimalną liczbę handlowych szlaków morskich, które spełnią założenia zadania. W kolejnych 2 ⋅ K wierszach powinny znaleźć się opisy proponowanych handlowych szlaków morskich.

Opis handlowego szlaku morskiego powinien składać się z dwóch wierszy. W pierwszym z nich powinna znajdować się jedna liczba naturalna X_i – liczba portów w proponowanym handlowym szlaku morskim. W drugim z nich powinno znaleźć się X_i liczb naturalnych pooddzielanych pojedynczymi odstępami i oznaczających numery kolejnych portów morskich w proponowanym handlowym szlaku morskim.

Jeśli istnieje wiele poprawnych odpowiedzi, możesz wypisać dowolną z nich.

Ograniczenia

2 ≤ N ≤ 100 000, 2 ≤ M ≤ 200 000, 1 ≤ A_i, B_i ≤ N, A_i ≠ B_i.

Przykład

9 8
1 2
2 3
2 4
2 5
6 7
7 8
8 9
9 6

3
3
1 2 5 
3
4 2 3 
5
9 6 7 8 9