#include <bits/stdc++.h>
using namespace std;
long long int x[200007], p, sor, vis[200007], par[200007];
vector<long long int> a[200007];
long long int fppp(long long int x) {
  if (par[x] == x) return x;
  return par[x] = fppp(par[x]);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int n, m;
  cin >> n >> m;
  long long int i;
  for (i = 0; i <= n; i++) par[i] = i;
  for (i = 0; i < m; i++) {
    long long int r, y;
    cin >> r >> y;
    a[r].push_back(y);
    a[y].push_back(r);
    x[r]++;
    x[y]++;
    if (x[r] > p) {
      p = x[r];
      sor = r;
    }
    if (x[y] > p) {
      p = x[y];
      sor = y;
    }
  }
  queue<long long int> q;
  q.push(sor);
  vis[sor] = 1;
  while (!q.empty()) {
    long long int u = q.front();
    q.pop();
    for (i = 0; i < a[u].size(); i++) {
      if (!vis[a[u][i]]) {
        vis[a[u][i]] = 1;
        long long int v = a[u][i];
        long long int g = fppp(u);
        long long int h = fppp(v);
        if (g != h) {
          cout << u << " " << v << endl;
          par[g] = h;
        }
        q.push(v);
      }
    }
  }
  return 0;
}
