Calvinball championship, again

The Calvinball championship is held again this year. A game is played by $n$ players with distinct names. Every player belongs to exactly one team, and no team is empty. Some players dislike each other. Disliking is symmetric: if player $a$ dislikes player $b$, then $b$ dislikes $a$.

The organizers changed the rule for forming 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 each other pairwise and need three different teams. Four teams are not an answer either, since three teams are possible and the number of teams has to be smallest.

Several divisions can satisfy the rule, so exactly one of them is asked for. Number the teams $1$ through $t$ and let $c_i$ be the number of the team that player $i$ belongs to. Among all divisions into the smallest number of teams and all ways of numbering those teams, the answer is the one whose sequence $(c_1, c_2, \dots, c_n)$ is lexicographically smallest. A sequence $A$ comes before a sequence $B$ lexicographically if $A$ holds the smaller value at the first position where the two differ. Under this rule player $1$ always belongs to team $1$.

The first line contains the number of players $n$ and the number of disliking pairs $m$ ($1 \le n \le 16$, $0 \le m \le n(n-1)/2$). The players are numbered $1$ through $n$. Each of the next $m$ lines contains two different integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$), meaning that players $a_i$ and $b_i$ dislike each other. The same pair is never given twice, in either order.

Print the smallest possible number of teams $t$ on the first line. Then print $t$ lines, where line $i$ contains the numbers of the players on team $i$ in increasing order, separated by single spaces. The team numbering must follow the lexicographically smallest rule stated above.