5020번 - Enemy Division 스페셜 저지다국어

Captain Keram has to make a difficult decision. It is year 2147 and there is a big war in the world. His soldiers have been together since the war started, two years ago, and some of them have become enemies. Luckily, each soldier has at most 3 enemies.

They need to attack another country soon, and Keram is worried that soldiers who are enemies might not cooperate well during the battle. He has decided to divide them into groups such that every soldier has at most one enemy in his group. He also wants to make it simple, so he wants to use as few groups as possible. Can you divide the soldiers into groups for him?

On the first line there are two integers n and m, 2 ≤ n ≤ 100 000, 0 ≤ m ≤ 3n/2, where n is the number of soldiers and m is the number of enemy pairs. Then follow m lines, each containing two space separated integers a_i, b_i, denoting that soldiers a_i and b_i are enemies, where 1 ≤ a_i < b_i ≤ n. You can assume that all soldiers have at most 3 enemies.

The first line of output contains the minimal number of groups of soldiers k. Each of the next k lines contains a space separated list of a soldiers in a unique group.