Calvinball team division

$n$ players enter a Calvinball championship. The players are numbered $1$ through $n$, and every player joins exactly one non-empty team. There is no limit on the number of teams.

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

The organizers changed the team selection rule. Two players who dislike each other must not share a team, and among all divisions that respect this, the number of teams must be as small as possible.

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 impossible, because Batman, Tom and Jerry dislike each other, so the three of them need three different teams. Four teams is not the answer either, because a division into fewer teams exists.

Given who dislikes whom, divide the players into teams.

The first line contains the number of players $n$ and the number of disliking pairs $m$, separated by a space. ($0 \le n \le 14$, $0 \le m \le n(n-1)/2$)

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. No pair is given twice.

Print the smallest possible number of teams $t$ on the first line.

The teams are numbered $1$ through $t$. 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 $t$ teams, so print the one picked by this rule. Let $c_i$ be the number of the team that player $i$ belongs to. Print the division whose sequence $(c_1, c_2, \ldots, c_n)$ is lexicographically smallest. That is, keeping the number of teams at the minimum $t$, make $c_1$ as small as possible, then $c_2$ as small as possible, and so on. Exactly one division satisfies this rule.

If $n = 0$, print $0$ on the first line and nothing else.