#include <stdio.h>

#define MAXN 1000

int n,m;

int sousedi[MAXN][MAXN];
int degree[MAXN];
int dom[3];
int ndom;
int domcol[3];

int availcol[MAXN][2];
int navailcol[MAXN];
int ohodn[MAXN];

int fle[2*MAXN][2*MAXN];
int fledeg[2*MAXN];

int trina[] = {1,3,9};

int is_dom (int v, int curr_size)
{
  int i;

  for (i = 0; i < curr_size; i++)
    if (dom[i] == v)
      return 1;

  return 0;
}

int has_dom_nbr (int v, int curr_size)
{
  int i;

  if (is_dom (v, curr_size))
    return 1;

  for (i = 0; i < degree[v]; i++)
    if (is_dom (sousedi[v][i], curr_size))
      return 1;

  return 0;
}

int small_dom_set (int curr_size, int curv)
{
  int i, u, sds;

  if (curr_size > 3)
    return curr_size;

  for (; curv < n; curv++)
    {
      if (!has_dom_nbr (curv, curr_size))
	{
	  dom[curr_size] = curv;
	  sds = small_dom_set (curr_size + 1, curv + 1);
	  if (sds <= 3)
	    return sds;

	  for (i = 0; i < degree[curv]; i++)
	    {
	      u = sousedi[curv][i];
	      dom[curr_size] = u;
	      sds = small_dom_set (curr_size + 1, curv + 1);
	      if (sds <= 3)
		return sds;
	    }

	  return 4;
	}
    }

  return curr_size;
}

int domvcol (int v)
{
  int i;

  for (i = 0; i < ndom; i++)
    if (dom[i] == v)
      return domcol[i];

  return -1;
}

void
det_avail_col (int v)
{
  int allowed[3], i, dvc;

  dvc = domvcol (v);

  if (dvc >= 0)
    {
      allowed[0] = allowed[1] = allowed[2] = 0;
      allowed[dvc] = 1;
    }
  else
    allowed[0] = allowed[1] = allowed[2] = 1;

  for (i = 0; i < degree[v]; i++)
    {
      dvc = domvcol (sousedi[v][i]);
      if (dvc >= 0)
	allowed[dvc] = 0;
    }

  navailcol[v] = 0;
  for (i = 0; i < 3; i++)
    if (allowed[i])
      availcol[v][navailcol[v]++] = i;
}

void forbid (int u, int uval, int v, int vval)
{
  int f = 2 * u + uval, fop = 2 * u + 1 - uval;
  int t = 2 * v + vval, top = 2 * v + 1 - vval;

  fle[f][fledeg[f]++] = top;
  fle[t][fledeg[t]++] = fop;
}

void add_edge (int u, int v)
{
  int i, j;

  for (i = 0; i < navailcol[u]; i++)
    for (j = 0; j < navailcol[v]; j++)
      if (availcol[u][i] == availcol[v][j])
	forbid (u, i, v, j);
}

int contradict (int v, int val)
{
  if (ohodn[v] == -1)
    return 0;

  if (ohodn[v] == val
      || ohodn[v] == val - 3)
    return 0;

  return 1;
}

/* tpe == 1 -- nastavuj permanentni hodnoty (0/1)
   tpe == 0 -- nastavuj docasne hodnoty (-2/-3)
   tpe == -1 -- nastavuj -1  */

int extend (int vv, int tpe)
{
  int v = vv / 2;
  int val = vv % 2;
  int i;

  if (contradict (v, val))
    return 0;

  if (ohodn[v] >= 0)
    return 1;

  if (tpe == -1
      && ohodn[v] == -1)
    return 1;

  if (tpe == 0
      && ohodn[v] != -1)
    return 1;

  if (tpe == 1)
    ohodn[v] = val;
  else if (tpe == 0)
    ohodn[v] = val - 3;
  else
    ohodn[v] = -1;

  for (i = 0; i < fledeg[vv]; i++)
    if (!extend (fle[vv][i],tpe))
      return 0;

  return 1;
}

int ohodnot (void)
{
  int u;

  for (u = 0; u < n; u++)
    if (navailcol[u] == 1)
      ohodn[u] = 0;
    else
      ohodn[u] = -1;

  for (u = 0; u < n; u++)
    {
      int pass = extend (2 * u, 0);

      extend (2 * u, 2 * pass - 1);

      if (pass)
	continue;

      if (!extend (2 * u + 1, 1))
	return 0;
    }

  return 1;
}

int main(void)
{
  int i, j, u, v, c;

  while (1)
    {
      scanf ("%d %d", &n, &m);
      if (n == 0)
	return 0;

      for (i = 0; i < n; i++)
	degree[i] = 0;

      for (i = 0; i < m; i++)
	{
	  scanf ("%d %d", &u, &v);
	  sousedi[u][degree[u]++] = v;
	  sousedi[v][degree[v]++] = u;
	}

      ndom = small_dom_set (0, 0);
      if (ndom > 3)
	{
	  printf ("NEMA DM\n");
	  continue;
	}

      domcol[0] = 0;
      for (i = 0; i < trina[ndom - 1]; i++)
	{
	  c = i;
	  for (j = 1; j < ndom; j++)
	    {
	      domcol[j] = c % 3;
	      c /= 3;
	    }

	  for (u = 0; u < n; u++)
	    {
	      det_avail_col (u);
	      if (!navailcol[u])
		break;
	    }

	  if (u != n)
	    continue;

	  for (u = 0; u < 2 * n; u++)
	    fledeg[u] = 0;

	  for (u = 0; u < n; u++)
	    for (j = 0; j < degree[u]; j++)
	      {
		v = sousedi[u][j];
		if (u > v)
		  continue;

		add_edge (u, v);
	      }

	  if (!ohodnot ())
	    continue;

	  u = 0;
	  printf ("%d", availcol[u][ohodn[u]]);
	  for (u++; u < n; u++)
	    printf (" %d", availcol[u][ohodn[u]]);
	  printf ("\n");
	  break;
	}

      if (i == trina[ndom - 1])
	{
	  printf ("The agents cannot be split\n");
	  continue;
	}
    }
}