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