#include <fstream>
#include <vector>
using namespace std;
vector <vector <int> > b;// списки суміжності
        vector <int>  b0;// список суміжеості однієї вершини
int nv,ne,m,             // вхідні дані з першого рядка
         v0,             // корінь каркасного дерева - початкова вершина
          v,             // поточна вершина
       l[9],             // поточні номери ребер у списках суміжності
      i,j,k;             // лічильники
bool neo[9];             // мітки "нова вершина"
ifstream fi;             // оголошення потоку зчтитування з файлу fi
ofstream fo;             // оголошення потоку запису у файл fo

void step(int v)
{ while (l[v] < b[v].size())
  { int w=b[v][l[v]];
    l[v]++;
    if (neo[w])
    {   neo[w]=false;
        fo<<v<<" "<<w<<endl;
        step(w);
    }
  }
}

int main()
{ fi.open("input.txt");    // прив'язування назви файлу до змінної fi
  fo.open("output.txt");   // gрив'язування назви файлу до змінної fo
  fi>>nv>>ne;
  for (j=0; j<nv; j++) b.push_back(b0);
  for (m=0; m<ne; m++)
  { fi>>j>>k;
    b[j].push_back(k);
    b[k].push_back(j);
  }
  fi.close();
  for (j=0; j<nv; j++)
  { neo[j]=true;
    l[j]=0;
  }
  v0=0;
  neo[v0]=false;
  step(v0);
  fo.close();
  return 0;
}