Calvinball championship team split

The Calvinball championship is held in Czech Republic this year. A game is played by $n$ players with distinct names, and the players are divided into teams. No team may be empty, and every player belongs to exactly one team.

Some pairs of players dislike each other. Disliking is symmetric: if player $a$ dislikes player $b$, then $b$ dislikes $a$.

The International Calvinball Disorganization changed the team selection rule at the last minute. Two players who dislike each other may not share a team, and among all divisions that obey 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 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 need three different teams. Four teams is not the answer either, because three teams already work.

Several divisions into the minimum number of teams may exist, so the answer is fixed as follows. Let $c_i$ be the number of the team that player $i$ belongs to. Print the division whose sequence $(c_1, c_2, \dots, c_n)$ is lexicographically smallest, using team numbers $1$ to $t$. Under that rule the teams come out ordered by their smallest member, and player $1$ is always in 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$ to $n$.

Each of the next $m$ lines contains two different integers $a_i$ and $b_i$. ($1 \le a_i, b_i \le n$) It means players $a_i$ and $b_i$ dislike each other. The same pair is never given twice.

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

Number the teams so that the sequence $(c_1, c_2, \dots, c_n)$ is lexicographically smallest, where $c_i$ is the number of the team holding player $i$. That rule makes the answer unique.