#include "stdio.h"
#include "stdlib.h"
#include "unistd.h"

#define MAX_VERTICES 256

char *edge1,*edge2;   // Edges we store in here
char *edges;   // NxN matrix :)

char vtex[MAX_VERTICES];  // vtex[i] = vertices available
char posn[MAX_VERTICES];  // posn[i] = where is vertex i?
char best[MAX_VERTICES];  // the best permutation so far
char used[MAX_VERTICES];  // tracks vertices used in the solution
char maxl[MAX_VERTICES];  // tracks max len of edge during backtracking
char rmap[MAX_VERTICES];  // used for dynamic randomizing
char larg[MAX_VERTICES];  // used to keep track of the first largest edge

int n; // number of vertices
int m; // number of edges

int minv;  // Smallest longest edge

int cnt=0;

int glug=0;
inline int max_edge() {
  int v=0, maxv=0, v1,v2;
  for (int i=0; i<m; i++) { 
    v1=edge1[i];
    v2=edge2[i];
    v = abs(posn[v2]-posn[v1]);
    if (v > maxv) { 
      maxv = v;
      glug=v1; if (random()%2) glug=v2;
    }
  }
  return maxv;
}

void find_sol(int level) {
  int nv, len, a, b, j, k;
  int i; 
  int t,w, flag, nv2;

  if (level==n) {
    int maxv=max_edge(); // maxl[level-1];
    if (maxv<minv) { 
      minv=maxv;
      for (int i=0; i<n; i++) best[i]=vtex[i];
      printf("Min is now: %d\n", minv);
    }

  } else {
    for (i=0; i<m; i++) {
      if (used[edge1[i]] && !used[edge2[i]]) 
        if (posn[edge1[i]] <= level-minv) return;
      if (!used[edge1[i]] && used[edge2[i]]) 
        if (posn[edge2[i]] <= level-minv) return;
    }
    for (int k=0; k<n; k++) {
      i=rmap[k];
      if (!used[i]) {
        used[i]=1;
        vtex[level]=i;
        posn[i]=level;

        find_sol(level+1);

        used[i]=0;
      }
    } // end of main for loop
  }
}
  
void main() {
  int i, j, v1, v2;

  fprintf(stderr, "Starting O(1) work...\n");

  scanf("%d", &n);   // Read initial data
  scanf("%d", &m);
  
  edge1 = (char *)malloc(m);  // Fix some space for edges
  edge2 = (char *)malloc(m);  // Fix some space for edges
  edges = (char *)malloc(256*n); // The adjacency matrix

  for (i=0; i<256*n; i++) edges[i]=0;

  int ecnt=0;
  for (i=0; i<m; i++) {        // Start reading edges
    scanf("%d %d", &v1, &v2);
    v1--; v2--;
    if (v1!=v2 && (v1>=0 && v1<n && v2>=0 && v2<n)) { // Loops don't matter
      edge1[ecnt]=v1;
      edge2[ecnt]=v2;
      ecnt++;
      edges[(v1<<8)+v2]=1;
      edges[(v2<<8)+v1]=1;
    }
  }
  m=ecnt;  

  for (i=0; i<n; i++) { // No vertices used up yet
    vtex[i]=i;
    used[i]=0;
    posn[i]=i;
    rmap[i]=i;
  }

  srandom(getpid()*1001);
  for (i=0; i<1000; i++) {
    v1 = random() % n;
    v2 = random() % n;
    j=rmap[v1]; rmap[v1]=rmap[v2]; rmap[v2]=j;
  }

  int om, nm, cnt;
  for (i=0; i<1000; i++) {
    v2 = random() % n;
    om = max_edge();
    v1=posn[glug];
    cnt=0;
    do {
      j=vtex[v1]; vtex[v1]=vtex[v2]; vtex[v2]=j;
      posn[vtex[v1]]=v1;
      posn[vtex[v2]]=v2;
      nm=max_edge();
      if (nm>om) {
	j=vtex[v1]; vtex[v1]=vtex[v2]; vtex[v2]=j;
	posn[vtex[v1]]=v1;
	posn[vtex[v2]]=v2;
      };
      cnt++;
      v2 = random() % n;
    } while (nm>=om && cnt<50);
  }
  minv = max_edge();
  for (i=0; i<n; i++) best[i]=vtex[i];
   
  for (i=0; i<n; i++) { // No vertices used up yet
    vtex[i]=i;
    used[i]=0;
    posn[i]=i;
    rmap[i]=i;
  }
    
  fprintf(stderr, "Starting O(f(n)) work...\n");

  printf("Good starting minimum: %d\n", minv);

  find_sol(0);  // here we go.

  fprintf(stderr, "Done.\n");  
  fprintf(stderr, "Solution: ");
  for (i=0; i<n; i++) fprintf(stderr, "%d ", best[i]+1);
  fprintf(stderr, "\n");
  
  fprintf(stderr, "Bandwidth: %d\n", minv);
  
}