Calvinball team assignment

The Calvinball championship is on again. A game is played by $n$ players with distinct names, and the players are divided into some number of non-empty teams. Some players dislike each other. Disliking is symmetric: if player $a$ dislikes player $b$, then $b$ dislikes $a$.

The organizers changed the rule for building teams. Two players who dislike each other may not be on the same team, and subject to that, 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 enough: Batman alone, Tom with Susie, and Calvin with Hobbes and Jerry. Two teams are not enough, because Batman, Tom, and Jerry dislike one another and must go to three different teams. Four teams is not an answer either, because three teams work.

Given who dislikes whom, produce a division of the players into teams that follows the rule.

The first line contains the number of players $n$ and the number of pairs of players who dislike each other $m$. ($1 \le n \le 15$, $0 \le m \le n(n-1)/2$)

Players are numbered from $1$ to $n$. Each of the next $m$ lines contains two different integers $a_i$ and $b_i$, meaning that players $a_i$ and $b_i$ dislike each other. ($1 \le a_i, b_i \le n$, $a_i \ne b_i$) No pair is given twice, and the two numbers of a pair come in either order.

Print the 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.

Several divisions can use the minimum number of teams, so the team numbers are fixed as follows. Let $c_i$ be the number of the team that player $i$ belongs to. Among all valid assignments, print the one whose sequence $(c_1, c_2, \dots, c_n)$ is lexicographically smallest. In that assignment every team from $1$ to $t$ holds at least one player.