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

#define INF 100001

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

void parcDF(TLista *v, int i, int nv, int *z){
	TLista nc = v[i];
	if (nv==0) return;
	while(nc!=NULL){
		//if (z[nc->x]==0){
			z[nc->x]=1;
			parcDF(v, nc->x, nv-1, z);
		//}
		nc=nc->urm;
	}
	
}
int verif(TLista *v, int dm, char *s, int n){
	int i, *z;
	z = (int*)malloc(n);
	if (!z){
		return -1;
	}
	for (i=0; i<n; i++) z[i]=0;
	for (i=0; i<n; i++){
		if (s[i]==1){
			z[i]=1;
			parcDF(v, i, dm, z);
		}
	}
	for (i=0; i<n; i++){
		if (z[i]==0){
			free(z);
			return 0;
		}
	}
	free(z);
	return 1;
}


int transf(FILE *f, TLista *v, int *g, int n, int m){
	/* transforma datele de intrere ale problemei "Salavre" in cele ale problemei "Cabane" */
	TLista nc;
	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;
		nc->urm = v[i];
		v[i]=nc;
		
		nc = (TLista)malloc(sizeof(TNod));
		if (!nc)
			return -1;
		nc->x = i;
		nc->urm=v[j];
		v[j]=nc;
	}
	fclose(f);
	return 0;
}

int alege(int dm, int n, int m, 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 
	 */
	int i, k, p, u, nr;
	int *g, *q, *d;
	char *w;
	TLista nc;
	/* 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 */
	g = (int *)malloc(n*sizeof(int));
	if (!g){
		printf("Eroare alocare!\n");
		return -2;
	}
	d = (int *)malloc(n*sizeof(int));
	if (!d){
		free(g);
		printf("Eroare alocare!\n");
		return -2;
	}
	q = (int *)malloc(n*sizeof(int));
	if (!q){
		free(d);
		free(g);
		printf("Eroare alocare!\n");
		return -2;
	}
	w = (char *)malloc(n);
	if (!q){
		free(d);
		free(g);
		free(q);
		printf("Eroare alocare!\n");
		return -2;
	}
	
	/* se creaza o copie a gradurilor nodurilor */
	memcpy(g, gg, n*sizeof(int));
	/* se initializeaza distantele de la frunze la puncte cu o valoare f. mare */
	for (i=0; i<n; i++){
		d[i] = INF;
		w[i] = 0;
	}
	/* se introduc frunzele in coada si se actualizeaza distanta lor cu dm */
	p = 0;
	u = -1;
	for (i=0; i<n; i++)
		if (g[i]==1){
			u++;
			q[u] = i;
			d[i] = dm;
			w[i] = 1;	// bagat in coada
		}
	/* se introduc restul de noduri in coada => u<n */
	nr = 0;
	while (u<n-1){
		/* se va prelua elementul curent si se vor scade gradele vecinilor */
		k = q[p];
		p++;
		nc = v[k];	// lista vecini
		while (nc!=NULL){
			if (!w[nc->x]){ // daca nu e bagat deja
				i = nc->x;
				break;
			}
			else
				nc=nc->urm;
		}
		/* scad grad */
		g[k]--;
		g[i]--;
		/* se actualizeaza distantele */
		if (d[k]<d[i])
			d[i]=d[k];
		/* se poate introduce in coada ? */
		if (g[i]==1){
			/* actualizez distanta */
			if (d[i]>0) d[i]--;
			/* poate fi punct de prim ajutor ? */
			if (d[i]==0){
				/* am gasit punct de prim ajutor =>
				 * il numaram si il marcam 
				 */
				nr ++;
				s[i]=1;
				d[i]=2*dm;//+1;
			}
			u++;
			q[u]=i;
			w[i] = 1;
		}
	}
	/* eliberari memorie */
	free(g);
	free(d);
	free(q);
	free(w);
	return nr;
}
int main(){
	/* variabile */
	int n, m, i, dmin, dmax, dmed, nr, min;
	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 date - deschidere fisier*/
	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));
	if (!v){
		printf("Eroare alocare!\n");
		return -2;
	}
	g = (int *)malloc(n*sizeof(int));
	if (!g){
		free(v);
		printf("Eroare alocare!\n");
		return -2;
	}
	s = (char *)malloc(n);
	if (!s){
		free(v);
		free(g);
		printf("Eroare alocare!\n");
		return -2;
	}
	ss = (char *)malloc(n);
	if (!ss){
		free(s);
		free(v);
		free(g);
		return -2;
	}
	/* initial nu avem nicio cabana selectata pt. post de prim ajutor */
	for(i=0;i<n;i++)
		s[i]=0;
	/* ======= citire pt Salvare ==== */
	if (transf(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);
			np = np->urm;
		}
		printf("g=%i \n",g[i]);
	}
	*/
	
	/* === Algoritm ===*/
	/* Se aplica o cautare binara dupa dmed => O(lgn)*/
	/*
	dmin = 1; 
	dmax = n;
	min = INF;
	while(dmin<=dmax){ 
		dmed=(dmin+dmax)/2;
		for(i=0;i<n;i++) s[i]=0;
		nr = alege(dmed, n, m, v, g, s);
		if (nr<=m){ 
			dmax=dmed-1;
			if (min>dmed){
				min = dmed;
				memcpy(ss, s, n);
			}
		}
		else 
			dmin=dmed+1; 
	}
	
	/* === Varianta iterativa de cautare O(n) */
	
	for (dmed=1; dmed<=n; dmed++){
		for(i=0;i<n;i++) s[i]=0;
		nr = alege(dmed, n, m, v, g, s);
		if (nr<=m)
			if (verif(v, dmed, s, n)==1)
				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;
}