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
I get 'WA' i.e. wrong answer on the very last test.
Created quite a few datasets myself and can't see where my program is going wrong.
Can anyone give me a hint as to what I might be doing wrong?
I had bigger cases, but was hesitant to add them because I didn't think it was fair. I either guess you guys are too pro , or my interpretation skills are bad.
Whatever, bounds increased with 2 more cases for now (and even more to come later today when I get home).
And now these bounds are getting somewhat ridiculous.
Since brute force works somehow, the value stays as 10 and the limit is back down as I originally intended.