캘빈볼 팀 나누기

올해도 캘빈볼 선수권 대회가 열린다. 캘빈볼 한 경기에는 이름이 서로 다른 선수 $n$명이 참가하고, 선수를 비어 있지 않은 팀 몇 개로 나눠서 진행한다. 선수 중에는 서로 싫어하는 사이가 있다. 싫어하는 사이는 대칭이다. 선수 $a$가 선수 $b$를 싫어하면 $b$도 $a$를 싫어한다.

국제 캘빈볼 무질서 협회는 대회 직전에 팀 편성 규칙을 바꿨다. 서로 싫어하는 두 선수는 같은 팀에 들어갈 수 없고, 이 조건을 지키면서 팀의 개수를 최소로 만들어야 한다.

예를 들어 캘빈(1번), 홉스(2번), 수지(3번), 톰(4번), 제리(5번), 배트맨(6번)이 경기에 참가하고, 배트맨은 나머지 다섯 명을 모두 싫어하며 톰은 제리와 홉스를 싫어한다고 하자. 배트맨과 톰과 제리는 셋이 서로 싫어하니 모두 다른 팀에 들어가야 하고, 그래서 두 팀으로는 나눌 수 없다. 세 팀으로는 나눌 수 있다. 캘빈과 홉스와 수지와 제리가 한 팀, 톰 혼자 한 팀, 배트맨 혼자 한 팀이면 규칙을 지킨다. 네 팀은 답이 아니다. 더 적은 개수로 나눌 수 있기 때문이다.

누가 누구를 싫어하는지 주어질 때, 팀의 개수가 최소인 편성을 구하는 프로그램을 작성하시오. 그런 편성이 여러 가지면 아래 출력 규칙이 정하는 하나를 출력한다.

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

다음 $m$개 줄에는 서로 싫어하는 두 선수의 번호 $a_i$와 $b_i$가 주어진다. ($1 \le a_i, b_i \le n$, $a_i \ne b_i$) 같은 쌍이 두 번 주어지는 일은 없다. 순서만 다른 두 줄도 같은 쌍으로 친다.

첫째 줄에 팀의 최소 개수 $t$를 출력한다. 다음 $t$개 줄에는 각 팀에 속한 선수의 번호를 공백으로 구분해 출력한다.

각 팀의 선수 번호는 증가하는 순서로 출력하고, 팀은 그 팀에서 가장 작은 선수 번호가 작은 것부터 출력한다. 팀 개수가 최소인 편성이 여러 가지면 다음 규칙으로 하나를 고른다. 출력하는 순서대로 팀에 $1$번부터 $t$번까지 번호를 붙이고, 선수 $i$가 속한 팀의 번호를 $c_i$라고 하자. 수열 $c_1, c_2, \dots, c_n$이 사전순으로 가장 앞서는 편성을 출력한다.

$n = 0$이면 첫째 줄에 $0$만 출력한다.