#include <bits/stdc++.h>
using namespace std;
int Int() {
  int x;
  scanf("%d", &x);
  return x;
}
long long Long() {
  long long x;
  scanf("%lld", &x);
  return x;
}
void err(istream_iterator<string> it) { cout << endl; }
template <typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << a << ' ';
  err(++it, args...);
}
const int N = (int)2e5 + 5;
const int maxN = (int)1e6 + 6;
const long long Mod = (long long)1e9 + 7;
const int inf = (int)2e9;
const long long Inf = (long long)1e18;
int deg[N], vis[N];
vector<int> g[N];
int par[N];
int Find(int s) { return par[s] == s ? s : Find(par[s]); }
int main() {
  int test = 1, tc = 0;
  while (test--) {
    int n = Int(), m = Int(), mx = 0, node = 0;
    for (int i = 1; i <= m; ++i) {
      int x = Int(), y = Int();
      deg[x]++, deg[y]++;
      if (deg[x] > mx) {
        mx = deg[x], node = x;
      }
      if (deg[y] > mx) {
        mx = deg[y], node = y;
      }
      g[x].push_back(y);
      g[y].push_back(x);
    }
    priority_queue<pair<int, int> > pp;
    pp.push({mx, node});
    while (!pp.empty()) {
      pair<int, int> c = pp.top();
      pp.pop();
      vis[c.second] = 1;
      for (int i : g[c.second]) {
        if (vis[i]) continue;
        printf("%d %d\n", i, c.second);
        vis[i] = 1;
        pp.push({deg[i], i});
      }
    }
  }
  return 0;
}
