eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Разделение врагов

Разделение врагов

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
prb6029

Капитан Керам должен принять трудное решение. Шел 2147 год, в мире шла большая война. Его солдаты были вместе в начале войны, два года назад, а сейчас некоторые из них стали врагами. К счастью, у каждого солдата имеется не более 3 врагов.

Они должны напасть на другую страну в ближайшее время, и Керам обеспокоен тем, что солдаты, являющиеся врагами, не могут успешно сотрудничать во время боя. Он решил разделить их на группы таким образом, чтобы каждый солдат имел не более одного врага в своей группе. Он хочет найти простое решение, поэтому желает использовать как можно меньшее количество групп. Можете ли Вы разделить солдат в группы для него?

Входные данные

Первая строка содержит два целых числа n и m (2n100000, 0m3n/2), где n - количество солдат, а m - количество пар врагов. Каждая из следующих m строк содержит целые числа a[i], b[i] (1a[i] < b[i]n) - номера солдат врагов. Считайте, что каждый солдат имеет не более 3 врагов.

Выходные данные

В первой строке выведите наименьшее количество групп солдат k. Каждая из следующих k строк должна содержать список солдат в каждой группе.

Пример

Входные данные #1
4 4
1 2
2 3
3 4
1 4
Выходные данные #1
2
1 3
2 4
Источник 2011 Nordic Collegiate Programming Contest, 1 Октября, Задача J