캘빈볼 챔피언십 팀 나누기

올해 캘빈볼 챔피언십이 체코에서 열린다. 한 경기에는 이름이 서로 다른 선수 $n$명이 참가하고, 선수는 여러 팀으로 나뉜다. 빈 팀은 없어야 하고, 각 선수는 정확히 한 팀에 속한다.

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

국제 캘빈볼 무질서 협회는 팀을 정하는 규칙을 마감 직전에 바꿨다. 서로 싫어하는 두 선수는 같은 팀에 들어갈 수 없고, 이 조건을 지키는 방법 중에서 팀 수가 가장 적어야 한다.

예를 들어 캘빈, 홉스, 수지, 톰, 제리, 배트맨이 경기에 참가하고 배트맨은 나머지 다섯 명을 모두 싫어하며 톰은 제리와 홉스를 싫어한다고 하자. 팀 세 개면 충분하다. 배트맨 혼자, 톰과 수지, 캘빈과 홉스와 제리로 나누면 된다. 팀 두 개로는 안 된다. 배트맨, 톰, 제리가 서로 싫어해서 세 팀이 필요하기 때문이다. 팀 네 개도 답이 아니다. 세 팀으로 이미 나눌 수 있기 때문이다.

팀 수가 최소인 나누기는 여러 가지일 수 있으므로 답을 하나로 정한다. 선수 $i$가 속한 팀의 번호를 $c_i$라고 할 때, 수열 $(c_1, c_2, \dots, c_n)$이 사전순으로 가장 앞서는 나누기를 출력한다. 팀 번호는 $1$부터 $t$까지 쓴다. 이 규칙을 따르면 팀은 속한 선수 번호의 최솟값이 작은 순서대로 나오고, 선수 $1$은 항상 팀 $1$에 속한다.

첫째 줄에 선수의 수 $n$과 서로 싫어하는 쌍의 수 $m$이 주어진다. ($1 \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$와 선수 $b_i$가 서로 싫어한다는 뜻이다. 같은 쌍이 두 번 주어지지 않는다.

첫째 줄에 팀 수의 최솟값 $t$를 출력한다. 다음 $t$개 줄 중 $i$번째 줄에는 팀 $i$에 속한 선수의 번호를 오름차순으로 공백 하나씩 띄워 출력한다.

팀 번호는 선수 $i$가 속한 팀의 번호를 $c_i$라고 할 때 수열 $(c_1, c_2, \dots, c_n)$이 사전순으로 가장 앞서도록 매긴다. 이 규칙을 지키면 답은 하나로 정해진다.