#include <iostream>

using namespace std;

// Definicja elementu listy sąsiedztwa

struct slistEl
{
  slistEl * next;                 // Następny element listy;
  int v;                          // Wierzchołek docelowy
};

int main()
{
  int n,m,i,u,v;
  slistEl **graf, *p, *r;
  int *CT;
  bool *C;

  cin >> n >> m;                  // Odczytujemy liczbę wierzchołków i krawędzi grafu

  graf = new slistEl * [n];       // Tablica list sąsiedztwa
  for(i = 0; i < n; i++) graf[i] = NULL;

  CT = new int [n];               // Tablica kolorów wierzchołków
  C  = new bool [n];              // Tablica dostępności kolorów

  // Odczytujemy krawędzie grafu

  for(i = 0; i < m; i++)
  {
    cin >> u >> v;                // Wierzchołki krawędzi
    p = new slistEl;              // Tworzymy element listy
    p->v = u;
    p->next = graf[v];            // Element dołączamy do listy sąsiadów v
    graf[v] = p;

    p = new slistEl;              // To samo dla krawędzi w drugą stronę
    p->v = v;
    p->next = graf[u];            // Element dołączamy do listy sąsiadów u
    graf[u] = p;
  }

  // Rozpoczynamy algorytm kolorowania grafu

  for(i = 1; i < n; i++) CT[i] = -1;

  CT[0] = 0;                      // Kolor pierwszego wierzchołka

  for(v = 1; v < n; v++)
  {
    for(i = 0; i < n; i++) C[i] = false;

    for(p = graf[v]; p; p = p->next) // Przeglądamy listę sąsiadów v
      if(CT[p->v] > - 1) C[CT[p->v]] = true; // Kolor u zaznaczamy jako zajęty

    for(i = 0; C[i]; i++);        // Szukamy wolnego koloru
    CT[v] = i;                    // Kolorujemy wierzchołek v
  }

  // Wyświetlamy wyniki

  cout << endl;
  for(v = 0; v < n; v++)
    cout << "vertex " << v << " has color " << CT[v] << endl;

  // Usuwamy tablice dynamiczne

  for(v = 0; v < n; v++)
  {
    p = graf[v];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }

  delete [] graf;
  delete [] CT;
  delete [] C;

  return 0;
}