After a seemingly endless mob war, many of the caporegimes in your family are killed. Each capo leads a crew of soldiers, but now that these capos are dead, their soldiers are out of control. As the consigliere of your family, it is your job to hire new capos to lead the riotous soldiers. The soldiers you're dealing with are not gentle people. Soldiers often hold grudges with each other. As a result, certain soldiers cannot be placed in the same crew.
There are N soldiers that are out of control, and M two-way grudges that you know exist between pairs of soldiers. Since the capos you're hiring are new, you don't know if they can be trusted. The more capos you hire, the more likely it is that one of them will rat. You must help the Don determine the minimum number of capos required to lead the soldiers, such that no grudges exist amongst the same crew. Additionally, you must find one such way of grouping the soldiers.
The first line of input will contain two integers: N (1 ≤ N ≤ 15), the number of soldiers, and M (1 ≤ M ≤ N*(N-1)/2), the number of grudges.
The next M lines will each contain two integers a and b (1 ≤ a, b ≤ N), denoting a grudge between soldiers a and b.
The first line of output should contain an integer, the minimum number of crews required to group the soldiers.
Each remaining line represents a separate crew. For every crew, you must output the soldiers that it contains. You may output the groups/soldiers in any order.
5 7 1 2 1 5 2 4 2 5 3 4 3 5 4 5
3 1 4 2 3 5
Soldiers 1 and 4 are led by a capo, soldiers 2 and 3 are led by a capo, and soldier 5 is led by another capo. There exists no grudges within any of the three groups.
Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Aug 01, 2013
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3