#include <bits/stdc++.h>
using namespace std;
const int MM = 2e5 + 10;
int pr[MM];
vector<pair<int, int> > point;
vector<int> graph[MM];
int ind[MM];
int n, m;
int find(int x) { return (pr[x] == x) ? x : pr[x] = find(pr[x]); }
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v;
    graph[u].push_back(v);
    graph[v].push_back(u);
    ind[u]++;
    ind[v]++;
  }
  for (int i = 1; i <= n; i++) {
    point.push_back({ind[i], i});
  }
  sort(point.begin(), point.end());
  reverse(point.begin(), point.end());
  for (int i = 0; i < MM; i++) pr[i] = i;
  int cnt = 0;
  for (int i = 0; i < point.size(); i++) {
    int nod = point[i].second;
    for (auto x : graph[nod]) {
      int u = find(pr[nod]);
      int v = find(pr[x]);
      if (u != v) {
        pr[u] = v;
        printf("%d %d\n", nod, x);
        cnt++;
      }
      if (cnt == n - 1) break;
    }
  }
  return 0;
}
