다시 열리는 캘빈볼 선수권 대회

올해도 캘빈볼 선수권 대회가 열린다. 한 경기에는 이름이 서로 다른 $n$명의 선수가 참가하고, 각 선수는 정확히 한 팀에 속하며 비어 있는 팀은 없다. 선수 중 일부는 서로 싫어한다. 싫어하는 관계는 대칭이라서 선수 $a$가 선수 $b$를 싫어하면 $b$도 $a$를 싫어한다.

조직위원회는 팀을 짜는 규칙을 바꿨다. 서로 싫어하는 두 선수는 같은 팀에 들어갈 수 없고, 이 조건을 지키면서 팀 수를 가장 적게 만들어야 한다.

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

조건을 만족하는 나눔은 여러 가지일 수 있으므로 그중 하나를 정해서 출력한다. 팀에 $1$번부터 $t$번까지 번호를 붙이고 선수 $i$가 속한 팀의 번호를 $c_i$라고 하자. 팀 수가 최소인 모든 나눔과 모든 번호 붙이기 가운데 수열 $(c_1, c_2, \dots, c_n)$이 사전순으로 가장 앞서는 것이 답이다. 두 수열은 값이 처음으로 달라지는 자리에서 더 작은 값을 가진 쪽이 사전순으로 앞선다. 이 규칙을 따르면 선수 $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 \ne b_i$) 선수 $a_i$와 선수 $b_i$가 서로 싫어한다는 뜻이다. 같은 쌍이 순서를 바꾼 형태까지 포함해 두 번 이상 주어지는 경우는 없다.

첫째 줄에 팀 수의 최솟값 $t$를 출력한다. 다음 $t$개의 줄 중 $i$번째 줄에는 $i$번 팀에 속한 선수의 번호를 오름차순으로 공백 하나씩 두고 출력한다. 팀 번호는 문제에서 정한 사전순으로 가장 앞서는 방식을 따라야 한다.