первая из доп контеста

#include <iostream>
#include <vector>

using namespace std;

class DSU {
    int num_of_sets;
    vector<int> parent;
    vector<int> size;
    vector<vector<int>> content;

public:

    explicit DSU(int n) {
        num_of_sets = n;
        parent.resize(n);
        size.resize(n, 1);
        content.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            content[i].emplace_back(i);
        }
    }

    int getParent(int v) {
        if (parent[v] == v)
            return v;
        return parent[v] = getParent(parent[v]);
    }

    void joinSets(int set1, int set2) {
        set1 = getParent(set1);
        set2 = getParent(set2);
        if (set1 != set2) {
            if (size[set1] < size[set2])
                swap(set1, set2);

            content[set1].insert(content[set1].end(), content[set2].begin(), content[set2].end());
            content[set2].clear();

            parent[set2] = set1;
            size[set1] += size[set2];
            num_of_sets--;
        }
    }

    int getNumOfSets() const {
        return num_of_sets;
    }

    vector<int> getContent(){
        return content[getParent(0)];
    }
};


int main() {
    int n;
    cin >> n;
    DSU a(n);
    for (int i = 0; i < n - 1; i++){
        int v1, v2;
        cin >> v1 >> v2;
        v1--;
        v2--;
        a.joinSets(v1, v2);
    }
    auto answer = a.getContent();
    for (auto &i : answer)
        cout << i + 1 << ' ';

    return 0;
}