#include <stdio.h>
#define MAX_N  1000
#define ABS(a) (((a) < 0) ? -(a) : (a))

int sousedi[MAX_N+1][MAX_N+1];  //mělo by se dynamicky alokovat; každý to zvládne
int sousedi_len[MAX_N+1];
int barvy[MAX_N+1]; //barva vrcholů
int nvrcholu[2], nstanic; // počet vrcholů dané barvy a stanic celkem

int obarvi(int v, int barva) {
  barvy[v] = barva; // $>$0 -- se stanicí, $<$0 -- bez stanice
  nvrcholu[ (barva > 0) ? 0 : 1 ]++;

  for (int i=0; i<sousedi_len[v]; i++) {
    if ( barvy[ sousedi[v][i] ] == barva ) return 0; // lichý cyklus

    if ( ABS(barvy[ sousedi[v][i] ]) < ABS(barva) ) // pokud ještě nebyl obarven v tomto kole, přebarvi
      if (!obarvi(sousedi[v][i], -barva)) return 0;
  }
  return 1;
}

int main() {
  int i, n, m, v[2];

  printf("Zadejne n a m:");
  scanf("%d %d",&n,&m); // počet měst a cest
  for (i=0; i<m; i++) {
    printf("Zadejte %d. hranu:",i+1);
    scanf("%d %d",v+0,v+1);
    sousedi[v[0]][sousedi_len[v[0]]++]=v[1];    
    sousedi[v[1]][sousedi_len[v[1]]++]=v[0];
  }
  for (i=1; i<=n; i++)
    if (barvy[i] == 0) { // chceme pouze neobarvené
      nvrcholu[0] = nvrcholu[1] = 0; // počet barev v komponentě
      if (!obarvi(i, 1)) // zkusime začít `kladnou' barvou
	break;
      nstanic += nvrcholu[ (nvrcholu[0] < nvrcholu[1]) ? 0 : 1 ];
      if (nvrcholu[0] > nvrcholu[1]) obarvi(i, -2); // lze umístnit méně stanic, přebarvíme
    }
  if (i > n) { // povedlo se obarvit všechny vrcholy
    printf("Stačí postavit %d stanic.\n",nstanic);
    for (i=1; i<=n; i++) if (barvy[i] > 0) printf("%d\n",i);
  } else printf("Stanice postavit nelze!\n");

  return 0;
}