#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const long long mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
vector<int> ff[maxn];
pair<int, int> p[maxn];
vector<pair<int, int> > ans;
bool vis[maxn];
long long n, m, k, t, sum = 0;
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> k >> t;
    ff[k].push_back(t);
    ff[t].push_back(k);
  }
  for (int i = 1; i <= n; i++) {
    p[i].first = ff[i].size();
    p[i].second = i;
  }
  sort(p + 1, p + 1 + n);
  reverse(p + 1, p + 1 + n);
  queue<int> q;
  vis[p[1].second] = 1;
  for (auto i : ff[p[1].second])
    q.push(i), vis[i] = 1, ans.push_back(make_pair(i, p[1].second));
  while (!q.empty()) {
    int now = q.front();
    q.pop();
    for (auto i : ff[now])
      if (!vis[i]) vis[i] = 1, ans.push_back(make_pair(i, now)), q.push(i);
  }
  for (auto i : ans) cout << i.first << " " << i.second << endl;
}
