#include <bits/stdc++.h>
using namespace std;
struct yes {
  int first, second, cost;
};
yes muc[200000 + 5];
int grad[200000 + 5];
vector<pair<int, int> > ans;
int dad[200000 + 5];
int sz[200000 + 5];
int sel;
bool cmp(yes a, yes b) { return a.cost > b.cost; };
int find_(int x) {
  int r = x, aux;
  while (dad[r] != r) r = dad[r];
  while (x != r) {
    aux = dad[x];
    dad[x] = r;
    x = aux;
  }
  return r;
}
void union_(int a, int b) {
  int da = a, db = b;
  a = find_(a);
  b = find_(b);
  if (a == b) return;
  ans.push_back({da, db});
  if (sz[a] > sz[b])
    dad[b] = a, sz[a] += sz[b], sz[b] = 0;
  else
    dad[a] = b, sz[b] += sz[a], sz[a] = 0;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, m;
  cin >> n >> m;
  int i, j, z;
  for (i = 0; i < m; i++) {
    cin >> muc[i].first >> muc[i].second;
    muc[i].first--;
    muc[i].second--;
    grad[muc[i].first]++;
    grad[muc[i].second]++;
  }
  for (i = 0; i < n; i++)
    if (grad[sel] < grad[i]) sel = i;
  for (i = 0; i < m; i++) {
    if (muc[i].first == sel || muc[i].second == sel)
      muc[i].cost = (INT_MAX / 2 - 1);
    else
      muc[i].cost = max(grad[muc[i].first], grad[muc[i].second]);
  }
  sort(muc, muc + m, cmp);
  for (i = 0; i < n; i++) dad[i] = i, sz[i] = 1;
  for (i = 0; i < m; i++) union_(muc[i].first, muc[i].second);
  for (i = 0; i < (int)(ans).size(); i++)
    cout << 1 + ans[i].first << ' ' << 1 + ans[i].second << '\n';
  return 0;
}
