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?

Input

On the first line there are two integers n and m (2 ≤ n ≤ 100000, 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 ai, bi, denoting that soldiers ai and bi are enemies, where 1 ≤ ai < bi ≤ n. You can assume that all soldiers have at most 3 enemies.

Output

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.