#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)(1e6 + 7);
const long long oo = (long long)(1e17);
int n, m, maxDegree, vertexMaxDegree, lab[MAXN];
vector<int> vr[MAXN];
int getRoot(int u) {
  while (lab[u] > 0) {
    u = lab[u];
  }
  return u;
}
void unionn(int u, int v) {
  int x = lab[u] + lab[v];
  if (lab[u] > lab[v]) {
    lab[u] = v;
    lab[v] = x;
  } else {
    lab[u] = x;
    lab[v] = u;
  }
}
int main() {
  maxDegree = 0;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    lab[i] = -1;
  }
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    vr[u].push_back(v);
    vr[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    if (maxDegree < (int)vr[i].size()) {
      maxDegree = (int)vr[i].size();
      vertexMaxDegree = i;
    }
  }
  for (int u : vr[vertexMaxDegree]) {
    int rU = getRoot(u);
    int rV = getRoot(vertexMaxDegree);
    if (rU != rV) {
      unionn(rU, rV);
      cout << u << " " << vertexMaxDegree << endl;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (i != vertexMaxDegree) {
      for (int u : vr[i]) {
        if (u != vertexMaxDegree) {
          int rU = getRoot(u);
          int rV = getRoot(i);
          if (rU != rV && u < i) {
            unionn(rU, rV);
            cout << u << " " << i << endl;
          }
        }
      }
    }
  }
  return 0;
}
