/* Program solving the Bilboard problem, IPSC 99 */
/* reads input from file a.txt */

#include <stdio.h>
#include <stdlib.h>
extern unsigned _stklen = 543210U;  //needed for the Borland compiler
FILE *f;


typedef struct EDGE{
    int node;
    struct EDGE* next;
  } list;

list *(edge[700]);  //array containing list of edges for each node
int color[700];
 /* color[i] is color of node i (color is 1,2 or 3),
    color[i]=0 no color is assigned to i */

int depth[700];
  /* depth[i] is the depth of recursion
              in which color was assigned to node i */

int options[700][4];
  /* options[i][0] is number of color still available for node i
     options[i][c] is 0 if color c is still an option for node i
                    otherwise it is depth of recursion in which
                    this option was removed */

int n;           //number of nodes
int found;       //whether there was found a solution

void addEdge(int i, int j)
{
//adds edge ending in j to the list of edges going from node i

   list *l;

   l = (list*) malloc (sizeof (list));
   if (l == NULL) printf ("not enough memory\n");
   l -> node = j;
   l -> next = edge[i];
   edge[i] = l;
}

void read_block(void)
{
//reads description of one graph

   int i, j, k, m;

   fscanf (f, "%d %d", &n, &m);
   for (i = 0; i < n; i++) edge[i] = NULL;

   for (i = 0; i < m; i++){  //read edges
     fscanf (f, "%d %d", &j, &k);
     addEdge (j - 1, k - 1);
     addEdge (k - 1, j - 1);
   }
}

void undo (int atDepth)
{
/* procedure undoes all changes done to arrays color, depth and options
   that were done in depth atDepth or later */

  int i, j;

  for (i = 0; i < n; i++){
    if (depth[i] >= atDepth){
      depth[i] = -1;
      color[i] = 0;
    }
    for (j = 1; j <= 3; j++){
      if (options[i][j] >= atDepth){
        options[i][j] = 0;
        options[i][0]++;
      }
    }  //for j
  } //for i
}


void updateOptions (int node, int newColor, int atDepth)
{
//removes color newColor from options of all neighbours of node

  list *p;

  for (p = edge[node]; p != NULL; p = p->next){
    //p->node is a nieghbour of node

    if (color[p->node] == 0 && options[p->node][newColor] == 0){
      //if it does not have assigned color and newColor is among options

      options[p->node][newColor] = atDepth;  //remove this option
      options[p->node][0]--;             //decrease the number of options
    }
  }
}

int find_minimum (void)
{
//founds a node with minimum number of options
  int min, i;

  min = -1;
  for (i = 0; i < n; i++){
    if (color[i] == 0){
      if (min == -1) min = i;
      if (options[min][0]>options[i][0]) min = i;
    }
  }
  return min;
}

void backtrack (int node, int newColor, int atDepth)
{
//takes node, assignes color newColor to this node
//removes this option from all its neigbours and
//tryes to color another node resursively

  int i, min;

  color[node] = newColor;   //assign color
  depth[node] = atDepth;

  updateOptions (node, newColor, atDepth);

  if (atDepth == n){  //if all colors are assigned, we have a solution
    found = 1;
    return;
  }

  min = find_minimum ();
    //continue with a node with smallest number of colors

  for (i = 1; i <= 3; i++){
    if (options[min][i] == 0){
      backtrack (min, i, atDepth+1);
      if (found) return;
    }
  }

  undo (atDepth);   //undo changes

}

void writeSolution (void)
{
   int i;

   if (!found)
     printf ("-1\n");
   else{
     for (i = 0; i < n; i++)
       printf ("%d ", color[i]);
     printf ("\n");
   }
}


void main (void)
{
   int block, blocks;
   int i;

   f = fopen ("a.txt", "r");
   fscanf (f, "%d", &blocks);  //number of data blocks in input

   for (block = 0; block < blocks; block++){

     read_block ();

     for (i = 0; i < n; i++){
       color[i] = 0; depth[i] = 0;
       options[i][1] = options[i][2] = options[i][3] = 0;
       options[i][0] = 3;
     }
     found = 0;

     backtrack (0, 1, 1);
     writeSolution ();
  }
}