#include<stdio.h>
#include<algorithm>
using namespace std;
#define MN 1001
#define ME (MN*MN)

int N,K;
#define KK ((1<<K)-1)
int R[MN][MN];
int deg[MN], delQ[MN], dq0,dq1;
int V[MN], E[ME], A[MN], nv, ne;
int C0[MN], C[MN], mx;

void dump() {
	int i,j;
	for(i=0;i<nv;i++) C[V[i]]=C0[i];
	while(dq1) {
		int y,x=delQ[--dq1], X=KK;
		for(y=1;y<=N;y++) if(R[x][y]) X&=~C[y];
		for(j=1;j<=X;j<<=1) if(X&j) break;
		C[x]=j;
	}
	for(i=1;i<=N;i++) printf("%d,",C[i]);printf("\n");
}		

void recurse(int i) {
	if(i>mx) { mx=i; printf("colored %d of %d\n",i,nv); }
	if(i==nv) { dump(); exit(0); }
	int j,X=0;
	for(j=A[i];j<A[i+1];j++) X|=C0[E[j]];
	X^=KK;
	for(j=1;j<=X;j<<=1) if(X&j) { C0[i]=j; recurse(i+1); }
}

bool comp(const int x, const int y)  {
	return deg[x]!=deg[y] ? deg[x]>deg[y] : x > y;
}

int main(int ac, char** av) {
	N=(ac>1)?atoi(av[1]):100;
	K=(ac>2)?atoi(av[2]):3;

	int i,j,x,y,s,p;
	for(x=3;x<=N;x++) R[x-1][x]=R[x][x-1]=1;
	for(x=2;x<=N;x++)for(s=x+2,p=2*x;s<2*x&&p<=N;p+=x,s++) R[s][p]=R[p][s]=1;

	for(x=1;x<=N;x++) {
		for(y=1;y<=N;y++) deg[x]+=R[x][y];
		if(deg[x] < K) delQ[dq1++]=x;
	}
	while(dq0<dq1) {
		x=delQ[dq0++];
		for(y=1;y<=N;y++) if(R[x][y]==1) {
			if(deg[y]==K) delQ[dq1++]=y;
			deg[y]--; deg[x]--;
			R[x][y]=R[y][x]=2;
		}
	}

	printf("%d-coloring [1,%d]...\n",K,N);
	printf("deleted %d vertices\n",dq1);
	for(x=1;x<=N;x++) if(deg[x]) V[nv++]=x;
	sort(V,V+nv,comp);
	for(i=0;i<nv;i++) {
		int x=V[i], p=A[i];
		for(j=0;j<i;j++) if(R[x][V[j]]) E[p++]=j;
		A[i+1]=p;
	}
	recurse(0);
	printf("failed\n");
}