#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
/*
Объявляем структуру Ребро, которой будем пользоваться для построения графа и дерева
*/
struct edge{
int x, y; //вершины
edge(){}
edge(int a, int b){
x = a;
y = b;
}
};
int main() {
int n, m;
cin >> n >> m;
vector <edge> graph (m); //ребра исходного графа
vector <edge> tree; //ребра дерева
vector <int> variety (n); //множество вершин
/*
variety[n] = m - вершина n принадлежит множеству m.
Следующий цикл определяет для каждой вершины свое множество
*/
for (int i = 0; i < n; i++){
variety[i] = i;
}
/*
Заполняем ребра исходного графа значениями из стандартного ввода
*/
for (int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
graph[i].x = a;
graph[i].y = b;
}
/*
Проверяем вершины каждого ребра.
Если вершины не принадлежат одному и тому же множеству,
но такое ребро добавляем в наше дерево, а вершины помещаем в одно множество
*/
for (int i = 0; i < m; i++){
int a = graph[i].x;
int b = graph[i].y;
if (variety[a] != variety[b]){
tree.push_back(graph[i]);
int old_variety = variety[b], new_variety = variety[a];
for (int j = 0; j < n; j++){
if (variety[j] == old_variety){
variety[j] = new_variety;
}
}
}
}
for(int i = 0; i < n-1; i++){ //по принципу построения дерева, оно содержит n-1 ребро
cout << tree[i].x << " " << tree[i].y;
if (i != n-2){
cout << endl;
}
}
return 0;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCi8qCtCe0LHRitGP0LLQu9GP0LXQvCDRgdGC0YDRg9C60YLRg9GA0YMg0KDQtdCx0YDQviwg0LrQvtGC0L7RgNC+0Lkg0LHRg9C00LXQvCDQv9C+0LvRjNC30L7QstCw0YLRjNGB0Y8g0LTQu9GPINC/0L7RgdGC0YDQvtC10L3QuNGPINCz0YDQsNGE0LAg0Lgg0LTQtdGA0LXQstCwCiovCnN0cnVjdCBlZGdlewoJaW50IHgsIHk7IC8v0LLQtdGA0YjQuNC90YsKCWVkZ2UoKXt9CgllZGdlKGludCBhLCBpbnQgYil7CgkJeCA9IGE7CgkJeSA9IGI7Cgl9Cn07CgppbnQgbWFpbigpIHsKCWludCBuLCBtOwoJY2luID4+IG4gPj4gbTsKCQoJdmVjdG9yIDxlZGdlPiBncmFwaCAobSk7IC8v0YDQtdCx0YDQsCDQuNGB0YXQvtC00L3QvtCz0L4g0LPRgNCw0YTQsAoJdmVjdG9yIDxlZGdlPiB0cmVlOyAvL9GA0LXQsdGA0LAg0LTQtdGA0LXQstCwCgl2ZWN0b3IgPGludD4gdmFyaWV0eSAobik7IC8v0LzQvdC+0LbQtdGB0YLQstC+INCy0LXRgNGI0LjQvQoJCgkvKgoJdmFyaWV0eVtuXSA9IG0gLSDQstC10YDRiNC40L3QsCBuINC/0YDQuNC90LDQtNC70LXQttC40YIg0LzQvdC+0LbQtdGB0YLQstGDIG0uCgnQodC70LXQtNGD0Y7RidC40Lkg0YbQuNC60Lsg0L7Qv9GA0LXQtNC10LvRj9C10YIg0LTQu9GPINC60LDQttC00L7QuSDQstC10YDRiNC40L3RiyDRgdCy0L7QtSDQvNC90L7QttC10YHRgtCy0L4KCSovCglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKyl7CgkJdmFyaWV0eVtpXSA9IGk7Cgl9CgkKCS8qCgnQl9Cw0L/QvtC70L3Rj9C10Lwg0YDQtdCx0YDQsCDQuNGB0YXQvtC00L3QvtCz0L4g0LPRgNCw0YTQsCDQt9C90LDRh9C10L3QuNGP0LzQuCDQuNC3INGB0YLQsNC90LTQsNGA0YLQvdC+0LPQviDQstCy0L7QtNCwCgkqLwoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspewoJCWludCBhLCBiOwoJCWNpbiA+PiBhID4+IGI7CgkJZ3JhcGhbaV0ueCA9IGE7CgkJZ3JhcGhbaV0ueSA9IGI7Cgl9CgkKCS8qCgnQn9GA0L7QstC10YDRj9C10Lwg0LLQtdGA0YjQuNC90Ysg0LrQsNC20LTQvtCz0L4g0YDQtdCx0YDQsC4gCgnQldGB0LvQuCDQstC10YDRiNC40L3RiyDQvdC1INC/0YDQuNC90LDQtNC70LXQttCw0YIg0L7QtNC90L7QvNGDINC4INGC0L7QvNGDINC20LUg0LzQvdC+0LbQtdGB0YLQstGDLCAKCdC90L4g0YLQsNC60L7QtSDRgNC10LHRgNC+INC00L7QsdCw0LLQu9GP0LXQvCDQsiDQvdCw0YjQtSDQtNC10YDQtdCy0L4sINCwINCy0LXRgNGI0LjQvdGLINC/0L7QvNC10YnQsNC10Lwg0LIg0L7QtNC90L4g0LzQvdC+0LbQtdGB0YLQstC+CgkqLwoJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspewoJCWludCBhID0gZ3JhcGhbaV0ueDsKCQlpbnQgYiA9IGdyYXBoW2ldLnk7CgkJaWYgKHZhcmlldHlbYV0gIT0gdmFyaWV0eVtiXSl7CgkJCXRyZWUucHVzaF9iYWNrKGdyYXBoW2ldKTsKCQkJaW50IG9sZF92YXJpZXR5ID0gdmFyaWV0eVtiXSwgbmV3X3ZhcmlldHkgPSB2YXJpZXR5W2FdOwoJCQlmb3IgKGludCBqID0gMDsgaiA8IG47IGorKyl7CgkJCQlpZiAodmFyaWV0eVtqXSA9PSBvbGRfdmFyaWV0eSl7CgkJCQkJdmFyaWV0eVtqXSA9IG5ld192YXJpZXR5OwoJCQkJfQoJCQl9CgkJCQoJCQkKCQkJCgkJfQoJfQoKCQoJZm9yKGludCBpID0gMDsgaSA8IG4tMTsgaSsrKXsgLy/Qv9C+INC/0YDQuNC90YbQuNC/0YMg0L/QvtGB0YLRgNC+0LXQvdC40Y8g0LTQtdGA0LXQstCwLCDQvtC90L4g0YHQvtC00LXRgNC20LjRgiBuLTEg0YDQtdCx0YDQvgoJCWNvdXQgPDwgdHJlZVtpXS54IDw8ICIgIiA8PCB0cmVlW2ldLnk7CgkJaWYgKGkgIT0gbi0yKXsKCQkJY291dCA8PCBlbmRsOwoJCX0KCX0KCXJldHVybiAwOwp9