캘빈볼 대회 팀 나누기

올해도 체코에서 캘빈볼 대회가 열린다. 한 경기에는 이름이 모두 다른 선수 $n$명이 참가하고, 선수들은 비어 있지 않은 팀 여러 개로 나뉜다. 몇몇 선수는 서로를 싫어한다. 이 관계는 대칭이라서, 선수 $a$가 선수 $b$를 싫어하면 $b$도 $a$를 싫어한다.

대회 조직위원회는 팀을 짜는 규칙을 바꿨다. 서로 싫어하는 두 선수는 같은 팀에 들어갈 수 없고, 이 조건을 지키는 편성 중에서 팀 수가 가장 적어야 한다.

예를 들어 캘빈, 홉스, 수지, 톰, 제리, 배트맨이 경기에 나서고 배트맨이 나머지 다섯 명을 모두 싫어하며 톰은 제리와 홉스를 싫어한다고 하자. 이때는 팀 세 개로 경기를 할 수 있다. 배트맨 혼자, 톰과 수지, 캘빈과 홉스와 제리로 묶으면 된다. 팀 두 개로는 안 되는데, 배트맨과 톰과 제리가 서로 싫어해서 셋을 모두 다른 팀에 넣어야 하기 때문이다. 팀 네 개도 답이 아니다. 더 적은 수가 가능하기 때문이다.

싫어하는 관계가 주어질 때, 팀 수가 최소인 편성을 구하라. 그런 편성이 여러 개면 출력 규칙에 따라 하나만 고른다.

첫째 줄에 선수 수 $n$과 서로 싫어하는 쌍의 수 $m$이 주어진다. ($1 \le n \le 15$, $0 \le m \le n(n-1)/2$) 선수는 $1$번부터 $n$번까지 번호가 붙어 있다.

다음 $m$개 줄에는 각각 서로 다른 두 정수 $a$와 $b$가 주어진다. ($1 \le a, b \le n$, $a \ne b$) 선수 $a$와 $b$가 서로를 싫어한다는 뜻이다. 같은 쌍이 두 번 주어지지는 않는다.

첫째 줄에 팀 수의 최솟값 $t$를 출력한다. 이어지는 $t$개 줄 중 $i$번째 줄에는 $i$번 팀에 속한 선수의 번호를 오름차순으로, 공백 하나로 구분해 출력한다.

조건을 만족하는 편성이 여러 개일 때는 다음 규칙으로 하나만 고른다. 선수 $i$가 들어간 팀의 번호를 $c_i$라고 할 때, 팀 수가 $t$인 모든 편성 중에서 수열 $(c_1, c_2, \ldots, c_n)$이 사전순으로 가장 앞서는 것을 출력한다. 이 규칙을 따르면 1번 선수는 항상 1번 팀에 들어가고, 팀 번호가 커질수록 그 팀에서 가장 작은 선수 번호도 커진다.