CSES-BuildingRoads

//Lucas Hernán Tarche, 4to 4ta Turno Tarde, ESCCP
#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> ady;
vector<bool> visited;

vector<pair<int, int>> res;

void dfs(int node) {
    if(visited[node]) return;
    visited[node] = true;
    for (auto edge : ady[node]) {
        dfs(edge);
    }
}

int main() {
    int N, M, u, v;
    cin >> N >> M;
    ady.resize(N+1);
    visited.resize(N+1);
    for (int i = 0; i < M; i++) {
        cin >> u >> v;
        ady[u].push_back(v);
        ady[v].push_back(u);
    }

    dfs(1);

    for (int i = 2; i <= N; i++) {
        if (!visited[i]) {
            res.push_back({1, i});
            dfs(i);
            ady[1].push_back(i);
            ady[i].push_back(1);
        }
    }

    cout << (int)res.size() << endl;
    for (auto edge : res){
        cout << edge.first << " " << edge.second << endl;
    }
}