// 
// Hi, here is my program. 
// 
// It's randomized; so with a little luck it will swallow up to 25 or 26,
// although it usually takes a couple of tries to get a fast search going.
// It mostly depends on a good starting minimum.
// 
// Basically, I've seen it do more on g-t-?? type graphs, little less on
// binary trees, and least on grid-graphs. I didn't optimize paths.
// 
// So I guess I'll settle for about 24 vertices within a minute, since 
// that's kinda the worst case (a grid graph g-gg-24-38) among 24 vertex
// graphs. 
// 
// You probably have a machine with a nice pipelined CPU so make sure you
// compile it using
// 
  // g++ -O3 -o novo novo.c
// 
// That should optimize it out some. 
// 
// 
// Regards, 
// 
// Dario Vlah
// -----------
// 
// Here goes the program:
// 
// -----------------------------------------------------------------------------
// **********************************************************************
// The CSE 373 assignment #3
// Due 3/19
// **********************************************************************
// 3/5 - Version 1.0. (novo.c)  Another approach
// 3/8 - Version 1.2. no more max_edge, I keep track of the max edge as I
//       raise the recursion level
//     - No need for green anymore... I just check edges formed by adding
//       the new vertex, and see if they are all smaller than the smallest
//       maximum yet. That's fast thanks to the adjacency matrix
//     - Try randomizing now.
//     - Pretty much done for now, will spawn a new file and try 
//       attempting new vertices in sorted order... if that can offset the
//       cost of sorting, that'd be cool
//3/12 - Unfortunately, the greedy sorting approach doesn't work too well.
//       Doesn't find a good minv, and even if it did, wouldn't help much.
//3/14 - How about randomizing only if it improves the edge length?
//     - This approach really paid off. I take one of the vertices in the
//       current max edge, and another random vertex, and swap them; but
//       only if the max edge length doesn't increase. If it stays the
//       same, I swap; that might lead to improvement later. I do this in
//       a 1000-cycle loop in the way that I vertices as described until
//       the max length improves, or until I do it a 50 times without
//       getting improvement, so that the loop doesn't deadlock. Now
//       I need a better pruning approach. 
//3/18 - New pruning approach: go through all the vertices not in the 
//       partial permutation yet, and if even one of them makes a long
//       enough edge with something in the partial permutation, stop 
//       the search in that direction, as nothing less than that edge
//       can be found. 
// **********************************************************************

#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);
  
}