#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 100001
#define min(a,b) ((a)<(b)?(a):(b))  

typedef struct nod
{
	int x;
	struct nod * urm;
}TNod, *TLista;

int transfx(FILE *f, TLista *v, int *g, int n, int m){
	TLista nc, np;
	int i,j,k;
	for (i=0;i<n;i++){
		g[i]=0;
		v[i]=NULL;
	}
	
	for (k=0; k<n-1; k++){
		fscanf(f, "%i %i", &i, &j);
		i--;
		j--;
		g[i]++;
		g[j]++;
		nc = (TLista)malloc(sizeof(TNod));
		if (!nc)
			return -1;
		nc->x = j;
		if (v[i]==NULL) {nc->urm=NULL; v[i]=nc;} 
		else{
			np = v[i];
			while (np->urm!=NULL && j>np->x) np=np->urm;
			nc->urm=np->urm;
			np->urm=nc;
		}
		
		nc = (TLista)malloc(sizeof(TNod));
		if (!nc)
			return -1;
		nc->x = i;
		if (v[j]==NULL) {nc->urm=NULL; v[j]=nc;} 
		else{
			np = v[j];
		    while (np->urm!=NULL && i>np->x) np=np->urm;
			nc->urm=np->urm;
			np->urm=nc;
		}
	}
	fclose(f);
	return 0;
}

int alegex(int n, int dm, TLista *v, int *gg, char *s){
	TLista nc;
	int p,u,i,k,nr;  
	int *a, *b, *q, *g;
	char *w;
     a = (int *)malloc(n*sizeof(int));
     b = (int *)malloc(n*sizeof(int));
     q = (int *)malloc(n*sizeof(int));
     g = (int *)malloc(n*sizeof(int));
     w = (char *)malloc(n);
     if (!a || !b || !q || !g || !w){
    	 free(a);
    	 free(b);
    	 free(q);
    	 free(g);
    	 free(w);
    	 return -2;
     }
     p = 0; u = -1;
     for(i=0;i<n;i++)  
     {  
         w[i]=0; 
         a[i]=dm; 
         b[i]=n; 
         g[i]=gg[i];  
         if(g[i]<2)  
             q[++u]=i;  
     }  
     nr = 0;
     while(p<=u)  
     {  
         k=q[p++];  
         if(a[k]<b[k] && (!a[k] || !g[k])){  
             b[k]=0;s[k]=1;nr++;}
         for (nc=v[k]; nc!=NULL; nc=nc->urm){
        	 i = nc->x;
             if(!w[i])  
             {  
                 if(a[k]<b[k])a[i]=min(a[i],a[k]-1);  
                 else  b[i]=min(b[i],b[k]+1);  
                 g[i]--;  
                 if(g[i]==1)q[++u]=i;  
             }  
         }
         w[k]=1;  
     }
     free(a);free(b);free(q);free(g);free(w);
     return nr;  
}

int main(){
	int n, m, i, dmin, dmax, dmed, nr, ddmin, nrmin;
	int *g;
	char *s, *ss;
	FILE *f;
	char fin[15] = "salvare.in", fout[15] = "salvare.out";
	TLista *v, np, nc;
	
	f = fopen(fin, "rt");
	if (!f){
		printf("Eroare fisier intrare!\n");return -1;
	}
	fscanf(f, "%i %i", &n, &m);
	v = (TLista *)malloc(n*sizeof(TLista));
	g = (int *)malloc(n*sizeof(int));
	s = (char *)malloc(n);
	ss = (char *)malloc(n);
	if (!v || !g || !s || !ss){
		free(s);
		free(v);
		free(g);
		free(ss);
		printf("Eroare alocare!\n");
		return -2;
	}
	if (transfx(f, v, g, n, m)){
		printf("Eroare transformare date!\n");
	}
	/* === Varianta cauta binara O(lgn) === */
	dmin = 0; 
	dmax = n-1;
	ddmin = INF;
	nrmin = INF;
	while(dmin<=dmax){ 
		dmed=(dmin+dmax)/2;
		for(i=0;i<n;i++) s[i]=0;
		nr = alegex(n, dmed, v, g, s);
		if (nr<=m){ 
			dmax=dmed-1;
			if (ddmin>dmed){
				ddmin = dmed;
				nrmin = nr;
				memcpy(ss, s, n);
			}
		}
		else 
			dmin=dmed+1; 
	}
	memcpy(s, ss, n);
	i=0;
	while(nr<m){
		if (s[i]!=1){s[i]=1;nr++;
		}
		i++;
	}
	f = fopen(fout, "wt");
	fprintf(f, "%i\n", ddmin);
	for (i=0; i<n; i++){
		if (s[i])
			fprintf(f, "%i ", i+1);
	}
	fprintf(f,"\n");	fclose(f);

	for (i=0; i<n; i++){
		np = v[i];
		while (np!=NULL){
			nc = np;
			np = np->urm;
			free(nc);
		}
	}
	free(v);
	free(g);
	free(s);
	return 0;
}