Enemy Division#6029
Captain Keram has to make a difficult decision. It is year 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 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 and ( ≤ ≤ , ≤ ≤ ), where is the number of soldiers and is the number of enemy pairs. Then follow lines, each containing two space separated integers a_i, b_i, denoting that soldiers a_i and b_i are enemies, where ≤ a_i < b_i ≤ . You can assume that all soldiers have at most enemies.
The first line of output contains the minimal number of groups of soldiers . Each of the next lines contains a space separated list of soldiers in a unique group.
Example 1