#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <queue>
using namespace std;
#define MAX_N	500


int N, M;
bool relations[MAX_N][MAX_N];
int relcounts[MAX_N];
unsigned long long masks[MAX_N][8];
int B[3];
int results[MAX_N];
int cache[MAX_N];
int cachecount;


bool find_badguy()
{
	unsigned long long tmp[8];
	memset(tmp, 0xff, sizeof(tmp));

	for (int i = 0; i < N; ++i) {
		int x = i / 64;
		int y = i % 64;
		tmp[x] &= ~(1ULL << y);
	}

	for (int i = 0; i < N; ++i) {
		unsigned long long tmp1[8];
		memcpy(tmp1, tmp, 8 * sizeof(unsigned long long));

		for (int j = 0; j < 8; ++j) {
			tmp1[j] |= masks[i][j];
		}
		int c1 = relcounts[i];

		int x = i / 64;
		int y = i % 64;
		tmp1[x] |= (1ULL << y);

		for (int j = i + 1; j < N; ++j) {
			unsigned long long tmp2[8];
			memcpy(tmp2, tmp1, 8 * sizeof(unsigned long long));

			for (int k = 0; k < 8; ++k) {
				tmp2[k] |= masks[j][k];
			}
			int c2 = c1 + relcounts[j];

			int x = j / 64;
			int y = j % 64;
			tmp2[x] |= (1ULL << y);

			for (int k = j + 1; k < N; ++k) {
				if (c1 + c2 + relcounts[k] < N - 3) continue;

				unsigned long long tmp3[8];
				memcpy(tmp3, tmp2, 8 * sizeof(unsigned long long));

				for (int l = 0; l < 8; ++l) {
					tmp3[l] |= masks[k][l];
				}

				int x = k / 64;
				int y = k % 64;
				tmp3[x] |= (1ULL << y);

				bool ok = true;
				for (int l = 0; l < 8; ++l) {
					if (tmp3[l] != 0xffffffffffffffffULL) {
						ok = false;
						break;
					}
				}
				if (ok) {
					B[0] = i;
					B[1] = j;
					B[2] = k;
					return true;
				}
			}
		}
	}
	return false;
}


bool init()
{
	memset(masks, 0, sizeof(masks));
	memset(relcounts, 0, sizeof(relcounts));

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (relations[i][j]) {
				int x = j / 64;
				int y = j % 64;
				masks[i][x] |= (1ULL << y);
				relcounts[i]++;
			}
		}
	}

	bool ret = find_badguy();
	if (!ret) return false;

	return true;
}


bool calc(int idx, int sel)
{
	if (results[idx]) {
		return results[idx] == sel;
	}
	results[idx] = sel;
	cache[cachecount++] = idx;

	for (int i = 0; i < N; ++i) {
		if (!relations[idx][i]) continue;
		if (i == B[0] || i == B[1] || i == B[2]) continue;

		bool flags[4];
		memset(flags, 0, sizeof(flags));
		for (int j = 0; j < 3; ++j) {
			if (relations[i][B[j]]) {
				flags[results[B[j]]] = true;
			}
		}
		flags[sel] = true;

		int count = 0, sel2 = -1;
		for (int j = 1; j <= 3; ++j) {
			if (!flags[j]) {
				++count;
				sel2 = j;
			}
		}
		if (count == 0) return false;
		if (count > 1) continue;
		if (!calc(i, sel2)) return false;
	}
	return true;
}


bool calc(int b0, int b1, int b2)
{
	if (b0 == b1 && relations[B[0]][B[1]]) return false;
	if (b0 == b2 && relations[B[0]][B[2]]) return false;
	if (b1 == b2 && relations[B[1]][B[2]]) return false;

	memset(results, 0, sizeof(results));
	results[B[0]] = b0;
	results[B[1]] = b1;
	results[B[2]] = b2;

	for (int i = 0; i < N; ++i) {
		if (results[i]) continue;

		bool flags[4];
		memset(flags, 0, sizeof(flags));
		for (int j = 0; j < 3; ++j) {
			if (relations[i][B[j]]) {
				flags[results[B[j]]] = true;
			}
		}

		bool ok = false;
		for (int j = 1; j <= 3; ++j) {
			if (!flags[j]) {
				cachecount = 0;
				if (calc(i, j)) {
					ok = true;
					break;
				}
				for (int k = 0; k < cachecount; ++k) {
					results[cache[k]] = 0;
				}
			}
		}
		if (!ok) return false;
	}
	return true;
}


bool calc()
{
	if (calc(1, 1, 1)) return true;
	if (calc(2, 1, 1)) return true;
	if (calc(1, 2, 1)) return true;
	if (calc(1, 1, 2)) return true;
	if (calc(1, 2, 3)) return true;
	return false;
}


int main()
{
	while (true) {
		scanf_s("%d %d", &N, &M);
		if (!N && !M) break;
		while (N < 1 || N > MAX_N) printf("...");

		memset(relations, 0, sizeof(relations));
		for (int i = 0; i < M; ++i) {
			int x, y; scanf_s("%d %d", &x, &y);
			while (x == y || x < 0 || x >= N || y < 0 || y >= N) printf("...");
			relations[x][y] = relations[y][x] = true;
		}

		if (N <= 3) {
			for (int i = 0; i < N; ++i) {
				printf("%d ", i);
			}
			printf("\n");
		}
		else {
			init();
			if (!calc()) {
				printf("The agents cannot be split\n");
			}
			else {
				for (int i = 0; i < N; ++i) {
					printf("%d ", results[i] - 1);
				}
				printf("\n");
			}
		}
	}
    return 0;
}