Calvinball team assignment

The Calvinball championship is held in the Czech Republic again this year. A game of Calvinball is played by $n$ players with distinct names, split into some number of non-empty teams. Some players dislike each other. Disliking is symmetric: if player $a$ dislikes player $b$, then $b$ also dislikes $a$.

The championship organizers changed the team selection rule. No two players who dislike each other may be on the same team, and among the splits that respect this, the number of teams must be as small as possible.

For example, suppose Calvin, Hobbes, Susie, Tom, Jerry and Batman play, Batman dislikes the other five, and Tom dislikes Jerry and Hobbes. Three teams are then enough: Batman alone, Tom with Susie, and Calvin with Hobbes and Jerry. Two teams are impossible, because Batman, Tom and Jerry dislike each other and must go to three different teams. Four teams is not the answer either, because a smaller number works.

Given the dislike relation, find a split into the smallest number of teams. Several such splits can exist, so the output rule below picks exactly one of them.

The first line contains the number of players $n$ and the number of disliking pairs $m$. ($1 \le n \le 15$, $0 \le m \le n(n-1)/2$) The players are numbered from $1$ to $n$.

Each of the next $m$ lines contains two distinct integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), meaning that players $a$ and $b$ dislike each other. No pair is given twice.

Print the minimum number of teams $t$ on the first line. On the $i$-th of the next $t$ lines, print the numbers of the players on team $i$ in increasing order, separated by single spaces.

When several splits use $t$ teams, print the one this rule selects. Let $c_i$ be the number of the team that player $i$ joins. Among all splits into $t$ teams, print the one whose sequence $(c_1, c_2, \ldots, c_n)$ is lexicographically smallest. Under this rule player 1 always joins team 1, and the smallest player number on a team grows as the team number grows.