#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> vc;
vector<tuple<int, int, int>> c;
int cost[200005];
int uf[200005];
int find(int x) {
  if (uf[x] == -1)
    return x;
  else
    return uf[x] = find(uf[x]);
}
bool merge(int a, int b) {
  a = find(a);
  b = find(b);
  if (a == b) return false;
  uf[b] = a;
  return true;
}
int main() {
  int n, k;
  cin >> n >> k;
  memset(uf, -1, sizeof(uf));
  vc.resize(n + 1);
  for (int i = 0; i < k; i++) {
    int a, b;
    cin >> a >> b;
    vc[a].push_back(b);
    vc[b].push_back(a);
    cost[a]++;
    cost[b]++;
  }
  for (int i = 1; i <= n; i++)
    for (auto j : vc[i]) c.push_back(make_tuple(cost[i], i, j));
  sort(c.begin(), c.end(), greater<tuple<int, int, int>>());
  int cnt = 0;
  for (int i = 0; i < c.size(); i++) {
    int a = get<1>(c[i]);
    int b = get<2>(c[i]);
    if (merge(a, b)) {
      cout << a << ' ' << b << '\n';
      if (++cnt == n - 1) break;
    }
  }
  return 0;
}
