#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){
	/* transforma datele de intrere ale problemei "Salavre" in cele ale problemei "Cabane" */
	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){
	/* Functie ce se bazeaza pe algoritm de tip GREEDY 
	 * Se incearca amplasarea unui nr. de posturi de prim ajutor (<=m)
	 * care sa se afle la distanta maxima dm fata de frunze 
	 */
	TLista nc;
	int p,u,i,k,nr;  
	int *a, *b, *q, *g;
	char *w;
	/* g - grade noduri
	 * q - coada noduri
	 * p - primul din coada (elementul de prelucrat)
	 * u - ultimul din coada (marimea cozii)
	 * w - ne spune statutul nodurilor (vizitate sa nu)
	 * dm - distanta de la frunza la punct de prim ajutor
	 */

     /* alocari memorie */
     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;
     }
     /* initializari */
     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;
     /* algoritm */
     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;  
     }
     /* eliberare memorie */
     free(a);
     free(b);
     free(q);
     free(g);
     free(w);
     return nr;  
}

int main(){
	/* variabile */
	int n, m, i, dmin, dmax, dmed, nr;
	int *g;
	char *s, *ss;
	FILE *f;
	char fin[15] = "salvare.in", fout[15] = "salvare.out";
	TLista *v, np, nc;
	/* n - nr. cabane
	 * m - nr. puncte prim ajutor ce trebuie deschise
	 * v - lista vecini pt. ficare nod
	 * g - vector grade noduri
	 * s - noduri selectate pt. puncte prim ajutor
	 */
	/* citire dtae */
	f = fopen(fin, "rt");
	if (!f){
		printf("Eroare fisier intrare!\n");
		return -1;
	}
	fscanf(f, "%i %i", &n, &m);
	/* alocari */
	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;
	}
	
	/* ======= Citire pt Salvare ==== */
	if (transfx(f, v, g, n, m)){
		printf("Eroare transformare date!\n");
	}
	/* citire date */
	/*
	for (i=0; i<n; i++){
		s [i] = 0;//nu e marcat
		fscanf(f, "%i", g+i);
		v[i] = NULL; //initial
		for (j=0; j<g[i]; j++){
			nc = (TLista)malloc(sizeof(TNod));
			if (!nc){
				printf("Eroare alocare!\n");
				return -3;
			}
			fscanf(f,"%i", &(nc->x));
			nc->x--;	//adaptare notatie
			nc->urm = NULL;
			if (j==0){
				np = nc;
				v[i] = nc;
			}
			else{
				np->urm = nc;
				np = nc;
			}
		}
	}
	fclose(f);
	*/
	
	/* Verificare citire 
	for (i=0; i<n; i++){
		np = v[i];
		while(np!=NULL){
			printf("%i ", np->x+1);
			np = np->urm;
		}
		printf("g=%i \n",g[i]);
	}
	*/
	
	/* === Varianta iterativa de cautare O(n) === */
	
	for (dmed=0; dmed<n-1; dmed++){
		for(i=0;i<n;i++) s[i]=0;
		nr = alegex(n, dmed, v, g, s);
		if (nr<0) return -1;		// eroare alocari
		if (nr<=m)
			break;
	}
	
	/* completare solutie */
	i=0;
	while(nr<m){
		if (s[i]!=1){
			s[i]=1;
			nr++;
		}
		i++;
	}
	
	/* afisare date */
	f = fopen(fout, "wt");
	fprintf(f, "%i\n", dmed);
	for (i=0; i<n; i++){
		if (s[i])
			fprintf(f, "%i ", i+1);
	}
	fprintf(f,"\n");
	fclose(f);
	/* eliberare memorie */
	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;
}