캘빈볼 팀 나누기

캘빈볼 대회에 선수 $n$명이 참가한다. 선수는 $1$번부터 $n$번까지 번호로 구분하며, 모든 선수는 비어 있지 않은 팀 중 정확히 하나에 들어간다. 팀의 개수에는 제한이 없다.

선수 중에는 서로 싫어하는 쌍이 있다. 싫어하는 관계는 대칭이다. 선수 $a$가 선수 $b$를 싫어하면 $b$도 $a$를 싫어한다.

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

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

누가 누구를 싫어하는지 주어질 때, 규칙을 지키는 팀 편성을 구한다.

첫째 줄에 선수의 수 $n$과 서로 싫어하는 쌍의 수 $m$이 공백으로 구분되어 주어진다. ($0 \le n \le 14$, $0 \le m \le n(n-1)/2$)

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

첫째 줄에 팀 개수의 최솟값 $t$를 출력한다.

팀에는 $1$번부터 $t$번까지 번호를 붙인다. 이어지는 $t$개의 줄 중 $i$번째 줄에 $i$번 팀에 속한 선수의 번호를 오름차순으로, 공백 하나로 구분해 출력한다.

$t$개의 팀으로 나누는 방법이 여러 가지면 다음 기준으로 하나를 고른다. 선수 $i$가 속한 팀의 번호를 $c_i$라고 할 때, 수열 $(c_1, c_2, \ldots, c_n)$이 사전순으로 가장 앞서는 편성을 출력한다. 즉 팀의 개수를 최솟값 $t$로 유지하면서 $c_1$을 최대한 작게, 그다음 $c_2$를 최대한 작게, 이런 식으로 차례대로 정한다. 이 기준을 만족하는 편성은 하나뿐이다.

$n = 0$이면 첫째 줄에 $0$만 출력하고 끝낸다.