칼빈볼 선수권 대회 팀 편성

올해도 칼빈볼 선수권 대회가 열린다. 한 경기에는 이름이 서로 다른 선수 $n$명이 참가하고, 이 선수들을 비어 있지 않은 팀 여러 개로 나눈다. 팀의 개수에는 제한이 없다. 선수 중 일부는 서로 사이가 나쁘다. 사이가 나쁜 관계는 대칭이다. 선수 $a$가 선수 $b$와 사이가 나쁘면 $b$도 $a$와 사이가 나쁘다.

조직위원회는 팀을 짜는 규칙을 바꾸었다. 사이가 나쁜 두 선수는 같은 팀에 들어갈 수 없고, 이 조건을 지키면서 팀의 개수를 최소로 만들어야 한다.

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

사이가 나쁜 선수 쌍이 주어질 때, 규칙을 지키면서 선수를 팀으로 나누어라.

첫째 줄에 선수의 수 $n$과 사이가 나쁜 선수 쌍의 수 $m$이 공백을 사이에 두고 주어진다. ($0 \le n \le 12$, $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$가 속한 팀의 번호를 $t_i$라 하고, 팀 번호는 처음 등장하는 순서대로 $1$번부터 매긴다. 즉 $t_1 = 1$이고, 모든 $i$에 대해 $t_i \le 1 + \max(t_1, \dots, t_{i-1})$이다. 팀의 개수가 최소인 나누기 중에서 수열 $(t_1, t_2, \dots, t_n)$이 사전순으로 가장 앞서는 것을 출력한다. 팀은 $1$번 팀부터 $t$번 팀까지 순서대로 출력한다.

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