#include <cstdio>
#include <list>
#include <vector>

using namespace std;

int N, M;
// Graf reprezentovaný zoznamom následníkov
vector<vector<int> > graph;
// Pole stupňov vrcholov
vector<int> deg;
// Chlieviky na vrcholy s rovnakým stupňom
vector<list<int> > deg_box;
// Pointer pre kaźdý vrchol do nejakého chlieviku
vector<list<int>::iterator > deg_box_ptrs;

int main()
{
  // Najprv načítame vstup
  scanf("%d%d", &N, &M);

  // Predpokladám číslovanie vrcholov od 0 do N-1
  graph.resize(N);
  deg.resize(N, 0);
  deg_box.resize(N);
  deg_box_ptrs.resize(N);

  for (int i = 0; i < M; i++) {
    int u, v;

    scanf("%d%d", &u, &v);

    graph[u].push_back(v);
    graph[v].push_back(u);
    deg[u]++;
    deg[v]++;
  }

  for (int i = 0; i < N; i++) {
    // Rozmiestnime vrcholy do chlievikov podľa stupňa
    deg_box[deg[i]].push_front(i);
    // Zapamätáme si, kde sa ktorý vrchol nachádza
    deg_box_ptrs[i] = deg_box[deg[i]].begin();
  }

  for (int k = 0; k < N; k++)
    // Spracujeme chliev s číslom k
    while (!deg_box[k].empty()) {
      // Odoberieme z chlievu vrchol ...
      int v = *(deg_box[k].begin());
      deg_box[k].pop_front();

      // ... a každého jeho suseda presunieme do správneho chlieva
      for (int i = 0; i < graph[v].size(); i++)
        // Presúvame len vrcholy s väčším stupňom
        if (deg[graph[v][i]] > deg[v]) {
          // Presum
          deg_box[deg[graph[v][i]]].erase(deg_box_ptrs[graph[v][i]]);
          deg_box[--deg[graph[v][i]]].push_front(graph[v][i]);
          deg_box_ptrs[graph[v][i]] = deg_box[deg[graph[v][i]]].begin();
        }

      printf("Pre turistu s cislom %d je hladane k rovne %d.\n", v, k);
    }

  return 0;
}