#include <bits/stdc++.h>
using namespace std;
typedef priority_queue<int, vector<int>, greater<int>()> p_que_rev;
const long long LINF = LLONG_MAX;
const int MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};
using Weight = long long;
struct Edge {
  int src, dst;
  Weight weight;
  Edge() : src(0), dst(0), weight(0) {}
  Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;
const Weight INF = numeric_limits<Weight>::max() / 8;
void add_edge(Graph &g, int a, int b, Weight w) {
  g[a].push_back(Edge(a, b, w));
  g[b].push_back(Edge(b, a, w));
}
void add_arc(Graph &g, int a, int b, Weight w) {
  g[a].push_back(Edge(a, b, w));
}
template <class Abel>
struct UnionFind {
  vector<int> par;
  vector<int> rank;
  vector<Abel> diff_weight;
  UnionFind(int n, Abel enherit = 0) { init(n, enherit); }
  void init(int n, Abel enherit = 0) {
    par.resize(n);
    rank.resize(n);
    diff_weight.resize(n);
    for (int i = 0; i < n; ++i) {
      par[i] = i;
      rank[i] = 0;
      diff_weight[i] = enherit;
    }
  }
  int root(int x) {
    if (par[x] == x) {
      return x;
    } else {
      int r = root(par[x]);
      diff_weight[x] += diff_weight[par[x]];
      return par[x] = r;
    }
  }
  Abel weight(int x) {
    root(x);
    return diff_weight[x];
  }
  bool is_same(int x, int y) { return root(x) == root(y); }
  bool unite_set(int x, int y, Abel w) {
    w += weight(x);
    w -= weight(y);
    x = root(x);
    y = root(y);
    if (x == y) {
      return false;
    }
    if (rank[x] < rank[y]) {
      swap(x, y);
      w = -w;
    }
    if (rank[x] == rank[y]) {
      ++rank[x];
    }
    par[y] = x;
    diff_weight[y] = w;
    return true;
  }
  Abel diff(int x, int y) { return weight(y) - weight(x); }
};
int main() {
  int n, m, s, t;
  cin >> n >> m;
  Graph g;
  set<pair<int, int>> ans;
  int counter[n];
  UnionFind<int> uf(n);
  priority_queue<pair<int, int>> que;
  for (int i = 0; i < n; ++i) {
    counter[i] = 0;
  }
  g.resize(n);
  for (int i = 0; i < m; ++i) {
    cin >> s >> t;
    s--;
    t--;
    counter[s]++;
    counter[t]++;
    add_edge(g, s, t, 1);
  }
  for (int i = 0; i < n; ++i) {
    que.push(make_pair(counter[i], i));
  }
  while (!que.empty() && ans.size() < n - 1) {
    auto p = que.top();
    que.pop();
    for (int i = 0; i < (int)g[p.second].size(); ++i) {
      if (!uf.is_same(g[p.second][i].src, g[p.second][i].dst)) {
        uf.unite_set(g[p.second][i].src, g[p.second][i].dst, 1);
        ans.insert(make_pair(g[p.second][i].src, g[p.second][i].dst));
      }
    }
  }
  for (auto itr = ans.begin(); itr != ans.end(); ++itr) {
    auto p = *itr;
    cout << p.first + 1 << " " << p.second + 1 << endl;
  }
  return 0;
}
