칼빈볼 최소 팀 나누기

칼빈볼 세계 선수권 대회가 올해도 체코에서 열린다. 한 경기에는 이름이 서로 다른 n명의 선수가 참가하고, 선수는 비어 있지 않은 여러 팀으로 나뉜다. 일부 선수는 서로를 싫어한다. 싫어하는 관계는 대칭이다. 선수 a가 선수 b를 싫어하면 b도 a를 싫어한다.

국제 칼빈볼 비조직위원회는 팀 편성 규칙을 바꿨다. 서로 싫어하는 두 선수는 같은 팀에 들어갈 수 없고, 그 조건을 지키면서 팀의 수는 가능한 한 적어야 한다.

예를 들어 캘빈, 홉스, 수지, 톰, 제리, 배트맨이 경기에 나선다고 하자. 배트맨은 나머지 다섯 명을 모두 싫어하고, 톰은 제리와 홉스를 싫어한다. 이때 팀 세 개면 충분하다. 배트맨 혼자, 톰과 수지, 캘빈과 홉스와 제리로 나누면 된다. 팀 두 개로는 안 된다. 배트맨, 톰, 제리가 서로를 싫어하므로 셋은 서로 다른 팀에 들어가야 한다.

싫어하는 관계가 모두 주어질 때 규칙을 지키는 팀 편성을 구하라. 조건을 만족하는 편성이 여러 개일 수 있으므로, 그중 무엇을 출력할지는 출력 항목에서 정한다.

첫째 줄에 선수의 수 n과 서로 싫어하는 선수 쌍의 수 m이 공백으로 구분되어 주어진다 ($0 \le n \le 20$, $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개 줄에는 각 팀에 속한 선수의 번호를 오름차순으로 공백으로 구분해 출력한다.

팀 t개를 쓰는 편성이 여러 개이면 다음 규칙으로 하나를 고른다. 선수 v가 속한 팀의 번호를 $c_v$라고 하자. 팀을 t개로 나누는 편성 중에서 수열 $(c_1, c_2, \dots, c_n)$이 사전순으로 가장 앞서는 것을 출력한다. 이 규칙을 따르면 i번 팀에 속한 가장 작은 선수 번호가 i가 커질수록 커진다.

n이 0이면 첫째 줄에 0만 출력하고 팀 줄은 출력하지 않는다.