Caporegime

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.

Input

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.

Output

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.

Sample Input

5 7
1 2
1 5
2 4
2 5
3 4
3 5
4 5

Sample Output

3
1 4
2 3
5

Explanation

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.

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Aug 01, 2013
Author: Alex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Hi guys, I get the right answer on all datasets bar the last one.

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?


Cheers

David

SourSpinach on Aug 02, 2013 - 9:13:52 am UTC Man, there are some weird algorithms happening

• (0/0)

But I'm pretty sure this should only be worth 10 points, unless my solution is not intended to pass (in which case, looks like some far stronger data is required).

But I'm pretty sure this should only be worth 10 points, unless my solution is not intended to pass (in which case, looks like some far stronger data is required).

Alex on Aug 02, 2013 - 9:46:00 am UTC Re: Man, there are some weird algorithms happening

• (0/0)

This is the weirdest thing, because Wikipedia said that the best known exact solution was at least around O(2^n*n), which is like 32 billion for n=30.
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 :applause:, 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).

This is the weirdest thing, because Wikipedia said that the best known exact solution was at least around O(2^n*n), which is like 32 billion for n=30.
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).

SourSpinach on Aug 02, 2013 - 6:01:59 pm UTC Re: Man, there are some weird algorithms happening

• (0/0)

Well, yeah, it's absolutely true that this problem is NP-complete and no real "nice" algorithms exist, so N=30 is already too large. But I guessed that brute force would be fine in most cases, and indeed, it happened to pass easily - though all of that means that this is not a great problem.

And now these bounds are getting somewhat ridiculous.

Well, yeah, it's absolutely true that this problem is NP-complete and no real "nice" algorithms exist, so N=30 is already too large. But I guessed that brute force would be fine in most cases, and indeed, it happened to pass easily - though all of that means that this is not a great problem.

And now these bounds are getting somewhat ridiculous.

Alex on Aug 02, 2013 - 8:29:23 pm UTC Re: Man, there are some weird algorithms happening

• (0/0)

The valuation was initially set by Daniel after I made him solve it (his solution is the intended one).
Since brute force works somehow, the value stays as 10 and the limit is back down as I originally intended.

The valuation was initially set by Daniel after I made him solve it (his solution is the intended one).
Since brute force works somehow, the value stays as 10 and the limit is back down as I originally intended.