/* Simulated annealing for a graph (bi)partitioning problem
*/

#include <stdio.h>
#include<math.h>
#define RAND_MAX 2147483648.0




/* To perturb the given node to get the next node to explore */

int Perturb(max_node)
int max_node;
{

 static int gljdum=1;
        float ran3();
  int rand_node;

  rand_node = ran3(&gljdum)* max_node;
  return rand_node;

}

/* To take the decision .... Metropolis equation/ other equation */

int metrop(de,t)
float de,t;
{
	static int gljdum=1;
	float ran3();
	float k=0.02;
	/* printf("%f %f \n",exp(-de/(k*t)),de); */
	return de < 0.0 ||  ran3(&gljdum) < exp(-de/(k*t));
}


#define MBIG 1000000000
#define MSEED 161803398
#define MZ 0
#define FAC (1.0/MBIG)

float ran3(idum)
int *idum;
{
        static int inext,inextp;
        static long ma[56];
        static int iff=0;
        long mj,mk;
        int i,ii,k;

        if (*idum < 0 || iff == 0) {
                iff=1;
                mj=MSEED-(*idum < 0 ? -*idum : *idum);
                mj %= MBIG;
                ma[55]=mj;
                mk=1;
                for (i=1;i<=54;i++) {
                        ii=(21*i) % 55;
                        ma[ii]=mk;
                        mk=mj-mk;
                        if (mk < MZ) mk += MBIG;
                        mj=ma[ii];
                }
                for (k=1;k<=4;k++)
                        for (i=1;i<=55;i++) {
                                ma[i] -= ma[1+(i+30) % 55];
                                if (ma[i] < MZ) ma[i] += MBIG;
                        }
                inext=0;
                inextp=31;
                *idum=1;
        }
        if (++inext == 56) inext=1;
        if (++inextp == 56) inextp=1;
        mj=ma[inext]-ma[inextp];
        if (mj < MZ) mj += MBIG;
        ma[inext]=mj;
        return mj*FAC;
}

#undef MBIG
#undef MSEED
#undef MZ
#undef FAC



main() {
struct Con {
	int node1;
	int node2;
    }  con[18000];
int n1,n2,nodes,no_edges,i,j,k; 
int Bin[3000],temp_bin[3000];
int Bin1=0,Bin0=0,temp_bin1=0,temp_bin0=0;
int Diff, temp_diff,cut_edge=0,temp_cut_edge=0;
int it,in_loop,out_loop,Succ=0,Succ_index,equil,decision;
float T=500.0;
float alpha= 0.5;
float E1, E2, E_diff;
int best_cut_edge,best_Bin0,best_Bin1,best_Bin[3000];
float best_E1 = 100000.0;



	scanf("%d",&nodes);



  srand(400); /* random seed */



	scanf("%d",&no_edges);

	for (i=1;i<=no_edges;i++)
		scanf("%d %d",&con[i].node1,&con[i].node2);



	/* initialize the bin distribution */
	for (i=1;i<=nodes;i++)
 		if( rand()/RAND_MAX <=0.5) Bin[i]=0;
	     	else           Bin[i]=1;
        
	/* Calculate the # of edges cut */

     for (i=1;i<=no_edges;i++) {
		n1 = con[i].node1;
		n2 = con[i].node2;
		if (Bin[n1] != Bin[n2]) cut_edge++;
     }
           

	for (i=1;i<=nodes;i++)
		Bin1 = Bin1 + Bin[i];
	Bin0 = nodes - Bin1;

        Diff = Bin0- Bin1;

/* Calculate Energy at this point    */
	E1 = cut_edge + alpha * Diff * Diff ;
it =0;
Succ_index = 1;
for (out_loop = 1; T >2 && Succ <20; out_loop++) {
equil =0;
   for (in_loop =1; in_loop<= 100 && equil <10 && Succ <20;in_loop++) {
   it++;
   /* printf("%d\n",it); */

/* Select randomly one vertex .. place it in the 'other' bin */

        k = Perturb(nodes);

	for (i=1;i<=nodes;i++)
	  temp_bin[i] = Bin[i];

	temp_bin[k] = 1 - Bin[k];

	if (temp_bin[k] ==0)   {
	    temp_bin0 = Bin0 +1;
	    temp_bin1 = Bin1 -1;
	}
	else {
	    temp_bin1 = Bin1 +1;
	    temp_bin0 = Bin0 -1;
	}


	        /* Calculate the # of edges cut */

	temp_cut_edge =0;

        for (i=1;i<=no_edges;i++) {
			n1 = con[i].node1;
			n2 = con[i].node2;
                        if (temp_bin[n1] !=temp_bin[n2])   temp_cut_edge ++;
	}

	temp_diff = temp_bin0 - temp_bin1;
	E2 = temp_cut_edge + alpha * temp_diff * temp_diff;


       E_diff = E2 - E1;
       /* printf("E_diff = %f \n",E_diff); */
	decision = metrop(E_diff, T);  

        if (decision) {
		Bin[k]= temp_bin[k];
		Bin0 = temp_bin0;
		Bin1 = temp_bin1;
                E1 = E2;
		if (Succ_index ==1) Succ++;
		cut_edge = temp_cut_edge;
		if (E1 < best_E1) {
		  best_E1 = E1;
		  best_Bin0 = Bin0;
		  best_Bin1 = Bin1;
		  for (i=1;i<=nodes;i++)  best_Bin[i] = Bin[i];
		  best_cut_edge = cut_edge;
		}

	}
	else {
	    equil++;
	    Succ =0;
	    Succ_index =0;
	}
	if (((it) % 100) ==0)
		printf("%d %f \n",it,best_E1);
  /*
  printf(" Temp = %f  Bin0 = %d  Bin1 = %d  Edges cut = %d Energy = %f \n",T,Bin0,Bin1,cut_edge,E1);
  */
    }

    T = 0.98 * T;

  }


/*
	for (i=1;i<=nodes;i++) {
     for (j=1;j<=nodes;j++) {
        printf("%d ",con[i][j]);
        }
        printf("\n");
   }
  printf(" Temp = %f  Bin0 = %d  Bin1 = %d  Edges cut = %d  iter = %d Energy = %f \n\n\n\n\n",T,Bin0,Bin1,cut_edge,it,E1);
*/
  printf(" Temp = %f  best_Bin0 = %d  best_Bin1 = %d  best_Edges cut = %d  iter = %d best_Energy = %f \n",T,best_Bin0,best_Bin1,best_cut_edge,it,best_E1);

 }