## 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)

Davo36on Jul 28, 2016 - 3:37:03 am UTC Nearly There...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

SourSpinachon Aug 02, 2013 - 9:13:52 am UTC Man, there are some weird algorithms happeningAlexon Aug 02, 2013 - 9:46:00 am UTC Re: Man, there are some weird algorithms happeningI 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).

SourSpinachon Aug 02, 2013 - 6:01:59 pm UTC Re: Man, there are some weird algorithms happeningAnd now these bounds are getting somewhat ridiculous.

Alexon Aug 02, 2013 - 8:29:23 pm UTC Re: Man, there are some weird algorithms happeningSince brute force works somehow, the value stays as 10 and the limit is back down as I originally intended.