#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
vector<pair<int, int> > ed;
int fa[200005];
int de[200005];
int fi(int x) { return x == fa[x] ? x : fa[x] = fi(fa[x]); }
int main() {
  int n, m;
  pair<int, int> s;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    fa[i] = i;
  }
  for (int i = 0; i < m; ++i) {
    scanf("%d%d", &s.first, &s.second);
    ed.push_back(s);
    de[s.first]++;
    de[s.second]++;
  }
  int mx = 0, id = 0;
  for (int i = 1; i <= n; ++i) {
    if (mx < de[i]) {
      mx = de[i];
      id = i;
    }
  }
  for (int i = 0; i < m; ++i) {
    if (ed[i].first == id) {
      fa[ed[i].second] = id;
      printf("%d %d\n", ed[i].first, ed[i].second);
    } else if (ed[i].second == id) {
      fa[ed[i].first] = id;
      printf("%d %d\n", ed[i].first, ed[i].second);
    }
  }
  for (int i = 0; i < m; ++i) {
    int af = fi(ed[i].first);
    int bf = fi(ed[i].second);
    if (af == bf) continue;
    if (af == id) {
      fa[bf] = id;
      printf("%d %d\n", ed[i].first, ed[i].second);
    } else if (bf == id) {
      fa[af] = id;
      printf("%d %d\n", ed[i].first, ed[i].second);
    } else {
      fa[af] = bf;
      printf("%d %d\n", ed[i].first, ed[i].second);
    }
  }
  return 0;
}
