Розділення ворогів
Капітан Керам стоїть перед важким вибором. Настав 2147 рік, і світ охопила велика війна. Його солдати були разом на початку конфлікту два роки тому, але тепер деякі з них стали ворогами. На щастя, кожен солдат має не більше 3 ворогів.
Незабаром вони повинні атакувати іншу країну, і Керам хвилюється, що солдати, які є ворогами, не зможуть ефективно співпрацювати в бою. Він вирішив розділити їх на групи так, щоб у кожній групі кожен солдат мав не більше одного ворога. Керам прагне знайти просте рішення, тому хоче використати якомога менше груп. Чи зможете ви допомогти йому розподілити солдатів на групи?
Вхідні дані
Перша стрічка містить два цілі числа n і m (2 ≤ n ≤ 100000, 0 ≤ m ≤ 3n/2), де n - це кількість солдатів, а m - кількість пар ворогів. Кожна з наступних m стрічок містить цілі числа a[i], b[i] (1 ≤ a[i] < b[i] ≤ n) - номери солдатів, які є ворогами. Вважайте, що кожен солдат має не більше 3 ворогів.
Вихідні дані
На першій стрічці виведіть найменшу кількість груп солдатів k. Кожна з наступних k стрічок повинна містити список солдатів у кожній групі.