Untitled

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class DisjointSet {
private:
    vector<int> parent;
    int components;

public:
    DisjointSet(int n) : components(n) {
        parent.resize(n + 1);
        for (int i = 0; i <= n; i++)
            parent[i] = i;
    }

    int root_parent(int u) {
        if (u == parent[u])
            return u;
        parent[u] = root_parent(parent[u]);
        return parent[u];
    }

    bool union_by_size(int u, int v) {
        int parent_u = root_parent(u);
        int parent_v = root_parent(v);

        if (parent_u == parent_v)
            return false;

        if (parent_u >= parent_v)
            parent[parent_u] = parent_v;
        else
            parent[parent_v] = parent_u;

        components--;
        return true;
    }

    int getComponents() const {
        return components;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    DisjointSet ds(n);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        ds.union_by_size(a, b);
    }

    int numBridges = ds.getComponents() - 1;
    vector<int> min_vals;

    for (int i = 1; i <= n; i++) {
        if (ds.root_parent(i) == i)
            min_vals.push_back(i);
    }

    sort(min_vals.rbegin(), min_vals.rend());
    int min_cost = accumulate(min_vals.begin(), min_vals.end(), 0) + min_vals.back() * (min_vals.size() - 2);

    cout << numBridges << " " << min_cost << endl;

    for (int i = 0; i < min_vals.size() - 1; i++)
        cout << min_vals[i] << " " << min_vals.back() << endl;

    return 0;
}