Капитан Керам должен принять трудное решение. Шел 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 строк должна содержать список солдат в каждой группе.