Разделение врагов
Разделение врагов
Капитан Керам должен принять трудное решение. Шел 2147 год, в мире шла большая война. Его солдаты были вместе в начале войны, два года назад, а сейчас некоторые из них стали врагами. К счастью, у каждого солдата имеется не более 3 врагов.
Они должны напасть на другую страну в ближайшее время, и Керам обеспокоен тем, что солдаты, являющиеся врагами, не могут успешно сотрудничать во время боя. Он решил разделить их на группы таким образом, чтобы каждый солдат имел не более одного врага в своей группе. Он хочет найти простое решение, поэтому желает использовать как можно меньшее количество групп. Можете ли Вы разделить солдат в группы для него?
Входные данные
Первая строка содержит два целых числа n и m (2 ≤ n ≤ 100000, 0 ≤ m ≤ 3n/2), где n - количество солдат, а m - количество пар врагов. Каждая из следующих m строк содержит целые числа ai
, bi
(1 ≤ ai
< bi
≤ n) - номера солдат врагов. Считайте, что каждый солдат имеет не более 3 врагов.
Выходные данные
В первой строке выведите наименьшее количество групп солдат k. Каждая из следующих k строк должна содержать список солдат в каждой группе.
4 4 1 2 2 3 3 4 1 4
2 1 3 2 4